Методы оптимальных решений

Размещено на http://www.allbest.ru/

Вариант 2

1. Витамины А, В и С, которых требуется в день 6, 8 и 2 г соответственно, содержатся в двух видах продуктов. Цена первого продукта равна 50 руб./кг, цена второго продукта -- 20 руб./кг., при этом в 1 кг первого продукта содержится 2 г витамина А, 4 г витамина В и 2 г витамина С; в 1 кг второго продукта содержится соответственно 2 и 3 г витаминов A и B (витамин C во втором продукте не содержится). Поставьте задачу составления пищевого рациона минимальной стоимости и решите эту задачу двойственным симплексным методом.

Решение. Задача имеет следующий вид:

Введем балансовые неизвестные х₃, х₄, х₅ и домножим целевую функцию и все ограничения на (-1):

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

Таблица 1

2. Заявки потребителей на продукцию фирмы на первый второй и третий год составляют соответственно d₁ =5, d₂ =3 и d₃ = 2 единицы. К началу первого этапа на складе имеется y₁ =2 единицы продукции. Затраты на хранение единицы продукции в течение первого, второго и третьего года равны h₁ = 5, h₂ = 4, h₃ =3 ден. ед. Затраты на производство u_j единиц продукции на j-м этапе определяются функцией ц_j(u_j) = u²_j + 4u_j + 3 (j =1, 2, 3). Составьте такой поэтапный план производства продукции, который обеспечивает удовлетворение всех заявок при минимальных суммарных затратах на производство и хранение.

Решение:

Исходные данные задачи можно кратко записать одной строкой:

d1 d2 d3 a b c h1 h2 h3 y1

5 3 2 1 2 3 5 4 3 2

Воспользовавшись рекуррентными соотношениями, последовательно вычисляем F1 (x = y2), F2 (x = y3), .... , Fk (x = yk+1), .... и соответственно находим 1 (x= y2), 2 (x = y3 ), .... , `k (x = yk+1), .... Положим k = 1.

Параметр состояния x = у2 может принимать целые значения на отрезке 0 у2 d2 + d3 0 y2 2 + 3 т. е. у2 = 0, 1, 2, 3, 4, 5. Каждому значению параметра состояния должна отвечать определенная область изменения переменной x1, характеризуемая условием 0 х1 d1 + у2 или 0 х1 3 + у2 Из балансового уравнения х1 + у1 - d1 = у2 непосредственно следует, что объем производства связан со значением параметра состояния x=у2 соотношением

x1 = y2 + d1 - y1 = y2 + 3 - 3 = y2

В этом и состоит особенность первого этапа. Если задан уровень запаса к началу первого этапа, то каждому значению у2 отвечает единственное значение х1 и потому F1(x = y2) = W1 (x1, y2) Придавая у2 различные целые значения от 0 до 6 и учитывая предыдущее соотношение, находим

симплексный метод переменная функция

y2=0, x1=0, W1(0;0)=02+2Ч0+2+4Ч0=2

y2=1, x1=1, W1(1;1)=12+2Ч2+2+4Ч1=11

y2=2, x1=2, W1(2;2)=22+2Ч2+2+4Ч2=18

y2=3, x1=3, W1(3;3)=32+2Ч3+2+4Ч3=29

y2=4, x1=4, W1(4;4)=42+2Ч4+2+4Ч4=42

y2=5, x1=5, W1(5;5)=52+2Ч5+2+4Ч5=57

Значения функции состояния F1(x):

x=y2

0 1 2 3 4 5

F1(x=y2)

2 11 18 29 42 57

x1(x=y2)

0 1 2 3 4 5

Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию F2(x = y3) Здесь минимум берется по единственной переменной х2, которая может изменяться в пределах 0Јx2Јd2+y3 или 0Јx2Ј2+y3.

где верхняя граница зависит от параметра состояния x = у3, который принимает значения на отрезке 0Јy3Јd3 , т. е. 0Јy3Ј3 а аргумент у2 связан с х2 и у3 балансовым уравнением x2+y2-d2=y3 откуда следует

y2=y3+d2-x2=y3+2-x2. Придавая параметру состояния различные значения от 0 до 3, будем последовательно вычислятьW2 (x2, x), а затем определять F2(x) и 2(x). Положим x=у3= 0. Тогда, 0Јx2Ј2, т. е. переменная х2 может принимать значения: 0, 1, 2, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле: у2=2-х2. Последовательно находим:

если x2 = 0, то у2 = 2 , W2 (0, 2) = 02 + 2Ч0 + 2 + F1(2) = 2 + 18 = 20,

x2 = 1, y2 = 2 - 1 = 1, W2 (1, 2) = 12 + 5Ч1 + 2 + F1(1) = 8 + 11 = 19,

x2 = 2, y2 = 2 - 2 =0, W2 (2, 2) = 22 + 5Ч2 + 2 + F1(0) = 16 + 2 = 18

Наименьшее из полученных значений W2 есть F2(0), т. е. F2(x=y3=0)=18, причем минимум достигается при значении х2, равном `2 (x = y3 = 0) = 2 Положим x = у3 = 1. Тогда, согласно (1), 0 Ј x2 Ј 3, т. е. переменная х2 может принимать значения: 0, 1, 2, 3, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (2): у2 = 3 - х2 Последовательно находим:

если x2=0, то y2=3-0=3, W2(0,1)=02+2Ч0+2+3Ч1+F1(3)=5+29=34,

x2=1, y2=3-1=2, W2(1,2)=12+2Ч1+2+3Ч1+F1(2)=8+18=26,

