Симплексный метод решения задач ЛП
Общая постановка задачи Симплексный метод – метод последовательного улучшения плана. Метод является универсальным, так как позволяет решить практически любую задачу линейного программирования. Математическая модель задачи приводится к каноническому (стандартному) виду. Заполняется опорная симплекс – таблица с использованием коэффициентов целевой функции и системы ограничений. Решается задача по алгоритму. Идея симплексного метода заключается в том, что начиная с некоторого исходного опорного решения осуществляется последовательно направленное перемещение по допустимым решениям к оптимальному. Значение целевой функции для задач на максимум не убывает. Так как число допустимых решений конечно, то через конечное число шагов получим оптимальное решение.
Алгоритм симплексного метода
1.Математическую модель задачи привести к каноническому (стандартному) виду.
2. Построить начальную симплекс-таблицу исходя из стандартного вида.
3. Найти разрешающий столбец. В строке коэффициентов ЦФ найти значение с самим маленьким отрицательным числом. Этот столбец и будет разрешающим.
4. Вычислить разрешающую строку и ведущий элемент (Почленно разделить столбец свободных членов на элементы разрешающего столбца, за исключением строки ЦФ. Выбрать наименьшее из частных. Эта строка будет разрешающей.Ведущий элемент будет на пересечении разрешающего столбца и разрешающей строки.).
5.Построить новую симплекс-таблицу-второй шаг.
При построении новой таблицы убрать из базиса строку с переменной разрешающей строки в предыдущей таблице. Ввести в базис строку с названием разрешающего столбца предыдущей таблицы.
· Построение ведущей строки в новой таблице. Почленно поделить всю разрешающую строку на разрешающий элемент. · Построение других строк в новой таблице. Почленно умножить ведущую строку на соответствующие этим строкам элементы разрешающего столбца из предыдущей таблицы и прибавить к соответствующим строкам в старой таблице.
6. Проверяем таблицу второго шага на оптимальность. Если в строке целевой функции нет отрицательных элементов, тогда таблица имеет оптимальный план, записать ответ. Если в строке ЦФ есть отрицательный элемент (элементы), тогда переходят к следующему (третьему) шагу, строят новую симплекс-таблицу в соответствии п.5 и затем проверяют ее на оптимальность. Построение таблиц заканчивается с нахождением оптимального плана.
Прямая задача на минимум решается следующим образом: · Написать математическую модель двойственной задачи в стандартном виде · Решить двойственную модель симплекс - методом · Записать ответ.
Связь между задачами двойственной пары в том, что, решая симплексным методом одну из них, автоматически получаем решение другой. Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач в последней симплекс-таблице.
Задача На предприятии имеется возможность выпускать 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= 6x1+5x2+4x3+3x4) 2x1+3x2+2x3+x4 < 25 4x1+x2+3x3+2x4 < 30 3x1+5x2+2x3+2x4 < 42 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
|
