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

Лекция 4. Симплекс метод. Двойственные задачи.

Симплекс-метод – это специальный метод оптимального (направленного) перебора, используемый при решении задач линейного программирования. Симплекс-метод обеспечивает сходимость к экстремальной точке за конечное число шагов, так как он предусматривает последовательный оптимальный просмотр вершин многогранника, число которых конечно, и является оптимальной процедурой отыскания экстремума.

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

Известно, что если решение задачи линейного программирования существует, то оно достигается в одной из вершин многогранника решений.

Симплекс-метод позволяет найти крайнюю точку области многогранника решений n и определить является ли эта точка точкой типа x^*. Если найденная точка не является искомой, то метод обеспечивает переход в другую точку с уменьшением (увеличением) значения целевой функции . Через конечное число подобных точек точка x^* либо находится, либо признаётся несуществующей.

Симплексный метод универсален, хотя и требует стандартную постановку задачи:

Табличный алгоритм симплекс метода

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

Изделия , и могут производиться в любых соотношениях (сбыт обеспечен), накладываются ограничения по количеству сырья каждого вида.

Требуется составить такой план производства изделий, при котором общая стоимость всей произведённой предприятием продукции является максимальной. Составим математическую модель.

Обозначим искомый выпуск изделий через , B через , через .

Целевая функция имеет вид:

. (1)

В общем виде целевая функция принимает вид:

(1’)

Ограничения записываются так

. (2)

Или в общем виде, так

, (2’)

где . (3)

Запишем эту задачу в форме основной задачи линейного программирования (ОЗЛП). Для этого перейдём от ограничений неравенств к ограничением равенствам:

(4)

В общем виде ограничения виде равенств записываются так:

. (4’)

Преобразуем систему (4) к векторной форме.

. (5)

; ; ; ;

; ; .

Запишем опорный план (базисное решение).

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

Составим симплексную таблицу для 1-ой итерации. Для этого по приведённым ниже формулам найдём следующие значения и запишем их в симплекс таблицу.

Сначала положим, что предприятие вообще не выпускает изделий, и поэтому целевая функция принимает нулевое значение, то есть

, где

— начальные значения коэффициентов в целевой функции.

Далее найдём начальные частичные суммы целевой функции .

Табл. 1. Симплекс таблица для 1-ой итерации.

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

Эти значения переменных отвечают такому «плану», при котором ничего не производится, сырьё не используется и значение целевой функции равно нулю. (то есть стоимость произведённой продукции отсутствует). Естественно, такой план не является оптимальным.

Это видно из 4-йстроки табл. 1 так как в ней имеются три отрицательных числа Напомним, что условие оптимальности указывает на то, что в последней строке не должно быть отрицательных чисел. Эти отрицательные числа не только свидетельствуют о возможности увеличения общей стоимости производимой продукции, но и показывают, на сколько увеличится эта сумма при введении в план единицы того или другого вида продукции. Так число означает, что при включении в план производства одного изделия обеспечивается увеличение выпуска продукции на руб. Поэтому с экономической точек зрения наиболее целесообразным является включение в план производства изделий . Это же и необходимо сделать и на основании формального признака симплексного метода, поскольку максимальное по абсолютной величине отрицательное число стоит в 4-й строке столбца . Следовательно, в базис введём вектор .

Определяем вектор, подлежащий исключению из базиса. Для этого находим для , то есть . Найдя число , мы тем самым с экономической точки зрения определили, какое количество изделий предприятие может изготовлять с учётом норм расхода и имеющихся объёмов сырья каждого вида. Так как сырья данного вида соответственно имеется 360, 192 и 180 кг, а на одно изделие требуется затратить сырья каждого вида соответственно 12, 8 и 3 кг, то максимальное число изделий , которое может быть изготовлено предприятием, равно , то есть ограничивающим фактором для производства изделий является имеющийся объём сырья II вида. С учётом его наличия предприятие может изготовить 24 изделия . При этом сырьё II вида будет полностью использовано. Следовательно, вектор подлежит исключению из базиса. Столбец вектора и вторая 2-я являются направляющими. Составим таблицу для второй итерации.

Сначала заполним строку вектора, вновь введённого в базис, т.е. строку, номер которой совпадает с номером направляющей строки. Здесь направляющей строкой является вторая строка. Элементы этой строки получаются из соответствующих элементов табл. 1 делением их на разрешающий элемент (т.е. на 8).

