Быстрый поиск

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

Решение одной из пары двойственных задач можно найти, зная только ответ к другой задаче и пользуясь 2-й теоремой двойственности: если i-e ограничение одной из пары двойственных задач на компонентах оптимального решения есть строгое неравенство, то оптимальное значение i-й переменной другой задачи равно 0, или, что то же самое - если оптимальное значение j-й переменной одной задачи строго положительно, то j-e ограничение другой из пары двойственных задач на компонентах оптимального решения есть равенство.

Важен экономический смысл двойственных оценок. Двойственная оценка, например, третьего ресурса у3=5 показывает, что добавление одной единицы третьего ресурса обеспечит прирост прибыли на 5 единиц.

Расшивка "узких мест" производства

Таблица N 3

C	B	H	48	30	29	10	0	0	0
C	B	H	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

При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, тем самым они образуют "узкие места" производства. Будем их заказывать дополнительно. Пусть Т=( t1,t2,t3) - вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие H+Q-lТ≥0, где Н - значения базисных переменных в последней симплексной таблице, а Q-1 - обращенный базис, который образуют столбцы при балансовых переменных в этой таблице. Задача состоит в том, чтобы найти вектор Т, максимизирующий суммарный прирост прибыли W=6t1+5 t3 при условии сохранения двойственных оценок ресурсов (и, следовательно, ассортимента выпускаемой продукции), предполагая, что можно получить дополнительно не более 1/3 первоначального объема ресурсов каждого вида.

24 2/7 0 -1/7 t1 0

4 + -4/21 1 -5/21 0 ≥ 0

34 -1/21 0 4/21 t3 0

t1 198

0 ≤ 1/3 96

t3 228

t1≥0, t3≥0.

W=6t1+5t3 àmax

-2/7 t1 + 1/7 t3 ≤ 24

4/21 t1 + 5/21 t3 ≤ 4

1/21 t1 - 4/21 t3 ≤ 34

t1≤198/3, t3≤228/3.

t1≥0, t3≥0.

Как видно, после графического решения (График 2) программа расшивки приобретает вид:

t1=21, t2=0, t3=0

С новым количеством ресурсов: 198+21 219

b' = 96+0 = 96

228+0 228

у предприятия будет новая производственная программа.

Найдем h'=Q-1 b'

5/28 0 -1/7 219 30 àx3

-4/7 1 -1/7 96 = 0 àx6

-3/28 0 2/7 228 33 àx1

Теперь новая производственная программа имеет вид: X'оpt=(33;0;30;0). При этом второй ресурс был использован полностью.

219

При наличии ресурсов b' = 96 производство наиболее выгодно, так как

228

достигается max прибыль с использованием всех ресурсов. Также обратим внимание на то, что производство продукции 1–го вида при заказе дополнительных ресурсов необходимо будет уменьшить на 15 единиц, а производство продукции 3–го вида – увеличить на единицу.

ΔLmax=(Y,t)=6·21=126, где Y=(6;0;5); t(21;0;0)

L'max= ΔLmax+ Lmax=126+2328=2454.

Этот результат можно проверить, подставив значения х1 и х3 в первоначальную целевую функцию: L'max=48xl+30x2+29x3+10x4=31·37+41·21=1147+861=2454.

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

Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в т пунктах производства (хранения) в количествах a1, а2,..., аm единиц, необходимо распределить между п пунктами потребления, которым необходимо соответственно b1, b2,,…, bn единиц. Стоимость перевозки единицы продукта из i-ro пункта отправления в j-й пункт назначения равна cij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.

Обозначим через xij количество груза, планируемого к перевозке от i-ro поставщика j-му потребителю. При наличии баланса производства и потребления

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

найти план перевозок

X=(xij), xij³0, iÎNm, jÎNn

минимизирующий общую стоимость всех перевозок

при условии, что из любого пункта производства вывозится весь продукт

, iÎNm

и любому потребителю доставляется необходимое количество груза

, jÎNn

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

А(а1,а2,а3)=(40;45;70); В(b1,b2,b3)=(48;30;29;40); 3 6 4 3

С= 2 3 1 3

6 5 1 4

Общий объем производства Sai=40+45+70=155 больше, чем требуется всем потребителям Sbj=48+30+29+40=147, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 155-147=8 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

Первое базисное допустимое решение легко построить по правилу "северо-западного угла".

Таблица 1

Потребл Произв	b1=48	b2=30	b3=29	b4=40	b5=8
a1=40	40 3	6	4	* 3	0	p1=0
a2=45	8 2	30 3	7 1	3	0	p2=-1
a3=70	6	5	22 1	40 4	8 0	p3=-1
	q1=3	q2=4	q3=2	q4=5	q5=1

Обозначим через m(p1, p2,…, pm, q1, q2,…, qn) вектор симплексных множителей или потенциалов. Тогда Dij=mAij-cij , iÎNm, jÎNn, откуда следует

Dij=pi+qj-cij , iÎNm, jÎNn

Положим, что p1=0. Остальные потенциалы находим из условия, что для базисных клеток Dij=0. В данном случае получаем

D11=0, p1+q1-c11=0, 0+q1-3=0, q1=3

D21=0, p2+q1-c21=0, p2+3-2=0, p2= -1

D23=0, p2+q3-c23=0, -1+q3-1=0, q3=2

аналогично, получим: q2=4, р3=-1, q4=5, q5=1.

Затем вычисляем оценки всех свободных клеток:

D12=p1+q2-c12=0+4-6= -2

D13=p1+q3-c13=0+2-4=-2

D14=2; D15=1; D24=1; D25=0; D31= -4; D32= -2

Находим наибольшую положительную оценку:

mах(Dij >0)=2=D14,

Для найденной свободной клетки 14 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 14-34-33-23-21-11. Производим перераспределение поставок вдоль цикла пересчета: