- •Линейная производственная задача
- •Двойственная задача
- •Задача о «расшивке узких мест производства»
- •Транспортная задача линейного программирования
- •Динамическое программирование. Распределение капитальных вложений
- •Матричная модель производственной программы предприятия
- •Матричная модель производственной программы предприятия
Оглавление.
Линейная производственная задача.(3)
Двойственная задача.(5)
Задача о «расшивке узких мест производства».(6)
Транспортная задача линейного программирования.(7)
Динамическое программирование. Распределение капитальных вложений.(10)
Матричная игра как модель конкуренции и сотрудничества.(12)
Матричная модель производственной программы предприятия.(14)
Список литературы.(17)
Линейная производственная задача
Предприятие выпускает 4 вида продукции, используя для этого три вида ресурсов. Известна технологическая матрица A, в которой каждый элемент aij означает необходимое количество i-го ресурса для выпуска j-го вида продукции:
-
3
2
0
3
А =
0
1
4
2
1
3
5
0
Известен вектор Bобъемов ресурсов, каждый элемент которогоbiозначает предельное количествоi-го ресурса для выпуска всего объема продукции:
-
168
В =
60
112
Также известен вектор удельной прибыли C, элементы которого cjозначают прибыль от производства единицы продукции j-го вида:
-
С =
18
19
8
5
Требуется составить производственную программу, обеспечивающую предприятию наибольшую прибыль при имеющихся ограниченных ресурсах.
Решение
Математическая модель задачи: найти производственную программу
(х1, х2, х3, х4),
максимизирующую прибыль
Z = 18 * х1+ 19 * х2+ 8 * х3+ 5 * х4
при ограничениях по ресурсам
-
3 * х1
2 * х2
+
+
3 * х4
<=
168
+
1 * х2
+
4 * x3
+
2 * х4
<=
60
(1)
1 * х1
+
3 * х2
5 * x3
+
<=
112
x1>= 0; x2>= 0; x3>= 0; x4>= 0
Введя дополнительные неотрицательные неизвестные х5, х6, х7, решаем полученную задачу симплексным методом (методом направленного перебора базисных допустимых решений) (см. Таблицу 1).
Таблица 1
|
|
|
|
18 |
19 |
8 |
5 |
0 |
0 |
0 |
|
C |
Базис |
Hi |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
|
0 |
х5 |
168 |
3 |
2 |
0 |
3 |
1 |
0 |
0 |
|
0 |
х6 |
60 |
0 |
1 |
4 |
2 |
0 |
1 |
0 |
|
0 |
х7 |
112 |
1 |
3 |
5 |
0 |
0 |
0 |
1 |
|
|
- |
0 |
-18 |
-19 |
-8 |
-5 |
0 |
0 |
0 |
|
0 |
х5 |
280/3 |
7/3 |
0 |
-10/3 |
3 |
1 |
0 |
-2/3 |
|
0 |
х6 |
68/3 |
-1/3 |
0 |
7/3 |
2 |
0 |
1 |
-1/3 |
|
19 |
х2 |
112/3 |
1/3 |
1 |
5/3 |
0 |
0 |
0 |
1/3 |
|
|
- |
2128/3 |
-35/3 |
0 |
71/3 |
-5 |
0 |
0 |
19/3 |
|
18 |
х1 |
40 |
1 |
0 |
-10/7 |
9/7 |
3/7 |
0 |
-2/7 |
|
0 |
х6 |
36 |
0 |
0 |
39/21 |
23/21 |
1/7 |
1 |
-3/7 |
|
19 |
х2 |
24 |
0 |
1 |
15/7 |
-3/7 |
-1/7 |
0 |
3/7 |
|
|
- |
1176 |
0 |
0 |
7 |
10 |
5 |
0 |
3 |
Как видно из последней симплексной таблицы, оптимальная производственная программа имеет вид
х1= 40, х2= 24, х3= 0, х4= 0,
а максимальная прибыль равна
Zmax= 1176
При этом 1-й и 3-й ресурсы будут исчерпаны полностью (х5=0, х7=0), а 2-й ресурс будет иметь остаток х6= 36 единиц.