Шпаргалка: 5 различных задач по программированию

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. РАСПРЕДЕЛЕНИЕ КАПИТАЛЬНЫХ ВЛОЖЕНИЙ

Пусть производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций fj(xj) приведены в таблице 1, где, например, число 50 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 50 тыс. руб. Таблица I

Прежде всего заполняем табл. 2. Значения f2(x2) складываем со значениями F1( - x2) = f1(- x2) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение . Заполняем таблицу 3.

Продолжая процесс, табулируем функции F3(), () и т.д. В табл. 6 заполняем только одну диагональ для значения = 700.

Таблица 2

 - x2 0 100 200 300 400 500 600 700

x2 F1( - x2)

f2(x2) 0 15 24 30 36 40 43 45

0

0 0 15 24 30 36 40 43 45

100 18 18* 33* 42* 48 54 58 61

200 26 26 41 50* 56 62 66

300 34 34 49 58* 64* 70*

400 39 39 54 63 69

500 42 42 57 66

600 44 44 59

700 46 46

Таблица 3

 0 100 200 300 400 500 600 700

F2() 0 18 33 42 50 58 64 70

 ()

0 0 100 100 200 300 300 300

Таблица 4

 - x3 0 100 200 300 400 500 600 700

x3 F2( - x3)

f3(x3) 0 18 33 42 50 58 64 70

0

0 0 18* 33 42 50 58 64 70

100 16 16 34* 49* 58 66 74 80

200 27 27 45 60* 69 77 85

300 37 37 55 70* 79* 87*

400 44 44 62 77 86

500 48 48 66 81

600 50 50 68

700 56 56

Таблица 5

 0 100 200 300 400 500 600 700

F3() 0 18 34 49 60 70 79 87

()

0 0 100 100 200 300 300 300

Таблица 6

 - x4 0 100 200 300 400 500 600 700

x4 F3( - x4)

f4(x4) 0 18 34 49 60 70 79 87

0 0 87

100 10 89*

200 17 87

300 23 83

400 29 78

500 34 68

600 38 56

700 41 41 .

Наибольшее число на этой диагонали: Zmax = 89 тыс. руб.,

причем четвертому предприятию должно быть выделено х*4 = 4 (700) = 100 тыс. руб.

На долю остальных трех предприятий остается 600 тыс. руб. Из табл. 5 видно, что третьему предприятию должно быть выделено x*3 = 3 (700-x*4) = 3 (600) = 300 тыс. руб.

Продолжая обратный процесс, находим x*2 = 2 (700 - x*4 - x*3) = 2 (300) = 100 тыс. руб.

На долю первого предприятия остается x*1 = 700 - x*4 - x*3 - x*2 = 200 тыс. руб.

Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:

x*1 =200; x*2 =100; x*3 = 300; x*4 = 100.

Оно обеспечивает производственному объединению наибольший воможный прирост прибыли 89 тыс. руб.

выполнение равенства: f1(x*1) + f2(x*2) + f3(x*3) + f4(x*4) = z max

24+18+37+10=89

ДИНАМИЧЕСКАЯ ЗАДАЧА УПРАВЛЕНИЯ ПРОИЗВОДСТВОМ И ЗАПАСАМИ

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

Пусть спрос (заявки) потребителей на нашу продукцию составляют: на первый этап d1=3 единицы, на второй – d2=2, на третий - d3=3 единицы. К началу первого этапа на складе имеется 3 единицы продукции, т.е. начальный уровень запаса равен y1=3. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h1=4, h2=3, h3=2. Затраты на производство xj единиц продукции на j-м этапе определяются функцией j(xj) = xj2 + 2xj + 2

т.е. а=1; b=5; с=2. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими.

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

d1 d2 d3 a b c h1 h2 h3 y1

3 2 3 1 2 2 4 3 2 3

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

Положим k = 1.

Параметр состояния  = у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 непосредственно следует, что объем производства связан со значением параметра состояния = у2 соотношением

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

В этом и состоит особенность первого этапа. Если задан уровень запаса к началу первого этапа, то каждому значению у2 отвечает единственное значение х1 и потому F1( = y2) = 1 (x1, y2)

Придавая у2 различные целые значения от 0 до 6 и учитывая предыдущее соотношение, находим

y2 = 0, x1 = 0, 1 (0;0) = 02 + 20 + 2 + 40 = 2*

y2 = 1, x1 = 1, 1 (1;1) = 12 + 22 + 2 + 41 = 11

y2 = 2, x1 = 2, 1 (2;2) = 22 + 22 + 2 + 42 = 18

y2 = 3, x1 = 3, 1 (3;3) = 32 + 23 + 2 + 43 = 29

y2 = 4, x1 = 4, 1 (4;4) = 42 + 24 + 2 + 44 = 42

y2 = 5, x1 = 5, 1 (5;5) = 52 + 25 + 2 + 45 = 57

Значения функции состояния F1( ) представлены в табл. 1

Таблица 1

 = y2012345

F1 ( = y2)

2 11 18 29 42 57

x1(=y2)012345

Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию F2( = y3)

Здесь минимум берется по единственной переменной х2, которая может изменяться в пределах

0  x2  d2 + y3 или 0  x2  2 + y3(1)

где верхняя граница зависит от параметра состояния  = у3, который принимает значения на отрезке

0  y3  d3 , т.е. 0  y3  3

а аргумент у2 связан с х2 и у3 балансовым уравнением x2 + y2 - d2 = y3 откуда следует y2 = y3 + d2 - x2 = =y3 + 2 - x2 (2)

Придавая параметру состояния различные значения от 0 до 3, будем последовательно вычислять 2 (x2, ), а затем определять F2( ) и 2( ).

Положим  = у3 = 0. Тогда, согласно (1), 0  x2  2, т.е. переменная х2 может принимать значения: 0, 1, 2, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (2): у2 = 2 - х2

Последовательно находим:

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

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

x2 = 2, y2 = 2 - 2 =0, 2 (2,2) = 22 + 52 + 2 + F1(0) = 16 + 2 = 18*,

Наименьшее из полученных значений 2 есть F2 (0), т.е.

F2 ( = y3 = 0) = 18,

причем минимум достигается при значении х2, равном  2 ( = y3 = 0) = 2

Положим  = у3 = 1. Тогда, согласно (1), 0  x2  3, т.е. переменная х2 может принимать значения: 0, 1, 2, 3, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (2): у2 = 3 - х2

Последовательно находим:

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

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

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

x2 = 3, y2 = 3-3 = 0, 2 (3,1) = 32 + 23 + 2 + 31 + F1(0) = 20 + 2 = 22*,

Наименьшее из полученных значений 2 есть F2 (1), т.е.

F2 ( = y3 = 1) = min 2 (x2,1) = 22,

причем минимум достигается при значении х2, равном  2 ( = y3 = 1) = 3

Положим  = у3 = 2. Тогда, согласно (1), 0  x2  4, т.е. переменная х2 может принимать значения: 0, 1, 2, 3, 4, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (2): у2 = 4 - х2

если x2 = 0, то y2 = 4-0 = 4,2 (0,2) = 02 + 20 + 2 + 32 + F1(4) = 8 + 42 = 50,

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

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

x2 = 3, y2 = 4-3 = 1, 2 (3,2) = 32 + 23 + 2 + 32 + F1(1) = 23 + 11 = 34*,

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

Наименьшее из полученных значений 2 есть F2 (2), т.е.

F2 ( = y3 = 2) = min 2 (x2,2) = min (64, 55, 50, 49, 52) = 49,

x2

причем минимум достигается при значении х2, равном  2 ( = y3 = 2) = 3

Положим  = у3 = 3. Тогда, согласно (1), 0  x2  5, т.е. переменная х2 может принимать значения: 0, 1, 2, 3, 4, 5, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (2): у2 = 5 - х2

если x2 = 0, то y2 = 5-0 = 5,2 (0,3) = 02 + 20 + 2 + 33 + F1(5) = 11 + 57 = 68,

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

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

x2 = 3, y2 = 5-3 = 2, 2 (3,3) = 32 + 23 + 2 + 33 + F1(2) = 26 + 18 = 44*,

x2 = 4, y2 = 5-4 = 1, 2 (4,3) = 42 + 24 + 2 + 33 + F1(1) = 35 + 11 = 46.

x2 = 5, y2 = 5-4 = 0, 2 (5,3) = 52 + 25 + 2 + 33 + F1(0) = 46 + 2 = 48.

Наименьшее из полученных значений 2 есть F2 (3), т.е.

F2 ( = y3 = 3) = min 2 (x2,3) = 44,

причем минимум достигается при значении х2, равном  2 ( = y3 = 3) = 3

Результаты табулирования функции F2 ( = y3)сведены в табл. 2.

Таблица 2

= у30123

F2 (= y3)18223444

(= y3)

2 3 2 или 3 3

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

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

0y40; =y4; 0  x3  d3 + y4 → 0  x3  3; y3 = y4 + d3-x3= y4+3- x3;

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

