Симплекс-метод решения ЗЛП

Краткая теория

Для решения задач линейного программирования предложено немало различных методов. Однако наиболее эффективным и универсальным среди них оказался симплекс-метод. При этом следует отметить, что при решении некоторых задач могут оказаться более эффективными другие методы. Например, при ЗЛП с двумя переменными оптимальным является графический метод решения, а при решении транспортной задачи - метод потенциалов. Симплекс-метод является основным и применимым к любой ЗПЛ в канонической форме.

В связи с основной теоремой линейного программирования естественно возникает мысль о следующем пути решения ЗЛП с любым числом переменных. Найти каким-нибудь способом все крайние точки многогранника планов (их не больше, чем ) и сравнить в них значения целевой функции. Такой путь решения даже с относительно небольшим числом переменных и ограничений практически неосуществим, так как процесс отыскания крайних точек сравним по трудности с решением исходной задачи, к тому же число крайних точек многогранника планов может оказаться весьма большим. В связи с этими трудностями возникла задача рационального перебора крайних точек.

Суть симплексного метода в следующем. Если известны какая-нибудь крайняя точка и значение в ней целевой функции, то все крайние точки, в которых целевая функция принимает худшее значение, заведомо не нужны. Отсюда естественно стремление найти способ перехода от данной крайней точки к смежной по ребру лучшей, от нее к еще лучшей (не худшей) и т. д. Для этого нужно иметь признак того, что лучших крайних точек, чем данная крайняя точка, вообще нет. В этом и состоит общая идея наиболее широко применяемого в настоящее время симплексного метода (метода последовательного улучшения плана) для решения ЗЛП. Итак, в алгебраических терминах симплексный метод предполагает:

  • умение находить начальный опорный план;
  • наличие признака оптимальности опорного плана;
  • умение переходить к нехудшему опорному плану.
Пример решения задачи

Задача

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве , , , единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве  единиц, ресурса второго вида в количестве   единиц, ресурса третьего вида в количестве   единиц. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве  ,  единиц, ресурсов второго вида в количестве    единиц, ресурсов третьего вида в количестве   единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно    тыс. руб.

  • Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.
  • К прямой задаче планирования товарооборота, решаемой симплексным методом, составить двойственную задачу линейного программирования.
  • Установить сопряженные пары переменных прямой и двойственной задач.
  • Согласно сопряженным парам переменных из решения прямой задачи получить решение двойственной задачи, в которой производится оценка ресурсов, затраченных на продажу товаров.

  

Решение

Построение модели

Через  обозначим товарооборот 1-го, 2-го и третьего вида товаров соответственно.

На сайте можно заказать решение задач, контрольных, самостоятельных, домашних работ (возможно срочное решение). Для этого вам нужно только связаться со мной:

Телеграм @helptask
ВКонтакте (vk.com/task100)
WhatsApp +7 (968) 849-45-98

Мгновенная связь в любое время и на любом этапе заказа. Общение без посредников. Удобная и быстрая оплата переводом на карту. Опыт работы более 25 лет.

Подробное решение в электронном виде (docx, pdf) получите точно в срок или раньше.

Тогда целевая функция, выражающая получаемую прибыль:

Ограничения по материально-денежным ресурсам:

Кроме того, по смыслу задачи

Получаем следующую задачу линейного программирования:

Решение прямой задачи линейного программирования

Приведем задачу к каноническому виду. Для преобразования неравенств в равенства введем дополнительные переменные . Переменные  входят в ограничения с коэффициентом 1. В целевую функцию все дополнительные переменные введем с коэффициентом,  равным нулю.

Ограничение имеет предпочтительный вид, если при неотрицательности правой части левая часть имеет переменную, входящую с коэффициентом, равным единице, а остальные ограничения-равенства - с коэффициентом, равным нулю. В нашем случае 1-е, 2-е, 3-е ограничения имеют предпочтительный вид с соответствующими базисными переменными .

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

Заполняем симплексную таблицу 0-й итерации.

БП Симплексные
отношения
8 6 4 0 0 0
0 520 16 18 9 1 0 0 65/2
0 140 7 7 2 0 1 0 20
0 810 9 2 1 0 0 1 90
0 -8 -6 -4 0 0 0

Так как мы решаем задачу на максимум – наличие в индексной строке отрицательных чисел при решении задачи на максимум свидетельствует о том, что нами оптимальное решение не получено и что от таблицы 0-й итерации необходимо перейти к следующей.

Переход к следующей итерации осуществляем следующим образом:

Ведущий столбец соответствует .

Ключевая строка определяется по минимуму соотношений свободных членов и членов ведущего столбца (симплексных отношений):

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е.7.

Теперь приступаем к составлению 1-й итерации. Вместо единичного вектора  вводим вектор .

В новой таблице на месте разрешающего элемента пишем 1, все остальные элементы ключевого столбца –нули. Элементы ключевой строки делятся на разрешающий элемент. Все остальные элементы таблицы вычисляются по правилу прямоугольника.

Получаем таблицу 1-й итерации:

БП Симплексные
отношения
8 6 4 0 0 0
0 200 0 2 31/7 1 -16/7 0 1400/31
8 20 1 1 2/7 0 1/7 0 70
0 630 0 -7 -11/7 0 -9/7 1
160 0 2 -12/7 0 8/7 0  

Ключевой столбец для 1-й итерации соответствует .

Находим ключевую строку, для этого определяем:

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 31/7.

Вектор  выводим из базиса и вводим вектор .

Получаем таблицу 2-й итерации:

БП Симплексные
отношения
8 6 4 0 0 0
4 1400/31 0 14/31 1 7/31 -16/31 0  
8 220/31 1 27/31 0 -2/31 9/31 0  
0 21730/31 0 -195/31 0 11/31 -65/31 1  
7360/31 0 86/31 0 12/31 8/31 0  

В индексной строке все члены неотрицательные, поэтому получено следующее решение задачи линейного программирования (выписываем из столбца свободных членов):

Ответ

Таким образом, необходимо продавать 7,1 тыс.р. товара 1-го вида и 45,2 тыс.р. товара 3-го вида. Товар 2-го вида продавать невыгодно. При этом прибыль будет максимальна и составит 237,4 тыс.р. При реализации оптимального плана остаток ресурса 3-го вида составит 701 ед.

Построение двойственной задачи линейного программирования

Запишем модель двойственной задачи.

Транспонируем матрицу исходной задачи:

Получаем:

Решение двойственной задачи на основании решения исходной

Приведем задачу к каноническому виду. Введем дополнительные переменные. В целевую функцию все дополнительные переменные введем с коэффициентом,  равным нулю.  Дополнительные переменные прибавим  к левым частям ограничений, не имеющих предпочтительного вида, и получим равенства.

Соответствие между переменными исходной и двойственной задачи:

|

|

|

|

|

|

На основании симплексной таблицы получено следующее решение двойственной задачи линейного программирования (выписываем из нижней строки):

Ответ

Таким образом, наиболее дефицитным является ресурс первого вида. Его оценка максимальна и равна . Ресурс третьего вида является избыточным -его двойственная оценка равна нулю . Каждая дополнительно проданная единица товара 2-й группы будет снижать оптимальную прибыль на