Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
30
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ
Кафедра прикладной математики
КУРСОВАЯ РАБОТА
по дисциплине «Прикладная математика»
Выполнил(а) ………………..
Институт
Отделение
Курс II
Группа ……………….
Руководитель ……………….
Дата сдачи на проверку ..............................
Дата защиты ..............................
Оценка ..............................
Подпись руководителя ..............................
Москва - 2002
|
[1]
[2]
[3]
[4] [4.0.0.1] Zmin = [4.0.0.2] Zmin = [4.0.0.3] Zmin = [4.0.0.4] Zmin =
[5]
[6]
[7]
[8]
[9] |
Постановка задачи
Сформулировать линейную производственную задачу и составить ее математическую модель.
Преобразовать данную задачу к виду основной задачи линейного программирования, решить ее методом направленного перебора базисных допустимых решений, обосновывая каждый шаг процесса, найти оптимальную производственную программу, максимальную прибыль, остатки ресурсов различных видов и указать “узкие места” производства.
В последней симплексной таблице указать обращенный базис Q-1, соответствующий оптимальному набору базисных неизвестных. Проверить выполнение соотношения
H = Q-1 * B.
Если по оптимальной производственной программе какие-то два вида продукции не должны выпускаться, то в таблице исходных данных вычеркнуть соответствующие два столбца, составить математическую модель задачи оптимизации производственной программы с двумя оставшимися переменными, сохранив прежнюю нумерацию переменных и решить графически.
Исходные данные
Предприятие выпускает 4 вида продукции, используя для этого три вида ресурсов. Известна технологическая матрица A, в которой каждый элемент aij означает необходимое количество i-го ресурса для выпуска j-го вида продукции:
|
2 |
0 |
2 |
3 |
|
|
А = |
1 |
5 |
4 |
2 |
|
3 |
4 |
0 |
1 |
Известен вектор B объемов ресурсов, каждый элемент которого bi означает предельное количество i-го ресурса для выпуска всего объема продукции:
|
142 |
|
|
В = |
100 |
|
122 |
Также известен вектор удельной прибыли C, элементы которого cj означают прибыль от производства единицы продукции j-го вида:
|
С = |
34 |
20 |
8 |
23 |
Требуется составить производственную программу, обеспечивающую предприятию наибольшую прибыль при имеющихся ограниченных ресурсах.
Решение
Математическая модель задачи: найти производственную программу
(х1, х2, х3, х4),
максимизирующую прибыль
Z = 34 * х1 + 20 * х2 + 8 * х3 + 23 * х4
при ограничениях по ресурсам
|
2 * х1 |
+ |
2 * х3 |
+ |
3 * х4 |
<= |
142 |
|||
|
х1 |
+ |
5 * х2 |
+ |
4 * x3 |
+ |
2 * х4 |
<= |
100 |
(1) |
|
3 * х1 |
+ |
4 * х2 |
|
|
+ |
х4 |
<= |
122 |
где по смыслу задачи
x1 >= 0; x2 >= 0; x3 >= 0; x4 >= 0
Введя дополнительные неотрицательные неизвестные х5, х6, х7, заменяем неравенства (1) уравнениями вида:
|
2 * х1 |
+ |
2 * х3 |
+ |
3 * х4 |
+ |
х5 |
= |
142 |
||
|
х1 |
+ |
5 * х2 |
+ |
4 * x3 |
+ |
2 * х4 |
+ |
х6 |
= |
100 |
|
3 * х1 |
+ |
4 * х2 |
|
|
+ |
х4 |
+ |
х7 |
= |
122 |
Решаем полученную задачу симплексным методом (методом направленного перебора базисных допустимых решений) (см. Таблицу 1).
Таблица 1
|
34 |
20 |
8 |
23 |
0 |
0 |
0 |
|||
|
C |
Базис |
Hi |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
|
0 |
х5 |
142 |
2 |
0 |
2 |
3 |
1 |
0 |
0 |
|
0 |
х6 |
100 |
1 |
5 |
4 |
2 |
0 |
1 |
0 |
|
0 |
х7 |
122 |
3 |
4 |
0 |
1 |
0 |
0 |
1 |
|
z – z0 |
0 |
-34 |
-20 |
-8 |
-23 |
0 |
0 |
0 |
|
|
0 |
х5 |
182/3 |
0 |
-8/3 |
2 |
7/3 |
1 |
0 |
-2/3 |
|
0 |
х6 |
178/3 |
0 |
11/3 |
4 |
5/3 |
0 |
1 |
-1/3 |
|
34 |
х1 |
122/3 |
1 |
4/3 |
0 |
1/3 |
0 |
0 |
1/3 |
|
z – z0 |
4148/3 |
0 |
76/3 |
-8 |
-35/3 |
0 |
0 |
34/3 |
|
|
23 |
х4 |
26 |
0 |
-8/7 |
6/7 |
1 |
3/7 |
0 |
-2/7 |
|
0 |
х6 |
16 |
0 |
39 |
18/7 |
0 |
-5/7 |
1 |
1/7 |
|
34 |
х1 |
32 |
1 |
12 |
-2/7 |
0 |
-1/7 |
0 |
3/7 |
|
z – z0 |
1686 |
0 |
12 |
18 |
0 |
5 |
0 |
8 |
Как видно из последней симплексной таблицы, оптимальная производственная программа имеет вид
х1 = 32, х2 = 0, х3 = 0, х4 = 26,
а максимальная прибыль равна
Zmax = 1686
При этом 1-й и 3-й ресурсы будут исчерпаны полностью (х5=0, х7=0), а 2-й ресурс будет иметь остаток х6 = 8 единиц.
Обращенный базис, отвечающий оптимальной производственной программе, содержится в последней симплексной таблице:
|
3/7 |
0 |
-2/7 |
|
|
Q –1 = |
-5/7 |
1 |
1/7 |
|
-1/7 |
0 |
3/7 |
Для того, чтобы убедиться в правильности полученного решения, следует проверить отношение Н = Q-1 * В:
|
3/7 |
0 |
-2/7 |
142 |
426/7 – 244/7 |
26 |
||||
|
Q-1 * В = |
-5/7 |
1 |
1/7 |
* |
100 |
= |
-710/7 + 100 + 122/7 |
= |
16 |
|
-1/7 |
0 |
3/7 |
122 |
-142/7 + 366/7 |
32 |
Следовательно, полученное решение верно.
Так как х2 = 0, х3= 0, можно составить математическую модель задачи с двумя переменными (х1 и х4):
|
Z = |
34 * х1 |
+ |
23 * х4 |
-> |
max |
|
2 * х1 |
+ |
3 * х4 |
<= |
142 |
|
|
х1 |
2 * x4 |
<= |
100 |
||
|
3 * х1 |
+ |
х4 |
<= |
122 |
Графическое решение такой модели изображено на Рисунке 1.
Рисунок 1
Решая систему двух линейных уравнений, получаем оптимальный результат:
|
2 * х1 |
+ |
3 * х4 |
= |
142 |
|
3 * х1 |
+ |
х4 |
= |
122 |
|
х1 |
= |
32 |
|
х3 |
= |
26 |
|
Zmax |
= |
1686 |
Полученный графическим методом результат совпадает с тем, который был получен ранее при использовании симплекс-метода.
Постановка задачи
Сформулировать задачу, двойственную линейной производственной задаче, как задачу определения расчетных оценок ресурсов, и найти ее решение, пользуясь второй основной теоремой двойственности (о дополняющей нежесткости). Указать оценку единицы каждого ресурса, минимальную суммарную оценку всех ресурсов, оценки технологий.
Применить найденные двойственные оценки ресурсов к решению следующей задачи.
Сформулировать задачу о расшивке “узких мест” производства и составить математическую модель. Определить область устойчивости двойственных оценок, где сохраняется структура программы производства. Решить задачу о “расшивке узких мест производства” при условии, что дополнительно можно получить от поставщиков не более 1/3 первоначального объема ресурса каждого вида (если задача окажется с двумя переменными, то только графически); найти план приобретения дополнительных объемов ресурсов, дополнительную возможную прибыль.
Исходные данные – см. Задачу 1.
Решение
При решении двойственной задачи требуется найти оценку единицы каждого вида ресурса. Это - задача линейного программирования, постановка которой формулируется следующим образом.
Найти вектор двойственных оценок
(у1, у2, у3),
минимизирующий общую всех ресурсов
f = 142 * y1 + 100 * y2 + 122 * y3
при условии, что по каждому виду продукции суммарная оценка ресурсов, затрачиваемых на производство единицы продукции, не меньше прибыли, получаемой от реализации единицы этой продукции
|
2 * у1 |
+ |
у2 |
+ |
3 * y3 |
>= |
34 |
|
5 * у2 |
+ |
4 * у3 |
>= |
20 |
||
|
2 * у1 |
+ |
4 * y2 |
|
|
>= |
8 |
|
3 * у1 |
+ |
2 * y2 |
+ |
у3 |
>= |
23 |
причем оценки ресурсов не могут быть отрицательными
у1 >= 0, у2 >= 0, у3 >= 0.
Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений х(х1,х2,х3) и у(у1,у2,у3) пары двойственных задач необходимо и достаточно выполнение условий
|
х1 * ( |
2 * у1 |
+ |
у2 |
+ |
3 * y3 |
- |
34 |
) = 0 |
|
х2 * ( |
5 * у2 |
+ |
4 * у3 |
- |
20 |
) = 0 |
||
|
х3 * ( |
2 * у1 |
+ |
4 * y2 |
|
|
- |
8 |
) = 0 |
|
х4 * ( |
3 * у1 |
+ |
2 * y2 |
+ |
у3 |
- |
23 |
) = 0 |
|
у1 * ( |
2 * х1 |
+ |
2 * х3 |
+ |
3 * х4 |
- |
142 |
) = 0 |
||
|
у2 * ( |
х1 |
+ |
5 * х2 |
+ |
4 * x3 |
+ |
2 * х4 |
- |
100 |
) = 0 |
|
у3 * ( |
3 * х1 |
+ |
4 * х2 |
|
|
+ |
х4 |
- |
122 |
) = 0 |
Ранее (см. Задачу 1) было найдено, что в решении исходной задачи х1>0 и х4>0. Поэтому
|
2 * у1 |
+ |
у2 |
+ |
3 * y3 |
- |
34 |
= 0 |
|
3 * у1 |
+ |
2 * y2 |
+ |
у3 |
- |
23 |
= 0 |
Если же учесть, что 2-й ресурс был избыточным и, согласно той же теореме двойственности, его двойственная оценка равна нулю:
y2 = 0
то приходим к системе уравнений
|
2 * у1 |
+ |
3 * y3 |
- |
34 |
= 0 |
|
3 * у1 |
+ |
у3 |
- |
23 |
= 0 |
откуда следует
у1 = 5,
у3 = 8.
Таким образом, получили двойственные оценки ресурсов
у1 = 5, у2 = 0, у3 = 8,
причем общая оценка всех ресурсов равна
fmin = 1686
Заметим, что это решение содержалось в последней строке симплексной таблицы исходной задачи.
Экономический смысл
Двойственная оценка 1-го ресурса у1 = 5 показывает, что добавление одной единицы этого ресурса обеспечит прирост прибыли в 5 единиц, двойственная оценка 3-го ресурса у3 = 8 - что добавление одной единицы 3-го ресурса обеспечит прирост прибыли в 8 единиц. Двойственная оценка 2-й технологии D2 = 12 показывает, что если произвести одну единицу продукции 2-го вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 12 единиц, оценка 3-й технологии D3 = 18 - что производство одной единицы продукции 3-го вида снизит прибыль на 18 единиц.
При выполнении оптимальной производственной программы 1-й и 3-й ресурсы используются полностью, т.е. образуют “узкие места производства”. Будем их заказывать дополнительно. Пусть T(t1, t2, t3) - вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие
H + Q-1 * T >= 0
Задача состоит в том, чтобы найти вектор
T (t1, t2, t3)
максимизирующий суммарный прирост прибыли
w = 5 * t1 + 8 * t3 (1)
при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)
|
26 |
3/7 |
0 |
-2/7 |
t1 |
0 |
||||
|
16 |
+ |
-5/7 |
1 |
1/7 |
* |
0 |
>= |
0 |
(2) |
|
32 |
-1/7 |
0 |
3/7 |
t3 |
0 |
предполагая, что дополнительно можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида
|
t1 |
142 |
||||
|
0 |
=< |
1/3 |
* |
100 |
(3) |
|
t3 |
122 |
причем по смыслу задачи
t1 >= 0, t3 >= 0 (4)
Переписав неравенства (2) и (3) в виде
|
-3 * t1 |
+ |
2 * t3 |
=< |
182 |
|
|
5 * t1 |
- |
t3 |
=< |
112 |
|
|
t1 |
- |
3 * t3 |
=< |
224 |
(5) |
|
t1 |
=< |
47.33 |
|||
|
t3 |
=< |
40.67 |
приходим к задаче линейного программирования: максимизировать (1) при условиях (4), (5).
Эту задачу решаем графическим методом (см. Рисунок 2).
Рисунок 2
Решаем систему уравнений:
|
5 * t1 |
- |
t3 |
= |
112 |
|
|
t3 |
= |
40.67 |
Программа “расшивки” имеет вид
t1 = 30.53, t2 = 0, t3 = 40.67
и прирост прибыли составит
w = 478.01
Сводка результатов приведена в Таблице 2.
Таблица 2
|
cj |
30 |
28 |
9 |
23 |
bi |
x4+i |
yi |
ti |
|
2 |
0 |
2 |
3 |
142 |
0 |
5 |
30.53 |
|
|
aij |
1 |
5 |
4 |
2 |
100 |
16 |
0 |
0 |
|
3 |
4 |
0 |
1 |
122 |
0 |
8 |
40.67 |
|
|
xj |
32 |
0 |
0 |
26 |
1686 |
478.01 |
||
|
D j |
0 |
12 |
18 |
0 |
Постановка задачи
Составить математическую модель транспортной задачи. Если полученная модель окажется открытой, то свести ее к замкнутой и найти оптимальное решение транспортной задачи методом потенциалов.
Исходные данные
Стоимости перевозок:
|
2 |
7 |
2 |
3 |
|
1 |
5 |
4 |
2 |
|
3 |
4 |
6 |
1 |
Вектор объемов производства:
А = (80, 60, 30).
Вектор объемов потребления:
В = (34, 40, 38, 53).
Решение
Так как размеры объемов производства превышают размеры объемов потребления на 5 единиц, вводим фиктивного b5=5 потребителя и определяем первоначальный опорный план методом северо-западного угла:
|
b1=34 |
b2=40 |
b3=38 |
b4=53 |
b5=5 |
|
|
a1=80 |
2 34 |
7 40 |
2 6 |
3 |
0 |
|
a2=60 |
1 |
5
|
4 32 |
2 28 |
0 |
|
a3=30 |
3 |
4 |
6
|
1 25 |
0 5 |
Находим оптимальное решение транспортной задачи методом потенциалов.
|
b1=34 |
b2=40 |
b3=38 |
b4=53 |
b5=5 |
||
|
a1=80 |
2 34 |
- 7 40 |
+ 2 6 |
3 |
0 |
p1 = 0 |
|
a2=60 |
1 |
+ 5 * |
- 4 32 |
2 28 |
0 |
p2 = 2 |
|
a3=30 |
3 |
4 |
6
|
1 25 |
0 5 |
p3 = 1 |
|
q1 = 2 |
q2 = 7 |
q3 = 2 |
q4 = 0 |
q5 = -1 |
||
|
D21 = 3 |
D22 = 4 |
D33 = -3 |
D14 = -3 |
D15 = -1 |
||
|
D31 = 0 |
D32 = 4 |
D25 = 1 |
||||
|
Zmin = |
565 |
|
b1=34 |
b2=40 |
b3=38 |
b4=53 |
b5=5 |
||
|
a1=80 |
2 34 |
- 7 8 |
2 38 |
3 |
+ 0 * |
p1 = 0 |
|
a2=60 |
1 |
+ 5 32 |
4 |
- 2 28 |
0 |
p2 = -2 |
|
a3=30 |
3 |
4 |
6
|
+ 1 25 |
- 0 5 |
p3 = -3 |
|
q1 = 2 |
q2 = 7 |
q3 = 2 |
q4 = 4 |
q5 = 3 |
||
|
D21 = -1 |
D32 = 0 |
D13 = -4 |
D14 = 1 |
D15 = 3 |
||
|
D31 = -4 |
D33 = -7 |
D25 = 0 |
||||
|
Zmin = |
441 |
|
b1=34 |
b2=40 |
b3=38 |
b4=53 |
b5=5 |
||
|
a1=80 |
2 34 |
- 7 3 |
2 38 |
+ 3 * |
0 5 |
p1 = 0 |
|
a2=60 |
1 |
+ 5 37 |
4 |
- 2 23 |
0 |
p2 = -2 |
|
a3=30 |
3 |
4 |
6
|
1 30 |
0 |
p3 = -3 |
|
q1 = 2 |
q2 = 7 |
q3 = 2 |
q4 = 4 |
q5 = 0 |
||
|
D21 = 0 |
D32 = 0 |
D23 = -4 |
D14 = 1 |
D25 = -2 |
||
|
D31 = -4 |
D33 = -7 |
D35 = -3 |
||||
|
Zmin = |
426 |
|
b1=34 |
b2=40 |
b3=38 |
b4=53 |
b5=5 |
||
|
a1=80 |
2 34 |
7 |
2 38 |
3 3 |
0 5 |
p1 = 0 |
|
a2=60 |
1 |
5 40 |
4 |
2 20 |
0 |
p2 = -1 |
|
a3=30 |
3 |
4 |
6
|
1 30 |
0 |
p3 = -2 |
|
q1 = 2 |
q2 = 6 |
q3 = 2 |
q4 = 3 |
q5 = 0 |
||
|
D21 = 0 |
D12 = -1 |
D23 = -3 |
D25 = -1 |
|||
|
D31 = -3 |
D32 = 0 |
D33 = -6 |
D35 = -2 |
|||
|
Zmin = |
423 |
Все потенциалы свободных клеток Dij неположительные, следовательно, решение, представленное в последней таблице, является оптимальным, причем минимальная стоимость всех перевозок составляет 423 единицы.
Постановка задачи
Методом динамического программирования решить задачу распределения капитальных вложений между четырьмя предприятиями производственного объединения, располагающего суммой в 700 тыс. руб. (выделяемые суммы кратны 100 тыс. руб.).
Исходные данные
Значения функции fj(хj) приведены в Таблице 1 (считаем их заданными, их определение - довольно трудоемкая экономическая задача):
Таблица 1
|
xj |
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
|
f1(xj) |
0 |
20 |
33 |
42 |
48 |
53 |
56 |
58 |
|
f2(xj) |
0 |
22 |
37 |
49 |
59 |
68 |
76 |
82 |
|
f3(xj) |
0 |
10 |
29 |
42 |
52 |
60 |
65 |
69 |
|
f4(xj) |
0 |
16 |
27 |
37 |
44 |
48 |
50 |
56 |
Решение
Воспользуемся методом динамического программирования для решения этой задачи.
Введем параметр состояния x - количество рублей, выделяемых нескольким предприятиям, и определим функцию состояния Fk(x) - максимальная прибыль на первых k предприятиях, если они вместе получат хk рублей.
Табулируя последовательно функции Fk(x), получим решение, ход которого приведен в Таблицах 2-6.
Таблица 2
|
x-х2 |
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
|
|
х2 |
F(x-x2) f2(x2) |
0 |
20 |
33 |
42 |
48 |
53 |
56 |
58 |
|
0 |
0 |
0 |
20 |
33 |
42 |
48 |
53 |
56 |
58 |
|
100 |
22 |
22* |
42* |
55 |
64 |
70 |
75 |
78 |
|
|
200 |
37 |
37 |
57* |
70* |
79 |
85 |
90 |
||
|
300 |
49 |
49 |
69 |
82* |
91 |
97 |
|||
|
400 |
59 |
59 |
79 |
92* |
101* |
||||
|
500 |
68 |
68 |
88 |
101* |
|||||
|
600 |
76 |
76 |
96 |
||||||
|
700 |
82 |
82 |
Таблица 3
|
x |
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
|
F2(x) |
0 |
22 |
42 |
57 |
70 |
82 |
92 |
101 |
|
x2(x) |
0 |
100 |
100 |
200 |
200 |
300 |
400 |
400/500 |
Таблица 4
|
x-х3 |
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
|
|
х3 |
F(x-x3) f3(x3) |
0 |
22 |
42 |
57 |
70 |
82 |
92 |
101 |
|
0 |
0 |
0* |
22* |
42* |
57* |
70 |
82 |
92 |
101 |
|
100 |
10 |
10 |
32 |
52 |
67 |
80 |
92 |
102 |
|
|
200 |
29 |
29 |
51 |
71* |
86* |
99* |
111 |
||
|
300 |
42 |
42 |
64 |
84 |
99* |
112* |
|||
|
400 |
52 |
52 |
74 |
94 |
109 |
||||
|
500 |
60 |
60 |
82 |
102 |
|||||
|
600 |
65 |
65 |
87 |
||||||
|
700 |
69 |
69 |
Таблица 5
|
x |
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
|
F2(x) |
0 |
22 |
42 |
57 |
71 |
86 |
99 |
112 |
|
x2(x) |
0 |
0 |
0 |
0 |
200 |
200 |
200/300 |
300 |
Таблица 6
|
x-х4 |
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
|
|
х4 |
F(x-x4) f4(x4) |
0 |
22 |
42 |
57 |
71 |
86 |
99 |
112 |
|
0 |
0 |
112 |
|||||||
|
100 |
16 |
115* |
|||||||
|
200 |
27 |
113 |
|||||||
|
300 |
37 |
108 |
|||||||
|
400 |
44 |
101 |
|||||||
|
500 |
48 |
90 |
|||||||
|
600 |
50 |
72 |
|||||||
|
700 |
56 |
56 |
Zmax = 115 тыс. руб.,
причем четвертому предприятию должно быть выделено
х4* = х4(700) = 100 тыс. руб.
На долю остальных трех предприятий остается 600 тыс. руб. Из Таблицы 5 видно, что третьему предприятию должно быть выделено
Продолжая обратный процесс, находим
На долю первого предприятия останется
Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:
Оно обеспечивает производственному объединению наибольший возможный прирост прибыли 115 тыс. руб.
В качестве проверки правильности решения задачи можно использовать равенство
f1(x1*) + f2(x2*) + f3(x3*) + f4(x4*) = Zmax
Следовательно, полученные решения верны.
Постановка задачи
Рассмотреть динамическую задачу управления производством и запасами.
Исходные данные
Спрос (заявки) потребителей на продукцию составляют: на первый этап d1 = 5 единиц, на второй – d2 = 1, на третий - d3 = 2 единицы. К началу первого этапа на складе имеется только 4 единицы продукции, т.е. начальный уровень запаса равен y1=4. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h1 = 2, h2 = 1, h3 = 1. Затраты на производство xj единиц продукции на j-м этапе определяются функцией
j(xj) = 2 * xj2 + 6 (1)
т.е. а = 2; b = 0; с = 6. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а общие затраты на производство и хранение за все три этапа были наименьшими.
Решение
Воспользовавшись рекурентными соотношениями, последовательно вычисляем F1 ( = y2), F2 ( = y3), ..., Fk ( = yk+1), ... и соответственно находим 1 (= y2), 2 ( = y3 ), ..., k ( = yk+1), ...
Положим k = 1. Тогда имеем
F1(= y2) = min{2 * xj2 + 6 + 2 * y2} (2)
Учтем, что параметр состояния = у2 может принимать целые значения на отрезке
0 у2 d2 + d3
0 y2 3
т.е.
у2 = 0, 1, 2, 3
При этом каждому значению параметра состояния должна отвечать определенная область изменения переменной x1, характеризуемая условием
0 х1 d1 + у2
0 х1 5 + у2
Из балансового уравнения
х1 + у1 - d1 = у2
непосредственно следует, что объем производства связан со значением параметра состояния = у2 соотношением
x1 = y2 + d1 - y1 = y2 + 5 - 4 = y2 + 1 (3)
Каждому значению у2 отвечает единственное значение х1 и потому
F1( = y2) = 1 (x1, y2)
Придавая у2 различные целые значения от 0 до 3 и учитывая (3), находим
y2 = 0, x1 = 1, 1 (1;0) = 2 * 12 + 6 + 2 * 0 = 8
y2 = 1, x1 = 2, 1 (2;1) = 2 * 22 + 6 + 2 * 1 = 16
y2 = 2, x1 = 3, 1 (3;2) = 2 * 32 + 6 + 2 * 2 = 28
y2 = 3, x1 = 4, 1 (4;3) = 2 * 42 + 6 + 2 * 3 = 44
Значения функции состояния F1() представлены в Таблице 1.
Таблица 1
|
= y2 |
0 |
1 |
2 |
3 |
|
F1 ( = y2) |
8 |
16 |
28 |
44 |
|
x1(=y2) |
1 |
2 |
3 |
4 |
Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию F2( = y3):
F2( = y3) = min 1 (x1, y2) = min{a * x22 + b * x2 + c + h2 * y3 + F1(y2)} =
= min {2 * x22 + 6 + y3 + F1(y2)} (4)
Здесь минимум берется по единственной переменной х2, которая может изменяться в пределах
0 x2 d2 + y3 или 0 x2 1 + y3 (5)
где верхняя граница зависит от параметра состояния = у3, который принимает значения на отрезке
0 y3 d3 , т.е. 0 y3 2 (6)
а аргумент у2 в последнем слагаемом справа в соотношении (4) связан с х2 и у3 балансовым уравнением
x2 + y2 - d2 = y3
откуда следует
y2 = y3 + d2 - x2 = y3 + 1 - x2 (7)
Придавая параметру состояния различные значения от 0 до 2, будем последовательно вычислять 2 (x2, ), а затем определять F2( ) и 2( ).
Положим = у3 = 0. Тогда, согласно (5),
0 x2 1,
т.е. переменная х2 может принимать значения 0, 1, которым отвечает значение у2, вычисляемое по формуле (7):
у2 = 1 - х2
Последовательно находим:
x2 = 0, y2 = 1 - 0 = 1, 2 (0,0) = 2 * 02 + 6 + 0 + F1(1) = 6 + 16 = 22
x2 = 1, y2 = 1 - 1 = 0, 2 (1,0) = 2 * 12 + 6 + 0 + F1(0) = 8 + 8 = 16*
Наименьшее из полученных значений 2 есть F2 (0), т.е.
F2 ( = y3 = 0) = min 2 (x2,0) = min (22, 16) = 16,
x2
причем минимум достигается при значении х2, равном
2 ( = y3 = 0) = 1
Положим = у3 = 1. Тогда, согласно (5),
0 x2 2,
т.е. переменная х2 может принимать значения: 0, 1, 2, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (7):
у2 = 2 - х2
Последовательно находим:
x2 = 0, y2 = 2 - 0 = 2, 2 (0,1) = 2 * 02 + 6 + 1 + F1(2) = 7 + 28 = 35
x2 = 1, y2 = 2 - 1 = 1, 2 (1,1) = 2 * 12 + 6 + 1 + F1(1) = 9 + 16 = 25
x2 = 2, y2 = 2 - 2 = 0, 2 (2,1) = 2 * 22 + 6 + 1 + F1(0) = 15 + 8 = 23*
Наименьшее из полученных значений 2 есть F2 (1), т.е.
F2 ( = y3 = 1) = min 2 (x2,1) = min (35, 25, 23) = 23,
x2
причем минимум достигается при значении х2, равном
2 ( = y3 = 1) = 2
Положим = у3 = 2. Тогда, согласно (5),
0 x2 3,
т.е. переменная х2 может принимать значения: 0, 1, 2, 3, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (7):
у2 = 3 - х2
Последовательно находим:
x2 = 0, y2 = 3 - 0 = 3, 2 (0,2) = 2 * 02 + 6 + 2 + F1(3) = 8 + 44 = 52
x2 = 1, y2 = 3 - 1 = 2, 2 (1,2) = 2 * 12 + 6 + 2 + F1(2) = 10 + 28 = 38
x2 = 2, y2 = 3 - 2 = 1, 2 (2,2) = 2 * 22 + 6 + 2 + F1(1) = 16 + 16 = 32*
x2 = 3, y2 = 3 - 3 = 0, 2 (3,2) = 2 * 32 + 6 + 2 + F1(0) = 26 + 8 = 34
Наименьшее из полученных значений 2 есть F2 (2), т.е.
F2 ( = y3 = 2) = min 2 (x2,2) = min (52, 38, 32, 34) = 32,
x2
причем минимум достигается при значении х2, равном
2 ( = y3 = 2) = 2
Результаты табулирования функции F2( = y3) сведены в Таблице 2.
Таблица 2
|
= у3 |
0 |
1 |
2 |
|
F2 (= y3) |
16 |
23 |
32 |
|
(= y3) |
1 |
2 |
2 |
Переходим к следующему этапу. Полагаем k=3 и табулируем функцию F3 ( = y4):
F3 ( = y4) = min{a * x32 + b * x3 + c + h3 * y4 + F2(y3)} =
= min{2 * x32 + 6 + y4 + F2(y3)}
Вычисляем значение функции состояния только для одного значения аргумента = у4 = 0, так как не имеет смысла оставлять продукцию в запас в конце исследуемого периода.
Тогда, согласно (5),
0 x3 2,
т.е. переменная х3 может принимать значения: 0, 1, 2, а каждому значению х3 отвечает определенное значение у3, вычисляемое по формуле (7):
у3 = 2 - х3
Последовательно находим:
x3 = 0, y3 = 2 - 0 = 2, 2 (0,0) = 2 * 02 + 6 + 0 + F2(2) = 6 + 32 = 38
x3 = 1, y3 = 2 - 1 = 1, 2 (1,0) = 2 * 12 + 6 + 0 + F2(1) = 8 + 23 = 31
x3 = 2, y3 = 2 - 2 = 0, 2 (2,0) = 2 * 22 + 6 + 0 + F2(0) = 14 + 16 = 30*
Получаем
F3 ( = y4) = min 3 (x3,0) = min (38, 31, 30) = 30,
x3
причем минимум достигается в двух значениях переменной х3
3 ( = y4 = 0) = 2
Таким образом, мы получили не только минимальные общие затраты на производство и хранение продукции, но и последнюю компоненту оптимального решения. Она равна
x3* = 2
Остальные компоненты оптимального решения найдем по обычным правилам метода динамического программирования. Чтобы найти предпоследнюю компоненту, учтем, что
х3 + у3 - d3 = y4
2 + у3 - 2 = 0,
у3 = 0,
Из таблицы 2 значений находим
x2*= 2 ( = y3 = 0) = 1
Аналогично, продолжая двигаться в обратном направлении и учитывая, что
х2 + у2 - d2 = y3
1 + у2 - 1 = 0,
у2 = 0
из таблицы (1) значений х1() находим
x1*= 1 ( = y2 = 0) = 1
Итак, оптимальный план производства имеет вид
х1 = 1
х2 = 1
х3 = 2
а минимальные общие затраты составляют 30 единиц.
Проверка полученного результата
Для этого по исходным данным и найденному плану производства убеждаемся, что заявки потребителей на каждом этапе выполняются
у1 + х1 d1 у2 + х2 d2 у3 + х3 d3
4 + 1 5 0 + 1 1 0 + 2 2
и что суммарный объем производства и имевшегося к началу первого этапа запаса продукции равен суммарной потребности
у1 + х1 + х2 + х3 = d1 + d2 + d3
4 + 1 + 1 + 2 = 5 + 1 + 2
8 = 8
причем это достигается при наименьших возможных затратах на производство и хранение продукции
(х1) + (х2) + (х3) + h1у2 + h2у3 = F3(y4=0)
8 + 8 + 14 + 2 * 0 + 1 * 0 = 30
30 = 30
Постановка задачи
Рассмотреть матричную игру как модель сотрудничества и конкуренции. Найти графическое решение игры. Указать, как проявляется конкуренция между игроками и сотрудничество между ними.
Исходные данные
|
1 |
2 |
4 |
0 |
|
2 |
0 |
-2 |
3 |
Решение
Сведем данный случай матричной игры (2*4) к анализу игры 2*2. Для этого необходимо графическое решение (см. Рисунок 3).
Рисунок 3
Как видно из Рисунка 3, данная матричная игра сводится к варианту
|
0 |
2 |
|
3 |
0 |
Рассчитаем оптимальные стратегии игроков P* и Q*:
p*1 = (a22 - a21) / (a11 + a22 - a12 - a21) = (0 - 3) / (0 + 0 – 2 – 3) = 3/5
p*2 = (a11 - a12) / (a11 + a22 - a12 - a21) = (0 - 2) / (0 + 0 – 2 – 3) = 2/5
q*1 = (a22 - a12) / (a11 + a22 - a12 - a21) = (0 - 2) / (0 + 0 – 2 – 3) = 2/5
q*2 = (a11 - a21) / (a11 + a22 - a12 - a21) = (0 - 3) / (0 + 0 – 2 – 3) = 3/5
P* = (3/5, 2/5)
Q* = (2/5, 3/5)
Рассчитаем цену игры v:
n m
v = S S aij * pi * qj = 0 * 3/5 * 2/5 + 3 * 2/5 * 2/5 + 2 * 3/5 * 3/5 + 0 * 2/5 * 3/5 = 6/5
j=1 i=1
Рассчитаем среднюю дисперсию и риск:
n m n m n m
D* = S S aij2 * p*i * q*j - (S S aij * p*i * q*j)2 = S S aij2 * p*i * q*j - v2 =
j=1 i=1 j=1 i=1 j=1 i=1
= 0 * 3/5 * 2/5 + 9 * 2/5 * 2/5 + 4 * 3/5 * 3/5 + 0 * 2/5 * 3/5 – 36/25 = 36/25
r = Ö D* = Ö 36/25 = 6/5 = 1.2
Рассчитаем риски игры r для Первого и Второго игроков:
n
Dj = S ai2 * p*i - v2
i=1
D1 = 0 * 3/5 + 9 * 2/5 – 36/25 = 54/25
D2 = 4 * 3/5 + 0 * 2/5 – 36/25 = 24/25
r1(1) = Ö 54/25 = 1.47
r1(2) = Ö 24/25 = 0.98
Зависимость риска Первого в малой окрестности его оптимальной стратегии показана на Рисунке 4.
r1(2) = 0.98 r = 1.2 r1(1) = 1.47
6/5
Рисунок 4
Как видно из Рисунка 4, при отходе Первого от своей оптимальной стратегии вправо, т.е. при увеличении вероятности выбора им 1-ой строки, Второй отвечает своей 1-ой чистой стратегией и риск Первого скачком увеличивается до r1(1) = 1.47, а при отходе Первого от своей оптимальной стратегии влево Второй отвечает своей 2-ой чистой стратегией и риск Первого скачком снижается до r1(2) = 0.98.
Аналогично - в отношении второго:
n
Di = S aj2 * q*j - v2
j=1
D1 = 0 * 2/5 + 4 * 3/5 – 36/25 = 24/25
D2 = 9 * 2/5 + 0 * 3/5 – 36/25 = 54/25
r2(1) = Ö 24/25 = 0.98
r2(2) = Ö 54/25 = 1.47
Зависимость риска Второго в малой окрестности его оптимальной стратегии показана на Рисунке 5.
r2(1) = 0.98 r = 1.2 r2(2) = 1.47
6/5
Рисунок 5
Как видно из Рисунка 5, при отходе Второго от своей оптимальной стратегии вправо, т.е. при увеличении вероятности выбора им 1-го столбца, Первый отвечает своей 2-ой чистой стратегией и риск Второго скачком увеличивается до r2(2) = 1.47, а при отходе Второго от своей оптимальной стратегии влево его риск скачком снижается до r2(1) = 0.98.
Величина r* = min(r1(1), r1(2), r2(1), r2(2)) - риск всей игры.
r* = min(1.47, 0.98, 0.98, 1.47) = 0.98.
С таким риском можно играть только при сотрудничестве обеих сторон. Для достижения такого риска игроки должны играть следующим образом: Первый игрок использует свою оптимальную стратегию P*(3/5, 2/5), а Второй отвечает своей 2-ой чистой стратегией, либо Второй игрок использует свою оптимальную стратегию Q*(2/5, 3/5), а Первый отвечает своей 1-й чистой стратегией.
Постановка задачи
Рассмотреть задачу о максимальном потоке в сети. Решить конкретную задачу на сети с 8-9 вершинами.
Исходные данные
Определить максимальный поток в сети, изображенной на Рисунке 6 из вершины x0 в вершину x8, где числа на дугах, снабженные стрелками, означают пропускные способности этих дуг в указанных направлениях.
Рисунок 6
Решение
Составим матрицу пропускных способностей дуг данной сети и представим сеть в матричной форме (см. Таблицу 1).
Таблица 1
|
xj xi |
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x0 |
2 |
4 |
2- |
|||||
|
x1 |
1 |
5 |
||||||
|
x2 |
3 |
|||||||
|
x3 |
+ |
5 |
1 |
6- |
||||
|
x4 |
2 |
5 |
||||||
|
x5 |
4 |
1 |
3 |
|||||
|
x6 |
2 |
8 |
||||||
|
x7 |
+ |
5 |
2 |
В качестве начального возьмем нулевой поток z0ij = 0. Найдем какой-нибудь путь, идущий из x0 в x7 по ненасыщенным дугам. Для этого в нулевой строке таблицы выберем какой-нибудь элемент cij, отличный от нуля, например c03. Из вершины x0 можно перейти в x3. Для наглядности дугу (x0, x3) проведем прямо в нулевой строке таблицы из нулевого столбца в 3-й. Теперь мы находимся в вершине x3. Чтобы зафиксировать это, сместимся по пятому столбцу до строки с тем же 3-м номером. В 3-й строке имеется 3 ненулевых элемента соответственно в 4-м, 5-м и 7-м столбцах. Это означает, что из x3 можно перейти или в x4, в x5 или в x7. Пойдем в сток x7. Этот переход изображен стрелкой в 3-й строке с началом в 3-м столбце и концом в 7-м. Таким образом, по таблице пропускных способностей дуг сети мы нашли путь, ведущий по ненасыщенным дугам из источника в сток:
m1 = [x0, x3, x7].
Теперь по таблице надо узнать пропускную способность q1 найденного пути и уменьшить пропускные способности всех дуг этого пути на q1, а симметричных им дуг – увеличить на q1. Для этого отмечаем знаком «-» числа в тех клетках, где находятся концы дуг, а числа в клетках, симметричных указанным относительно главной диагонали, отмечаем знаком «+». Пропускная способность найденного пути, очевидно, равна наименьшему среди чисел, отмеченных знаком «-» (Таблица 1).
q1 = 2
Из всех чисел, отмеченных знаком «-», вычитаем наименьшую пропускную способность q1. Получаем Таблицу 2. Это – сеть с измененными пропускными способностями дуг.
Таблица 2
|
xj xi |
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x0 |
2 |
4- |
||||||
|
x1 |
1 |
5 |
||||||
|
x2 |
+ |
3- |
||||||
|
x3 |
2 |
5 |
1 |
4 |
||||
|
x4 |
2+ |
5- |
||||||
|
x5 |
4 |
1 |
3 |
|||||
|
x6 |
2 |
8 |
||||||
|
x7 |
2 |
5+ |
2 |
Ищем новый путь, идущий из источника в сток по ненасыщенным дугам и процедуру повторяем. Получаем путь m2 и пропускную способность q2:
m2 = [x0, x2, x4, x7]
q2 = 3
Далее
Таблица 3
|
xj xi |
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x0 |
2- |
1 |
||||||
|
x1 |
+ |
1 |
5- |
|||||
|
x2 |
3 |
|||||||
|
x3 |
2 |
5 |
1 |
4 |
||||
|
x4 |
5 |
2 |
||||||
|
x5 |
4+ |
1 |
3- |
|||||
|
x6 |
2+ |
8- |
||||||
|
x7 |
2 |
8 |
2+ |
m3 = [x0, x1, x5, x6, x7]
q3 = 2
Таблица 4
|
xj xi |
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x0 |
1 |
|||||||
|
x1 |
2 |
1 |
3 |
|||||
|
x2 |
3 |
|||||||
|
x3 |
2 |
5 |
1 |
4 |
||||
|
x4 |
5 |
2 |
||||||
|
x5 |
6 |
1 |
1 |
|||||
|
x6 |
4 |
6 |
||||||
|
x7 |
2 |
8 |
4 |
Из Таблицы 4 видно, что не существует ни одного пути из источника в сток. (Из x0 можно перейти только в x2, а оттуда – обратно в x0). Следовательно, увеличить поток нельзя.
Для определения величины полученного максимального потока вычитаем из элементов Таблицы 1 соответствующие элементы Таблицы 4. Записывая только положительные из найденных разностей, получаем Таблицу 5, указывающую максимальный поток в заданной сети с величиной
w* = z37 + z47 + z67 = q1 + q2 + q3 = 7
Таблица 5
|
xj xi |
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x0 |
2 |
3 |
2 |
|||||
|
x1 |
2 |
|||||||
|
x2 |
3 |
|||||||
|
x3 |
2 |
|||||||
|
x4 |
3 |
|||||||
|
x5 |
2 |
|||||||
|
x6 |
2 |
|||||||
|
x7 |
Карандаев И.С. и др. Математические методы исследования операций в примерах и задачах: Учебное пособие / ГАУ. М., 1993, 72 с.
Карандаев И.С., Юнисов Х.Х. Прикладные задачи исследования операций. Учебное пособие для студентов всех специальностей. М.: МИУ имени Серго Орджоникидзе. – 79 с.
Математические методы принятия решений в экономике: Учебник / Под ред. В.А. Колемаева / ГУУ. – М.: ЗАО «Финстатинформ», 1999. – 386 с.
Методические указания к выполнению курсовой работы по дисциплине “Прикладная математика” / Сост.: Колемаев В.А., Карандаев И.С., В.И. Малыхин, Т.М. Гатауллин, Ю.Г. Прохоров, Х.Х. Юнисов; ГУУ, М., 2000. 73 с.
x
x
0
x
2
x
1
3
x
4
x
5
x
6
x
7
2
0
5
4
3
2
8
2
6
0
1
1
1
0
2
0
4
0
3
2
5
5
5
0