x3=0 y3=3 3(0;0)=02 + 20 +2 +20 +F2(3)=2 +44=46

x3=1 y3=2 3(1;0)=12 + 21 +2+20 + F2(2)=5 +34=39

x3=2 y3=1 3(2;0)=22 + 22 +2+20 + F2(1)=10+22=32*

x3=3 y3=0 3(3;0)=32 + 23 +2+20 +F2(0)=17 +18=35

Получаем F3 ( = y4) = min 3 (x3,0) = 32, причем минимум достигается при  3 ( = y4 = 0) = 2.

Таким образом, мы получили не только минимальные общие затраты на производство и хранение продукции, но и последнюю компоненту оптимального решения. Она равна = 2.

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

Аналогично, продолжая двигаться в обратном направлении и учтя, что х2 + у2 - d2 = y3 или 3 + у2 - 2 = 1, получаем у2 = 0; из таблицы (1) значений х1() находим .

Итак, оптимальный план производства имеет вид х1 = 0, х2 = 3, х3 = 2, а минимальные общие

затраты составляют 32 единицы.

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

плану производства заполняем таблицу 5 и убеждаемся, что заявки потребителей на каждом

этапе выполняются у1 + х1  d1у2 + х2  d2у3 + х3  d3

3 + 0  30 + 3  21 + 2  3

и что суммарный объем производства и имевшегося к началу первого этапа запаса продукции равен суммарной потребности у1 + х1 + х2 + х3 = d1 + d2 + d3 3 + 0 + 3 + 2 = 3 + 2 + 3

причем это достигается при наименьших возможных затратах на производство и хранение продукции

(х1) + (х2) + (х3) + h1у2 + h2у3 = F3(y4=0)

2 + 17 + 10 + 0 + 3 = 32

Самопроверка результатов

ЭТАПЫ январь февраль март Итого за 3 месяца

Имеем продукции к началу месяца, шт. у1 = 3 у2 = 0 у3 = 1 у1 = 3

Производим в течение месяца, шт. х1 = 0 х2 = 3 х3 = 2 х1+ х2+ х3 = 5

Отпускаем заказчикам, шт. d1 = 3 d2 = 2 d3 = 3 d1+ d2+ d3 = 8

Остаток к концу месяца (храним в течение текущего месяца), шт. у2 = 0 у3 = 1 у4 = 0

Затраты на производство, руб.(х1)=2(х2)=17(х3)=10(х1) + (х2) + (х3) = 29

Затраты на хранение, руб. h1у2 = 0 h2у3 = 3 0 h1у2 + h2у3 = 3

МАТРИЧНАЯ МОДЕЛЬ ПРОИЗВОДСТВЕННОЙ ПРОГРАММЫ ПРЕДПРИЯТИЯ

- производственная программа

0*80+ 0,1*60 +0,2*70=20

0,4*80 +0*60 +0,1*70=39

0,2*80 +0,3*60 +0,2*70=48

где Y - объем товарной продукции.

где В – коэффициенты прямых затрат.

h11=4*0 +7*0,1+ 2*0,2=1,1

h21=2*0 +4*0,1+ 1*0,2=0,6

h31=20*0 +13*0,1+ 16*0,2=4,5

h41=0,2*0+0,3*0,1+ 0,2*0,2=0,07

h12=4*0,4 +7*0+ 2*0,1=1,8

h22=2*0,4+4*0+ 1*0,1=0,9

h32=20*0,4+13*0+ 16*0,1=9,6

h42=0,2*0,4 +0,3*0+ 0,2*0,1=0,1

h13=4*0,2+7*0,3+ 2*0,2=3,3

h23=2*0,2+4*0,3+ 1*0,2=1,8

h33=20*0,2+13*0,3+ 16*0,2=11,1

h43=0,2*0,2+0,3*0,3+0,2*0,2=0,17

1,1*80 +1,8*60 +3,3*70=427

0,6*80 +0,9*60 +1,8*70=228

4,5*80 +9,6*60 +11,1*70=1713

0,07*80 +0,1*60 +0,17*70=23,5

где S – полные затраты всех внешних ресурсов.

МАТРИЧНАЯ ИГРА КАК МОДЕЛЬ КОНКУРЕНЦИИ И СОТРУДНИЧЕСТВА

Седловой точки нет. Обозначим искомую оптимальную стратегию первого игрока (х, 1-х). Это вектор-столбец, который мы записываем для удобства в виде строки.

Обозначим j(x) – средний выигрыш первого в расчете на партию, когда он и?