Табл. 2.Симплекс таблица для второй итерации.

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

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

Число, стоящее на месте этого элемента в предыдущей таблице. В нашем случае это число, стоящее в табл. 1 на пересечении столбца вектора и 1-й строки (360);

Число, стоящее в той же строке что и отыскиваемый элемент и в столбце вектора вводимого в базис из предыдущей симплекс таблицы. В нашем случае это число, стоящее в табл. 1 на пересечении столбца вектора и 1-й строки (12);

Число в строке введённого в базис вектора и в столбце отыскиваемого элемента в текущей симплекс таблице. В нашем случае это число, стоящее в табл. 2 на пересечении столбца вектора и 2-й строки (24).

Вычитая из первого числа произведение двух других, находим искомый элемент: ; записываем его в 1-й строке столбца вектора табл. 2. Аналогичным образом находим и все остальные элементы:

;

; ;

; .

По окончании расчёта всех элементов табл. 2 в ней получены новый опорный план и коэффициенты разложения векторов ( ) через базисные векторы , , и значения и . Как видно из этой таблицы, новым опорным планом задачи является план . При данном плане производства изготовлены 24 изделия и остаётся неиспользованным 72 кг сырья I вида и 108 кг сырья III вида. Стоимость всей производимой при этом плане продукции равна 384 руб. Указанные числа записаны в столбце вектора табл. 2. Как видно, данные этого столбца по-прежнему представляют собой параметры рассматриваемой задачи, хотя они значительные изменения. Изменились данные и других столбцов, а их экономическое содержание стало более сложным. Так, например, возьмём два столбца вектора . Число во 2-й строке этого столбца показывает, на сколько следует уменьшить изготовление изделий , если запланировать выпуск одного изделия . Числа 9 и в 1-й и 3-й строках вектора показывают соответственно, сколько потребуется сырья I и II вида при включении в план производства одного изделия , то это обеспечит увеличение выпуска продукции в выражении стоимости на 2 руб. Другими словами, если включить в план производства продукции одно изделие , то это потребует уменьшения выпуска изделия на ед. и потребует дополнительных затрат 9 кг сырья I вида и кг сырья III вида, а общая стоимость изготовляемой продукции в соответствии с новым оптимальным планом возрастёт на 2 руб. Таким образом, числа 9 и выступают как бы новыми «нормами» затрат сырья I и III вида на изготовление одного изделия (как видно из табл. 1, ранее они были равны 15 и 3), что объясняется уменьшением выпуска изделий .

Такой же экономический смысл имеют и данные столбца вектора табл. 2. Несколько иное экономическое содержание имеют, числа записанные в столбце вектора . Число во 2-й строке этого столбца, показывает, что увеличении объёмов сырья II вида на 1 кг позволило бы увеличить выпуск изделий на ед. Одновременно потребовалось бы дополнительно кг сырья I вида и кг сырья III вида. Увеличение выпуска изделий на ед. приведет к росту выпуска продукции на 2 руб.

Из изложенного выше экономического содержания данных табл. 2 следует, что найденный на II итерации план задачи не является оптимальным. Это видно и из 4-й строки табл. 2, поскольку в столбце вектора этой строки стоит отрицательное число . Значит, в базис следует ввести вектор , то есть в новом плане следует предусмотреть выпуск изделий . При определении возможного числа изготовления изделий следует учитывать имеющиеся количество сырья каждого вида, а именно: возможный выпуск изделий определяется для , то есть находим

Следовательно, исключению из базиса подлежит вектор , иными словами, выпуск изделий ограничен имеющимися в распоряжении предприятия сырьём I вида. С учётом имеющихся объёмов этого сырья предприятию следует изготовить 8 изделий . Число 9 является разрешающим элементом, а столбец вектора и 1-я строка табл. 2 являются направляющими.

Составляем таблицу для III итерации.

Табл. 3.Симплекс таблица для третей итерации.

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

Затем заполняем элементы столбцов векторов базиса и по правилу треугольника вычисляем элементы остальных столбцов.

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

Проверяем является ли данный опорный план оптимальным или нет. Для этого рассмотрим 4-ю строку табл. 3. В этой строке среди чисел нет отрицательных. Это означает, что найденный опорный план является оптимальным и . Следовательно, план выпуска продукции, включающий изготовление 8 изделий и 20 изделий , является оптимальным. При данном плане выпуска изделий полностью используется сырьё I и II вида и остаётся неиспользованным 96 кг сырья III вида, а стоимость производимой продукции равна 400 руб.

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

Недостатки симплекс метода.

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

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

С каждой задачей линейного программирования (ЗЛП), называемой прямой или исходной, тесно связана другая ЗЛП, называемая двойственной. При этом указанные задачи будут образовывать пару взаимно двойственных задач. Решая одну из них, можно найти решение и второй задачи.

Пара двойственных ЗЛП в симметричной форме имеет следующий вид:

прямая задача

двойственная задача

Рассмотренная пара взаимно двойственных задач может быть экономически интерпретирована, например, так.

Прямая задача: сколько продукции j-го вида надо произвести, чтобы при заданных стоимостях единицы продукции , объемах имеющихся ресурсов и нормах расходов максимизировать выпуск продукции в стоимостном выражении?

Двойственная задача: какова должна быть оценка единицы каждого из ресурсов , чтобы при заданных стоимостях единицы продукции , объемах имеющихся ресурсов и нормах расходов минимизировать общую оценку затрат на все ресурсы?

Чтобы из решения прямой задачи получить решение двойственной задачи нужно записать обе задачи в канонической форме:

прямая задача

двойственная задача

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

Если в оптимальном плане прямой задачи переменная равна нулю, то соответствующая ей переменная двойственной задачи отлична от нуля. Значения целевых функций двойственных задач совпадают, т.е. .

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

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

Если прямая задача не имеет решения, то и двойственная ей тоже не имеет решения.

Пример 1.

Составить задачу, двойственную к ЗЛП, рассмотренной в примере 1.3. Дать экономическую интерпретацию прямой и двойственной задач. Из решения прямой задачи (пример 1.6) найти решение двойственной задачи.

Решение

прямая задача

;

двойственная задача

;

Экономическая интерпретация.

Прямая задача: сколько единиц продукции П_j надо произвести, чтобы при заданной прибыли от единицы продукции, объемах имеющихся ресурсов и нормах расходов максимизировать прибыль от всей выпущенной продукции?

Двойственная задача: какова должна быть оценка единицы каждого из ресурсов , чтобы при заданной прибыли от единицы продукции, объемах имеющихся ресурсов и нормах расходов минимизировать общую оценку затрат на все ресурсы?

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

Для нахождения решения двойственной задачи запишем обе задачи в канонической форме:

прямая задача

;

двойственная задача

;

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

Определим из канонической формы прямой задачи, какие переменные равны нулю в оптимальном плане и из приведенного соответствия определим отличные от нуля двойственные переменные. Так

Для нахождения отличных от нуля двойственных переменных и решим систему уравнений, полученную из системы ограничений канонической формы двойственной задачи:

Откуда . Таким образом, , или для двойственной задачи в симметричной форме . Причем .

Оценки единицы каждого из ресурсов определяют дефицитность используемых ресурсов и показывают, насколько увеличится целевая функция при увеличении соответствующего ресурса на единицу.

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

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

1) Если прямая задача на максимум, то двойственная к ней – на минимум, и наоборот.

2) Если прямая (двойственная) задача на максимум, то ограничения-неравенства системы представляются в виде неравенств типа , если на минимум, то ограничения-неравенства системы представляются в виде неравенств типа .

3) Каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот, каждому ограничению двойственной задачи соответствует переменная прямой задачи, следовательно, число ограничений прямой задачи равно числу переменных двойственной, а число ограничений двойственной – числу переменных прямой.

4) Матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием.

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

6) Если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение-неравенство, если же нет, то как ограничение-равенство.

7) Если какое-либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не налагается.

Пример 2

Составить задачу, двойственную к ЗЛП:

;

Решение

Воспользовавшись правилами построения двойственной задачи, получим следующую пару двойственных ЗЛП:

прямая задача

;

двойственная задача

;

Пример 3

Составить задачу, двойственную к ЗЛП, рассмотренной в примере 1.8 (на максимум). Из решения прямой задачи (пример 1.8) найти решение двойственной задачи.

Решение

Исходная ЗЛП:

Построим пару двойственных ЗЛП:

прямая задача

двойственная задача

;

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

Для нахождения решения двойственной задачи запишем обе задачи в канонической форме, без учета неотрицательности исходных переменных и добавляя во все ограничения неотрицательные переменные. Если переменная добавляется в ограничение-равенство, то она равна нулю:

прямая задача