Реферат: Линейное и динамическое программирование

Таблица N 2

C	B	H	48	30	29	10	0	0	0
			x1	x2	x3	x4	x5	x6	x7
0	х5	84	0	-½	31 /2	3	1	0	-3 /6
0	x6	20	0	11 /3	2 /3	2	0	1	-2 /6
48	х1	38	1	5 /6	1 /6	0	0	0	1 /6
1824	0	10	-21	-10	0	0	-8

Таблица N 3

C	B	H	48	30	29	10	0	0	0
			x1	x2	x3	x4	x5	x6	x7
29	х3	24	0	-1 /7	1	6 /7	2 /7	0	-1 /7
0	x6	4	0	13 /7	0	13 /7	-4 /21	1	-5 /21
48	х1	34	1	6 /7	0	-1 /7	-1 /21	0	4 /21
2328	0	7	0	8	6	0	5

Оптимальное решение (производственная программа): X_{о pt} =(34; 0; 22; 0); максимум целевой функции равен 2328.

Значение переменной с номером i большим 4-х есть остаток (i-4)-ro ресурса. 'Гак как все оценочные коэффициенты неотрицательны, то получено оптимальное решение: базисные переменные равны свободным членам, остальные равны 0.

Следует обратить внимание на экономический смысл элементов послед­ней строки последней симплексной таблицы. Например, коэффициент Δ₂ =7 при переменной х₂ показывает, что если произвести одну единицу продукции второго вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 7 единиц.

Заметим, что в рассматриваемом примере ли­нейной производственной задачи возможна самопроверка результата.

Воспользуемся тем, что в оптимальной производственной программе х₂ =0, х₄ =0. Предположим, что вторую и четвертую продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя перемен­ными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:

L(x₁ ,x₃ )=48x_l +29x₃ -max

3х₁ +4х₃ ≤198

2х₁ + х₃ ≤ 96

6х₁ + х₃ ≤228

x₁ ≥0, x₃ ≥0

Задачу линейного программирования с двумя переменными можно решить графически. Возьмем на плоскости систему координат: ось OX₃ направим горизонтально и вправо, ось OХ₁ -вертикально и вверх. Каждое ограничение задачи, раз оно линейное нестрогое неравенство, графически изображается полуплоскостью, граничная прямая которой соответствует уже не неравенству, а равенству. Допустимое множество задачи является пересечением всех этих полуплоскостей и есть выпуклый многоугольник. Вторая из двух основных теорем линейного программирования гласит: Если экстремум целевой функции достигается на допустимом множестве, то функция принимает его в какой-то вершине многоугольника-допустимого множества. Исходя из этой теоремы, найти искомый экстремум можно просто перебрав вершины многоугольника и определив ту, в которой значение функции экстремально. Чаще делают по-другому: строят линию уровня целевой функции и двигают ее параллельно в направлении экстремума, стараясь уловить последнюю точку пересечения линии с допустимым множеством.

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

Задача линейного оптимального планирования - исходная в своей паре симметричных двойственных задач. Вообще же другая задача в двойственной паре строится так:

1)меняется тип экстремума целевой функции (mах на min и наоборот);

2)коэффициенты целевой функции одной задачи становятся свободными членами другой задачи;

3)свободные члены одной задачи становятся коэффициентами целевой функции двойственной задачи;

4)тип неравенств меняется (≤ на ≥ и наоборот);

5) каждый столбец одной задачи порождает строку ограничений другой задачи и наоборот. В матрично-векторном виде обе задачи выглядят так:

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

L=(c,x)-max Z=(b,y)-min

Ax≤b, x≥0 Ya≥c, y≥0,

L(x₁ ,x₂ ,x₃ ,x₄ )=48x_l +30x₂ +29x₃ +10x₄ -max Z(y₁ ,y₂ ,y₃ ,y₄ )=198y_l +96y₂ +228y₃ - min

3х₁ +2х₂ +4х₃ +3х₄ ≤198 3y₁ +2y₂ +6y₃ ≥48

2х₁ +3х₂ +1х₃ +2х₄ ≤96 2y₁ +3y₂ +5y₃ ≥30

6х₁ +5х₂ +1х₃ +0х₄ ≤228 4y₁ + y₂ + y₃ ≥29

x_j ≥0, jєN₄ 3y₁ +2y₂ ≥10

y_j ≥0, jєN₃

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений X(x_1, x_2, x_3, x₄ ) и Y(y_1, y_2, y₃ ) пары двойственных задач необходимо и достаточно выполнение условий: