3.2. Симплекс-метод решения задач линейного программирования
Поскольку, как было показано в п. 3.1 решение задачи линейного программирования находится в одной из крайних (угловых) точек ОДЗ, важным вопросом является изучение не системы неравенств (4), а соответствующей системы уравнений AX = B, решение которой дает угловые точки ОДЗ.
Если уравнения системы АX = B линейно независимы, то система имеет множество решений при n > m и единственное решение при n = m. При решении задачи линейного программирования симплекс-методом всегда будет выполняться n > m, поэтому для получения некоторого одного решения, «лишние» n – m переменных приравниваются нулю.
Если приравнять к нулю n – m произвольных переменных (например, переменные xm+1, xm+2, …, xn) и, решив систему, найти значения оставшихся m переменных (x1, x2, …, xm), то такое решение называется базисным.
Если нулю приравнять некоторые другие n – m переменных – получим другое базисное решение. Любое базисное решение, у которого все переменные неотрицательные называется допустимым базисным решением.
Переменные, которые были приравнены нулю, называются небазисными. Оставшиеся т переменных, значение которых получены из решения системы, называются базисными.
Допустимое базисное решение представляет собой угловую вершину ОДЗ.
Решение задачи симплекс-методом сводится к направленному перебору смежных друг с другом угловых точек, которые представляют собой допустимые базисные решения.
Сформулируем в общем виде алгоритм симплекс-метода:
1: Приведение задачи к стандартной форме. Стандартной формой задачи линейного программирования будем называть задачу, у которой все ограничения записаны как равенства и при этом правые части ограничений неотрицательны.
2: Выделение исходного базисного решения (по возможности из стандартной формы). То есть определение тех переменных n – m переменных, которые приравниваются нулю и нахождение значений оставшихся базисных переменных.
3: Определение, является ли полученное базисное решение оптимальным, если да, то решение окончено, иначе переходим к шагу 4.
4: Определение переменной, которая войдет в базис и переменной, которая из базиса выйдет таким образом, чтобы новое решение было лучше предыдущего. То есть, если текущее базисное решение неоптимально, необходимо определить, какую из базисных переменных приравнять нулю, и какую из небазисных переменных вместо нее включить в базис.
5: Использование эквивалентных преобразований методом Жордана-Гаусса для нахождения нового допустимого базисного решения. Переход к шагу 3.
Чтобы привести задачу линейного программирования к стандартной форме необходимо:
1. Убедиться, что во всех ограничениях правые части bi неотрицательны. Если есть отрицательные правые части ограничений, такие ограничения нужно умножить на –1 (при этом учесть, что в ограничениях типа или знак ограничения изменится на противоположный).
2. К левой части ограничений типа нужно прибавить новую, дополняющую переменную S, которая уравнивала бы левую и правую часть и показывала бы насколько левая часть ограничения меньше правой.
в стандартном виде будет выглядеть так:
3. Из левой части ограничений типа нужно вычесть новую, избыточную переменную e, которая уравнивала бы левую и правую часть и показывала бы насколько левая часть ограничения больше правой.
в стандартном виде будет выглядеть так:
Дополняющие переменные S и избыточные e будем называть вспомогательными, в то время, как переменные x – основными.
Чтобы из стандартной формы сразу выделить базисное решение, необходимо в качестве базисных переменных выбрать те m переменных, каждая из которых встречается только в одном из уравнений и включена в него с коэффициентом, равным единице.
В качестве исходных базисных переменных в задачах с ограничениями удобно брать переменные S1, …, Sn.
Реализацию алгоритма симплекс-метода проиллюстрируем на следующем примере.
Пример 3.2. Мебельная фабрика может производить шкафы, столы, стулья. При изготовлении мебели используются древесина, труд рабочих на столярном и отделочном участках. Необходимое количество ресурсов для изготовления шкафов, столов и стульев приведено в таблице:
Таблица 3.1 – Исходные данные к примеру 3.2
3. 5 Симплексный метод решения задач лп
Метод является универсальным, так как позволяет решить практически любую задачу линейного программирования. Математическая модель задачи приводится к каноническому (стандартному) виду. Заполняется опорная симплекс – таблица с использованием коэффициентов целевой функции и системы ограничений. Решается задача по алгоритму.
Идея симплексного метода заключается в том, что начиная с некоторого исходного опорного решения осуществляется последовательно направленное перемещение по допустимым решениям к оптимальному. Значение целевой функции для задач на максимум не убывает. Так как число допустимых решений конечно, то через конечное число шагов получим оптимальное решение.
Алгоритм симплексного метода
1.Математическую модель задачи привести к каноническому (стандартному) виду.
2. Построить начальную симплекс-таблицу исходя из стандартного вида.
3. Найти разрешающий столбец. В строке коэффициентов ЦФ найти значение с самим маленьким отрицательным числом. Этот столбец и будет разрешающим.
4. Вычислить разрешающую строку и ведущий элемент (Почленно разделить столбец свободных членов на элементы разрешающего столбца, за исключением строки ЦФ. Выбрать наименьшее из частных. Эта строка будет разрешающей.Ведущий элемент будет на пересечении разрешающего столбца и разрешающей строки.).
5.Построить новую симплекс-таблицу-второй шаг.
При построении новой таблицы убрать из базиса строку с переменной разрешающей строки в предыдущей таблице. Ввести в базис строку с названием разрешающего столбца предыдущей таблицы.
- Построение ведущей строки в новой таблице. Почленно поделить всю разрешающую строку на разрешающий элемент.
- Построение других строк в новой таблице. Почленно умножить ведущую строку на соответствующие этим строкам элементы разрешающего столбца из предыдущей таблицы и прибавить к соответствующим строкам в старой таблице.
6. Проверяем таблицу второго шага на оптимальность. Если в строке целевой функции нет отрицательных элементов, тогда таблица имеет оптимальный план, записать ответ. Если в строке ЦФ есть отрицательный элемент (элементы), тогда переходят к следующему (третьему) шагу, строят новую симплекс-таблицу в соответствии п.5 и затем проверяют ее на оптимальность. Построение таблиц заканчивается с нахождением оптимального плана. Прямая задача на минимум решается следующим образом:
- Написать математическую модель двойственной задачи в стандартном виде
- Решить двойственную модель симплекс — методом
- Записать ответ.
Связь между задачами двойственной пары в том, что, решая симплексным методом одну из них, автоматически получаем решение другой. Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач в последней симплекс-таблице.
| Х1 | x2 | … | xn | S1 | S2 | … | Sm |
| S1 | S2 | … | Sm | y1 | y2 | … | ym |
Задача На предприятии имеется возможность выпускать n видов продукции (1,2,…n). При ее изготовлении используются ресурсы Р1, Р2, Р3. Размеры прямых затрат ресурсов ограничены соответственно величинами b1, b2, b3. Расход i –го ресурса на единицу продукции j-того вида составляют aij. Цена единицы продукции j-того вида равна cj ден. ед. Сформулировать прямую и двойственную задачу и раскрывать экономический смысл всех переменных. Требуется: Найти оптимальный план симплекс-методом. Найти решение двойственной задачи Указать дефицитность ресурсов Обосновать эффективность плана производства Оценить целесообразность приобретения ресурса Оценить целесообразность выпуска новой продукции Данные : b1 = 25, b2 = 30, b3 = 42 a11= 2, a12= 3, a13= 2, a14= 1 a21= 4, a22= 1, a23= 3, a24= 2 a31= 3, a32= 5, a33= 2,a34= 2 c1= 6, c2= 5, c3= 4, c4= 3 Математическая модель прямой задачи max (Z= 6×1+5×2+4×3+3×4) 2×1+3×2+2×3+x425 4×1+x2+3×3+2×430 3×1+5×2+2×3+2×442 x1, x2, x3, x4 > 0 Математическая модель двойственной задачи min (Z*= 25y1+30y2+42y3) 2y1+4y2+3y3> 6 3y1+y2+5y3> 5 2y1+3y2+2y3> 4 y1+2y2+2y3> 3 y1, y2, y3, y4 > 0 Стандартный вид min (Z= -6×1-5×2-4×3-3×4) 2×1+3×2+2×3+x4+S1=25 4×1+x2+3×3+2×4+S2=30 3×1+5×2+2×3+2×4+S3=42 x1, x2, x3, x4, S1, S2, S3 > 0 Экономический смысл переменных Xi – количество произведенной продукции Yj – цена ресурса Si – количество оставшегося ресурса
| базис | значение |  x1 | x2 | x3 | x4 | S1 | S2 | S3 | отношение |
| Z | 0 | -6 | -5 | -4 | -3 | 0 | 0 | 0 | |
| S1 | 25 | 2 | 3 | 2 | 1 | 1 | 0 | 0 | 12,5 |
 S2 | 30 | 4 | 1 | 3 | 2 | 0 | 1 | 0 | 7,5 |
