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

Рассмотрим следующую задачу. Предприятие планирует выпускать 3 вида продукции – П₁, П₂, П₃. Для этого оно располагает объемами ресурсов 3-х видов Р₁, Р₂, Р₃. Затраты каждого ресурса на изготовление единицы продукции и цена единицы продукции приведены в таблице:

Пj Рi	П1	П2	П3	Объем
Р1
Р2
Р3
Цена

Требуется:

1) построить модель исходной и двойственной задач;

2) решить исходную задачу симплексным методом;

3) найти оптимальное решение двойственной задачи, используя проверочную строку последней симплексной таблицы;

4) дать экономический анализ основным и дополнительным переменным оптимальных решений обеих задач;

5) в ответе записать оптимальные решения обеих задач и значения их целевых функций; указать наиболее дефицитный ресурс и наиболее убыточный вид продукции.

Решение. 1. Построим модель исходной задачи

, .

Здесь х₁, х ₂, х₃ – план выпуска продукции.

Составим математическую модель двойственной задачи:

, .

2. Решим исходную задачу симплексным методом.

Запишем ее канонический вид:

, .

х₄, х₅, х₆ – дополнительные и они же базисные переменные. Начальный опорный план (0; 0; 0; 180; 210; 244).

Базис		В
		–10	–14	–12				таб. 1

Базис		В
					0,5	0,5
					0,5	–0,5
			–3			–1
				–5				таб. 2
			2,375			0,625		–0,125
			1,375			0,125		–0,625
			–0,75			–0,25		0,25
		14,25			5,75		1,25	таб. 3

Так как все оценки , то получен оптимальный план:

= (0; 82; 16; 0; 80; 0); = 1340.

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

основные переменные	дополнительные переменные
дополнительные переменные	основные переменные

Откуда: 5,75; 0; 1,25; 14,25; 0; 0.

= (5,75; 0; 1,25; 14,25; 0; 0); 1340.

Таким образом получили = 1340.

4. Проанализируем основные и дополнительные переменные оптимальных решений обеих задач. Основные переменные исходной задачи – это планируемый выпуск продукции.

Продукцию І-го вида к выпуску не планируют, ІІ-го вида – в количестве 82 ед. и ІІІ-го вида – в количестве 16 ед.

Дополнительные переменные исходной задачи показывают остатки сырья.

Сырье І и ІІІ видов израсходовано полностью. А сырье ІІ вида осталось в количестве 80 ед.

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

Таким образом, сырье І и ІІІ видов дефицитное, причем наиболее дефицитное сырье І-го вида. Сырье ІІ вида недефицитное.

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

По этому соотношению видно, что продукция І вида нерентабельна, а ІІ и ІІІ – рентабельна.

Ответ: = (0; 82; 16; 0; 80; 0); = 1340;

= (5,75; 0; 1,25; 14,25; 0; 0); 1340

Наиболее дефицитное сырье І вида. Наиболее убыточный І вид продукции.

Задания для самостоятельной работы.

Для производства четырех видов продукции (П₁, П₂, П₃, П₄) используются три вида ресурсов. Норма затрат ресурсов, использованных для выпуска единицы продукции каждого вида, цена единицы продукции и запасы ресурсов приведены в таблице.

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

Ресурсы Продукция	Затраты ресурсов на единицу продукции	Объем ресурсов
П1	П2	П3	П4
Р1
Р2
Р3
Цена единицы

Транспортная задача (ТЗ)

Транспортная задача возникает при планировании рациональных перевозок грузов. Математическая модель транспортной задачи в простейшем случае имеет вид:

max (1)

(2)

, , (3)

Здесь: – запасы поставщиков;

– спрос потребителей;

– тарифы, т.е. стоимости перевозки единицы груза от -го поставщика к -му потребителю;

Z – транспортные расходы;

- количество продукта, перевозимого от -го поставщика к -му потребителю.

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

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

Любая транспортная задача имеет допустимое решение (матрицу перевозок ), если

(4)

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

Допустимое решение транспортной задачи часто называют планом перевозок.

Построение начального опорного плана. Его вырожденность или невырожденность. Ранг матрицы системы.