Симплексный метод решения задачи ЛП

1. Пример исходной задачи ЛП

2. Каноническая форма задачи ЛП СТАНДАРТНАЯ

Приведение к стандартному виду ограничения типа « ≥ »
Пример ограничения на

3. Матричная форма записи задачи

5. БАЗИСНАЯ ФОРМА ЗАДАЧИ ЛП ПРЕДПОЧИТАЕМАЯ, СИМПЛЕКСНАЯ опорный план

L =

СИМПЛЕКСНОЕ ОТНОШЕНИЕ ДЛЯ НОВОЙ БАЗИСНОЙ ПЕРЕМЕННОЙ x2

Решение разрешающего уравнения относительно x2

5. СИМПЛЕКСНАЯ ТАБЛИЦА с е д и н и ч н о

5а. с о к р а щ е н н а

6. ОЦЕНКИ НЕБАЗИСНЫХ ПЕРЕМЕННЫХ

Оценка Δi небазисной переменной xi
численно равна величине приращения

Небазисная переменная, оценка которой положительна, называется перспективной

Если текущий опорный план содержит перспективные переменные, то его можно улучшить

7.1. Преобразование СИМПЛЕКСНОЙ ТАБЛИЦЫ выбираем новую базисную переменную x2 Δ1= +5,

7.2. Преобразование СИМПЛЕКСНОЙ ТАБЛИЦЫ нахождение разрешающей строки

Величина симплексного отношения указывает максимально возможное значение новой базисной переменной, «

Признак неограниченности критерия

Если получена очередная таблица, для которой не найдено ни

7.1-2. Разрешающий элемент

7.3. Преобразование разрешающей строки производится путем ее деления на разрешающий элемент x2

7.4а. Преобразование остальных строк

Из преобразуемой строки вычитается
преобразованная разрешающая строка,

7.4.б. Преобразование строки x3

7.4.в. Преобразована строка x3

7.4.г. Преобразованы все строки

8. ОПТИМАЛЬНАЯ ТАБЛИЦА

8.а. ОПТИМАЛЬНАЯ ТАБЛИЦА

8.а. ОПТИМАЛЬНАЯ ТАБЛИЦА

Базисная форма

Базисная форма

8.а. ОПТИМАЛЬНАЯ ТАБЛИЦА

8.б. ОПТИМАЛЬНАЯ ТАБЛИЦА

9.а. Анализ конечной таблицы ПРИЗНАК ОПТИМАЛЬНОСТИ

Если все небазисные переменные имеют отрицательную оценку,

9.б. Анализ конечной таблицы ПРИЗНАК единственности оптимального плана

Если в оптимальном опорном

9.в. Анализ конечной таблицы ПРИЗНАК множества оптимальных планов

Если в оптимальном опорном

9.г. Анализ оценки дополнительной переменной x3 ⎯ остаток ресурса №1

Небазисная переменная x3*

Оптимальное значение критерия при этом получит приращение ΔL = − 0,4. и

Напротив, увеличение использования этого ресурса на 1, приведет к изменению оптимального