| S3 | 42 | 3 | 5 | 2 | 2 | 0 | 0 | 1 | 14 |
| Таблица 2 | |||||||||
| базис | значение | x1 |  x2 | x3 | x4 | S1 | S2 | S3 | отношение |
| Z | 45 | 0 | -3,5 | 0,5 | 0 | 0 | 1,5 | 0 | |
S1  | 10 | 0 | 2,5 | 0,5 | 0 | 1 | -0,5 | 0 | 4 |
| x1 | 7,5 | 1 | 0,25 | 0,75 | 0,5 | 0 | 0,25 | 0 | 30 |
| S3 | 19,5 | 0 | 4,25 | -0,3 | 0,5 | 0 | -0,8 | 1 | 4,59 |
| Таблица 3 | |||||||||
| базис | значение | x1 | x2 | x3 | x4 | S1 | S2 | S3 | отношение |
| Z | 59 | 0 | 0 | 1,2 | 0 | 1,4 | 0,8 | 0 | |
| x2 | 4 | 0 | 1 | 0,2 | 0 | 0,4 | -0,2 | 0 | |
| x1 | 6,5 | 1 | 0 | 0,7 | 0,5 | -0,1 | 0,3 | 0 | |
| S3 | 2,5 | 0 | 0 | -1,1 | 0,5 | -1,7 | 0,1 | 1 | |
Анализ решения Продукции 1 вида производим 6,5 ед., второго вида 4 единицы, третьего и четвертого вообще не производим. Прибыль при этом составит 59 ден. единиц. Ресурс 1 типа стоит 1,4 ден. ед., 2 типа – 0,8 ден. ед. Третий тип ресурса у нас остался в количестве 2,5 ед., поэтому его покупать не нужно. Ресурсы 1 и 2 типа дефицитны, 3 типа избыточен. Эффективность производства Z = 6*6.5+5*4+4*0+3*0=59 Z*=25*1.4+30*0.8+42*0=59 Производство в целом эффективно 2*1,4+4*0,8+3*06 6=6 Производство 1 вида продукции эффективно 3*1,4+1*0,8+5*05 5=5 Производство 2 вида продукции эффективно 2*1,4+3*0,8+2*04 5,2> 4 Производство 3 вида продукции не эффективно 1*1,4+2*0,8+2*03 3=3 Т.к. x4 не входит в базис, то оптимальный план не единственен. Оценить целесообразность покупки 5 ед. второго ресурса по цене 10 ден. ед, т.е. единица ресурса обойдется нам в 2 ден. ед. Мы же готовы покупать только по 0,8 ден. ед. за 1 единицу ресурса. а1 = 2, а2 = 2, а3 = 4. Цена новой продукции равна 4. 2*1,4+2*0,8+2*04 4,4> 4 Производство 5 вида продукции не эффективно. Контрольные вопросы. 1.Определение математической модели экономической задачи. 2.Виды математических моделей ЛП. 3.Составление математической модели. 4.Экономическая формулировка математической модели прямой и двойственной задач. 5.Понятие двойственности в задачах линейного программирования. 6.Правило построения математической модели двойственной задачи. 7. Первая теорема двойственности. 8. Вторая теорема двойственности. 9. Третья теорема двойственности. 10.Алгоритм геометрического метода решения задач ЛП. 11.Симплексный метод решения задач ЛП и его применение. 12.Алгоритмм симплексного метода. 13.Анализ решения задачи по симплекс – таблице, отвечающей критерию оптимальности.