[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4]

Решение задачи.

Решить задачу о смесях, приведенную в разд. 1.2, с помощью двойственной.
Экономико-математическая модель задачи:
Z=4х₁ + 6х₂ ==> min
при ограничениях
3х₁+ х₂ >= 9,
х₁ + 2х₂ >= 8,
х₁ + 6х₂ >= 12,
Число ограничений m=3,
число переменных n=2.

Решение. Расширенная система задачи имеет вид:
3х₁ + х₂ - х₃ = 9,
х₁ + 2х₂ - х₄ = 8,
х₁ + 6х₂ - х₅ = 12,
Очевидно, что взяв в качестве базиса выравнивающие переменные, мы получим базисное решение X = (0,0,-9,-8,-12), недопустимое по всем основным переменным.
Решим вместо этой задачи двойственную
F = 9y₁ + 8y₂ + 12y₃ ==> max, при ограничениях
3y₁ + y₂ + y₃ + y₄ = 4,
y₁ + 2y₂ + 6y₃ + y₅ = 6,
Заполняем первую симплексную таблицу (табл.1), в которой переменные y₄, y₅ - основные. Последняя строка заполняется коэффициентами линейной функции с противоположным знаком.

Базис	Свободный член	Переменные					Оценочное отношение
		y1	y2	y3	y4	y5
y4	4	3	1	1	1	0	4/1
y5	6	1	2	6	0	1	6/6¬
F	0	-9	-8	-12	0	0

Базис	Свободный член	Переменные					Оценочное отношение
		y1	y2	y3	y4	y5
y4	3	17/6	2/3	0	1	-1/6	18/17¬
y3	1	1/6	1/3	1	0	1/6	6/1
F	12	-7	-4	0	0	2

Базис	Свободный член	Переменные					Оценочное отношение
		y1	y2	y3	y4	y5
y1	18/17	1	4/17	0	6/17	-1/17	9/2
y3	14/17	0	5/17	1	-1/17	3/17	14/5¬
F	330/17	0	-40/17	0	42/17	27/17

Базис	Свободный член	Переменные
		y1	y2	y3	y4	y5
y1	2/5	1	0
y2	14/5	0	1	17/5	-1/5	3/5
F	26	0	0	8	2	3	max

Критерий оптимальности выполнен, значит Zmin = Fmax =26,
оптимальное базисное решение двойственной задачи (2/5; 14/5; 0; 0; 0)
оптимальное базисное решение исходной задачи (2; 3; 0; 0; 8) получаем по таблице соответствия коэффициентов.
Для первоначальных переменных x_j ↔ y_m+j
т.е. x₁ ↔ y₃₊₁
x₂ ↔ y₃₊₂

Для выравнивающих переменных x_n+i ↔ y_i
т.е. x₂₊₁ ↔ y₁
x₂₊₂ ↔ y₂
x₂₊₃ ↔ y₃

Полученное решение совпадает с ранее полученным графиеским методом.

[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4]

[В начало страницы]