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

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

Найти максимум целевой функции:

(3.9)

при ограничениях:

, (3.10)

; ; (3.11)

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

, (3.12)

при ограничениях:

, , (3.13)

, .

Число переменных в системах (3.10) и (3.13) одинаково и равно n + m.

Базисными переменными в исходной модели будут , а в двойственной – переменные .

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

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

Представим модели в виде симплексных таблиц. Таблица для исходной модели имеет вид:

Таблица 3.1

БП		СП
…
=		…
…	…	. . .
=		…
		…

Таблица для двойственной модели:

Таблица 3.2

Б.П.	А	СП
y … y
=		…
…	…	. . .
=		…
F		…

Положив свободные переменные , найдем значения базисных переменных , …, (табл. 3.1). Если положить переменные то получим , …, (табл. 3.2). Учитывая соответствие между переменными, при решении одной из двойственных моделей, получаем решение другой. Получить решение двойственной модели можно из последней симплексной таблицы прямой модели. Если прямая модель решается на максимум, то оптимальное решение двойственной модели соответствует оценкам индексной строки в последней симплексной таблице прямой модели: .

Если прямая модель решается на минимум, то оптимальное решение двойственной модели равно компонентам индексной строки в последней симплексной таблице, взятыми с противоположными знаками, т.е. .

Пример 3.2. На предприятии имеется 4 вида сырья в количествах = 18, = 16, = 8, = 6 единиц, из которых выпускаются 3 продукта П , П , П . Нормы затрат и прибыли от реализации каждого вида продукции приведены в таблице 3.3.

Таблица 3.3

Сырье	Продукты	Объем сырья
П	П	П
Прибыль				max

Составить план производства трех видов продукции, при котором доход был бы максимальным. Найти двойственные оценки.

Решение. Пусть – количество -го вида продукции, = 1, 2, 3. Математическая модель задачи имеет вид: требуется найти план производства продукции , при котором функция прибыли и который удовлетворяет системе ограничений по запасам сырья:

Сформулируем двойственную модель. Пусть , – оценки единицы сырья . Определим оценки сырья , при которых функция стоимости сырья и которые удовлетворяют системе ограничений:

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

В целевую функцию дополнительные переменные вводятся с коэффициентами равными нулю = 0, i = : = = = = 0.

Составляем симплексную таблицу № 1 (таблица 3.4):

Таблица 3.4

БП		СП
-	-	-
-строка		–3	–4	–2

Строка функции цели заполняется компонентами, вычисляемыми по формулам:

Наименьшей компонентой индексной строки является «–4». Поэтому разрешающим столбцом является третий столбец. Находим симплексные отношения: 18/2 = 9, 16/1 = 16, 8/1 = 8, 6/1 = 6. Среди них наименьшее равно 6. Следовательно, разрешающей строкой является четвертая строка.

Составляем новую симплексную таблицу № 2 (таблица 3.5).

Таблица 3.5

БП		СП
-	-	-
			–2	–1
			–1
			–1	–1
		–3

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

Находим симплексные отношения: 6/1 = 6, 10/2 = 5, 2/1 = 2. Наименьшее – «2», поэтому разрешающей строкой будет третья строка.

Составляем новую симплексную таблицу № 3 (таблица 3.6):

Таблица 3.6

БП		СП
-	-	-
		–1	–1
		–2		│2│
			–1	–1
				–1

Так как в Z-строке есть отрицательный элемент, то применяем еще раз симплекс-метод. Составляем симплексные отношения: 6/1 = 6, 6/2 = 3. Выбираем в качестве разрешающей - вторую строку.

Составляем симплексную таблицу № 4 (таблица 3.7):

Таблица 3.7

БП		СП
-	-	-
		–1	–1
		–1	1/2	1/2
			–1/2	1/2
			1/2	–1/2
			3/2	1/2

Все элементы индексной строки положительные. Следовательно, построенный опорный план оптимальный. Приравняв свободные переменные нулю, , получим: = (5, 3, 3, 4, 0, 0, 0) и

= 33.

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

После решения и введения новых переменных в базис, получим:

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

= (0, , 2, , 0, 0, 0)

Оценка для сырья равна нулю, так как сырье используется не полностью. Для сырья , , оценки положительны, что указывает на полное использование сырья. Значение целевой функции:

= 18 · 0 + 16 · + 8 · 2 + 6 · = 33.

Система ограничений двойственной задачи при подстановке оптимальных значений выполняется:

0 + 2 · + 2 = 3; 2 · 0 + + 2 + = 4; 0 + + = 2.

Пример 3.3.Прутки стального проката длиной 600 см, согласно заявкам потребителей, нужно раскраивать на заготовки трех видов с длиной соответственно см, см и см для производства 45 изделий. На каждое изделие требуется по 3 заготовки длиной , 4 заготовки длиной и 5 заготовок длиной . Определить, какое количество прутков нужно разрезать для изготовления 45 изделий, чтобы отходы были минимальными.

Решение. Прежде всего, построим таблицу 3.8 возможных вариантов раскроя.

Таблица 3.8

Способ раскроя	Количество заготовок	Остаток
=250	=200	=150
I II III IV V VI

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

.

Аналогично составляются условия по заготовкам и :

Количество раскраиваемых прутков не может быть отрицательным, т. е.

Целевая функция, выражающая суммарную величину остатков, составляется с использованием величин остатков по каждому из способов раскроя (см. 5 столбец табл. 2.8):

.

Эта сумма должна быть минимальной. Таким образом, математическая модель задачи построена:

требуется найти план количества раскраиваемых прутков , при котором целевая функция и который удовлетворяет ограничениям: ,

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

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

Таблица 3.9

0=
0=
0=
=		-100		-50	-50	-100

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

Таблица 3.10

=	67,5	0,5	0,5
0=
0=
=	6 750			-50	-100

На втором шаге выбираем разрешающим столбцом четвертый столбец. Этот столбец также исключим из следующей таблицы. Так как

min (180:1=180; 225:2=112,5)=180, то разрешающей строкой будет третья строка. Выполнив преобразования, получим следующую таблицу 3.11.

Таблица 3.11

=	67,5	0,5	0,5
0=	67,5	0,5	-1,5	1,5	-2
=	112,5	0,5	1,5	0,5
=	18 000

На третьем шаге выбираем разрешающим столбцом третий столбец. Так как min (67,5:1,5=45; 112,5:0,5=225)=45, то разрешающей строкой будет вторая строка. Выполнив преобразования, получим следующую таблицу 3.12.

Таблица 3.12

БП		СП
=	67,5	0,5	0,5
=			-1
=
=	18 000

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

Таблица 3.13

БП		СП
=	67,5		0,5
=	87,5	0,5		0,5
=	33,75
=	11 250			-75

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

Таблица 3.14

БП		СП
=
=
=	16,875
=	543,75	-150	-37,5	-37,5

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

↕ ↕ ↕ ↕ ↕ ↕

После решения и введения новых переменных в базис, получим:

Из последней симплексной таблицы находим значения двойственных оценок при условии, что свободные переменные равны нулю, т. е. : =150, = 37,5, = 37,5. Оптимальный план двойственной модели будет иметь вид: .