x2=2, y2=3-2=1, W2(2,1)=22+2Ч2+2+3Ч1+F1(1)=13+11=24,

x2=3, y2=3-3=0, W2(3,1)=32+2Ч3+2+3Ч1+F1(0)=20+2=22.

Наименьшее из полученных значений W2 есть F2 (1), т. е. F2(x=y3=1)=minW2(x2,1)=22, причем минимум достигается при значении х2, равном 2(x=y3=1)=3 Положим x=у3=2. Тогда, 0Јx2Ј4, т. е. переменная х2 может принимать значения: 0, 1, 2, 3, 4, а каждому значению х2 отвечает определенное значение у2: у2=4-х2 если

x2=0, то y2=4-0=4, W2(0,2)=02+2Ч0+2+3Ч2+F1(4)=8+42=50,

x2=1, y2=4-1=3, W2(1,2)=12+2Ч1+2+3Ч2+F1(3)=11+29=40,

x2=2, y2=4-2=2, W2(2,2)=22+2Ч2+2+3Ч2+F1(2)=16+18=34,

x2=3, y2=4-3=1, W2(3,2)=32+2Ч3+2+3Ч2+F1(1)=23+11=34,

x2=4, y2=4-4=0, W2(4,2)=42+2Ч4+2+3Ч2+F1(0)=32+2=40.

Наименьшее из полученных значений W2 есть F2(2), т. е. F2(x=y3=2)=minW2(x2,2)=min(64,55,50,49,52)=49, причем минимум достигается при значении х2, равном `2 (x = y3 = 2) = 3 Положим x = у3 = 3. Тогда, согласно (1), 0 Ј x2 Ј 5, т. е. переменная х2 может принимать значения: 0, 1, 2, 3, 4, 5, а каждому значению х2 отвечает определенное значение у2:

у2=5-х2 если

x2=0, то y2=5-0=5, W2(0, 3)=02+2Ч0+2+3Ч3+F1(5)=11+57 = 68,

x2=1, y2=5-1=4, W2(1,3)=12+2Ч1+2+3Ч3+F1(4)=14+42=56,

x2=2, y2=5-2=3, W2(2,3)=22+2Ч2+2+3Ч3+F1(3)=19+29=48,

x2=3, y2=5-3=2, W2(3,3)=32+2Ч3+2+3Ч3+F1(2)=26+18=44,

x2=4, y2=5-4=1, W2(4,3)=42+2Ч4+2+3Ч3+F1(1)=35+11=46,

x2=5, y2=5-5=0, W2(5,3)=52+2Ч5+2+3Ч3+F1(0)=46+2=48.

Наименьшее из полученных значений W2 есть F2 (3), т. е. F2 (x = y3 = 3) = min W2 (x2, 3) = 44, причем минимум достигается при значении х2, равном 2(x=y3=3)=3 x=у3

0 1 2 3

F2(x=y3)

18 22 34 44

(x=y3)

2 3 2 или 3 3

Переходим к следующему этапу. Полагаем k=3 и табулируем функцию F3(x=y4):

Вычисляем значение функции состояния только для одного значения аргумента x = у4= 0, так как не хотим оставлять продукцию в запас в конце исследуемого периода.

0Јy4Ј0; x=y4; 0 Ј x3 Ј d3 + y4 > 0 Ј x3 Ј 3; y3 = y4 + d3-x3= y4+3- x3;

W3(x3, y4) = a + bx3 + c + h3y4 + F2(y3)= +2 x3+2 + 2 y4 + F2(y3)

x3=0 y3=3 W3(0; 0)=02 + 2Ч0 +2 +2Ч0 +F2(3)=2 +44=46

x3=1 y3=2 W3(1;0)=12+2Ч1+2+2Ч0+F2(2)=5+34=39

x3=2 y3=1 W3(2;0)=22+2Ч2+2+2Ч0+F2(1)=10+22=32

x3=3 y3=0 W3(3; 0)=32 + 2Ч3 +2+2Ч0 +F2(0)=17 +18=35

Получаем F3 (x = y4) = min W3 (x3, 0) = 32, причем минимум достигается при `3 (x = y4 = 0) = 2. Таким образом, мы получили не только минимальные общие затраты на производство и хранение продукции, но и последнюю компоненту оптимального решения. Она равна 2.

Остальные компоненты оптимального решения найдем по обычным правилам метода динамического программирования. Чтобы найти предпоследнюю компоненту, учтем, что х3 + у3 - -d3 = y4 или 2 + у3 - 3 = 0, откуда у3 = 1. Из таблицы (2) значений находим Аналогично, продолжая двигаться в обратном направлении и учтя, что х2 + у2 - d2 = y3 или 3 + у2 - 2 = 1, получаем у2 = 0; из таблицы (1) значений х1(x) находим. Итак, оптимальный план производства имеет вид х1 = 0, х2 = 3, х3 = 2, а минимальные общие затраты составляют 32 единицы.

Полезна самопроверка полученного результата. Для этого по исходным данным и найденному плану производства заполняем таблицу 5 и убеждаемся, что заявки потребителей на каждом этапе выполняются у1+х1іd1у2+х2іd2у3+х3іd33+0і30+3і21+2і3 и что суммарный объем производства и имевшегося к началу первого этапа запаса продукции равен суммарной потребности у1+х1+х2+х3=d1+d2+d33+0+3+2=3+2+3 причем это достигается при наименьших возможных затратах на производство и хранение продукции j(х1)+j(х2)+j(х3)+h1у2+h2у3=F3(y4=0) 2+17+10+0+3=32.

Размещено на Allbest.ru