Двойственные оценки как инструмент определения эффективности отдельных вариантов

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

Столбец симплексной  таблицы с этим номером на данной итерации называется генеральным столбцом.

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

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

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

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

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

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

Пример решения оптимизационных  задач линейного программирования симплексным методом

Пусть необходимо найти  оптимальный план производства двух видов продукции (х₁ и х₂).

Исходные данные:

 

Вид продукции	Норма расхода ресурса на единицу прибыли		Прибыль на единицу изделия
	А	В
1	5	8	7
2	20	4	3
Объем ресурса	20	36

 

Построим оптимизационную  модель

 

 – ограничение по ресурсу А;

 – ограничение по ресурсу  В.

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

 

 

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

 

x₃=20 и x₄=36

 

Базисные переменные	Свободные члены (план)	x1	x2	x3	x4
x3	20	5	2	1	0
x4	36	8	4	0	1
Fj – Cj		7	3	0	0

 

1-я итерация. Находим генеральный столбец и генеральную строку:

 

max (7,3) = 7

 

Генеральный элемент  равняется 5.

 

Базисные переменные	Свободные члены (план)	x1	x2	x3	x4
x1	4	1	0.4	0.2	0
x4	4	0	0.8	-1.6	1
Fj – Cj	28	0	0.2	-1.4	0

 

2-я итерация. Найденное базисное решение не является оптимальным, т.к. cтрока оценок (F_j-C_j) содержит один положительный элемент. Находим генеральный столбец и генеральную строку:

 

max (0,0.3,-1.4,0) = 0.2

 

Базисные переменные	Свободные члены (план)	x1	x2	x3	x4
x1	2	1	0	1	-0.5
x2	5	0	1	-2	1.25
Fj – Cj	29	0	0	-1	-0.25

 

Найденное решение оптимально, так как все специальные оценки целевой функции F_{j –} C_j равны нулю или отрицательны. F(x)=29 x₁=2; x₂=5.

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

Пусть предприятие (например, мебельная фабрика) производит столы  и стулья. Расход ресурсов на их производство и прибыль от их реализации представлены ниже:

 

	СТОЛЫ	СТУЛЬЯ	ОБЪЕМ РЕСУРСОВ
Расход  древесины на изделие, м3	0,5	0,04	200
Расход  труда, чел-час	12	0,6	1800
Прибыль от реализации единицы изделия, руб.	180	20

 

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

Пусть x₁ – количество столов;

х₂ – количество стульев.

Тогда система ограничений  и целевая функция запишутся  следующим образом:

180x₁ + 20х₂ max (целевая функция );

0.5x₁ + 0.04х₂ 200 (ограничения по древесине);

12x₁ + 0.6х₂ 1800 (ограничения по труду);

x₁ 80 (контракт с муниципалитетом);

x₁ 0; х₂ 0;

x₁, х_{2 –} целые числа.

Для решения задачи в  Excel запишем ее виде, представленном на рис. 3.4.

 

Рис. 3.4. Запись исходных данных для решения задачи линейной оптимизации

 

Для решения задачи вызовем  меню Сервис-Поиск решения (Tools-Solver).

В открывшемся диалоговом окне Поиск решения (рис. 3.5.) укажем:

адрес целевой ячейки (в нашем примере D5);

диапазон искомых  ячеек (А2:A3);

ограничения: А2>=80

 

A2:A3=целое

A2:A3>=0

В2<=D2

B3<=D3 .

 

Добавления, изменения  и удаления ограничений производятся с помощью кнопок Добавить, Изменить, Удалить (Add, Change, Delete).

Для нахождения оптимального решения нажмем кнопку Выполнить (Solve). В результате в таблице получим значение целевой функции – 42400 млн руб. при x₁ = 80 и x₂ = 1400.

 

Рис. 3.5. Диалоговое окно Поиск решения

 

Диалоговое окно Результаты поиска решения позволяет (рис. 3.6.):

· сохранить на текущем рабочем листе найденное оптимальное решение;

· восстановить первоначальные значения;

· сохранить сценарий;

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

 

Рис.3.6. Рабочий лист с  найденным оптимальным решением

 

Рис. 3.7. Диалоговое окно Результаты поиска решения

 

Если щелкнуть по кнопке ОК, то на месте исходной таблицы получим таблицу с найденными оптимальными значениями (см. рис. 3.7).

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

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

Двойственная задача линейного  программирования может быть сформулирована следующим образом:

Найти переменные y_i (i=1,2,...m), при которых целевая функция была бы минимальной

 

,

 

не нарушая ограничений

 

 

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

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

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

 

F(x)=Z(y) или .

 

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

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

 

 

Следствие1. Пусть оптимальное значение некоторой переменной двойственной задачи строго положительно

 

 .

 

Тогда из условия (1) получим:

 

или

 

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

Следствие2. Пусть для оптимального значения некоторой переменной x_i прямой задачи выполняется условие строгого неравенства

 

.

 

Тогда основываясь на том же первом условии (1) можно заключить, что y_i=0.

Экономически это  означает, что если в оптимальном  плане какой-то ресурс используется не полностью, то его объективно обусловленная  оценка обязательно равна нулю.

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

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

 

 

В системе неравенств должны быть однотипные знаки «меньше  или равно». Поэтому неравенство  умножим на – 1 и поменяем знак неравенства на противоположный.

 

 

Ограничение на целочисленность переменных здесь не требуется.

Решение прямой задачи дало следующие результаты:

 

Х₁=80; Х₂=1400; F(x)=42400.

 

В результате решения  двойственной задачи получим

 

Y₁=0; Y₂=33.3; Y₃=220; Z(y)=42400.

 

Объективно обусловленная  оценка Y₁=0 указывает на то, что у нас избыток древесины. Y₂=33.3, т.е. больше нуля. Это говорит о том, что этот ресурс (труд) полностью используется в оптимальном плане. Значение целевой функции Z(y)= F(x)=42400. Это свидетельствует о том, что найденное решение оптимально.

Свойства объективно обусловленных оценок и их анализ.

Анализ задачи с использованием объективно обусловленных оценок показывает, что первый ресурс (древесина) используется не полностью. Можно убедиться, что  для найденного оптимального плана  достаточно 96 куб. м древесины, а 104 куб. м избыточны. Изменение ограничения  по древесине с 200 до 96 куб. м не повлияет на оптимальный план. Следовательно, объективно обусловленные оценки является устойчивыми в некоторых пределах изменения исходных условий задачи.

Объективно обусловленные  оценки выступают, как мера дефицитности ресурсов. Древесина, объективно обусловленная  оценка которой у нас равна нулю, не дефицитна, а трудовые ресурсы с объективно обусловленной оценкой, равной в нашей задаче 33.3, дефицитны и используются полностью.

Объективно обусловленные  оценки выступают как мера влияния  ограничений на целевую функцию  при приращении данного ресурса  на единицу. Так, например, уменьшение задания по производству столов с 80 до 79 увеличивает целевую функцию  на 220 руб., а увеличение трудовых ресурсов с 1800 до 1801 чел. час. увеличивает целевую функцию (если снять условие целочисленности) на 33.3 руб.

Объективно обусловленные  оценки выступают как меры взаимозаменяемости резервов (ограничений). Так, например, если увеличить задание по производству столов на единицу, то для того чтобы  целевая функция осталась прежней, нужно добавить 6.6 чел.-чис. (220/33.3). В этом случае х₁ будет равен 81, х₂ =1391, а значение целевой функции составит 42400.

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

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