оптимальных значениях x1=0, x2=4, x3=2, x4=0, x5=0, x6=0 целевая функция Z(x) принимает максимальное значение: Z (max) = 10.
Результаты решения задачи с помощью макроса MS Excel «Поиск решение» представлены в таблице 3.4:
Таблица 3.4 – Результаты решения
Уравнения |
Коэффициенты при переменных |
Контроль ограничений |
Ограничения |
||
1 |
2 |
1 |
-1 |
2 |
2 |
2 |
2 |
-1 |
5 |
6 |
6 |
3 |
8 |
2 |
2 |
12 |
12 |
Коэф-ты целевой функции |
1 |
2 |
1 |
||
0 |
4 |
2 |
10 |
Вывод: решив задачу при помощи симплексных преобразований, мы пришли к оптимальному решению, т. е. когда в индексной строке отсутствуют отрицательные значения и это решение совпало с решением, полученным с помощью макроса MC Excel «Поиск решение».
Условие:
Z = x1-2x2-x3 → max;
Z =- x1+2x2+x3 +0x4+0x5+0x6+Mx7+Mx8+Mx9→ min;
где - базисные переменные
- искусственные базисные переменные.
Решение производим с помощью таблиц (4.1-4.5) симплексным методом:
Таблица 4.1 – Итерация№1
Ci |
Базис |
Cj |
-1 |
+2 |
+1 |
0 |
0 |
0 |
M |
M |
M |
План |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
||
M |
X7 |
4 |
3 |
1 |
1 |
-1 |
0 |
0 |
1 |
0 |
0 |
M |
X8 |
6 |
2 |
3 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
M |
X9 |
1 |
1 |
-2 |
0 |
0 |
0 |
+1 |
0 |
0 |
1 |
11M |
6M+1 |
2M-2 |
M-1 |
(-)M |
(-)M |
(-)M |
0 |
0 |
0 |
Таблица 4.2 – Итерация№2
Ci |
Базис |
Cj |
-1 |
+2 |
+1 |
0 |
0 |
0 |
M |
M |
План |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
||
M |
X7 |
1 |
0 |
7 |
1 |
-1 |
0 |
-3 |
1 |
0 |
M |
X8 |
4 |
0 |
7 |
0 |
0 |
-1 |
-2 |
0 |
1 |
-1 |
X1 |
1 |
1 |
-2 |
0 |
0 |
0 |
+1 |
0 |
0 |
5M-1 |
0 |
14M |
M-1 |
(-)M |
(-)M |
-5M-1 |
0 |
0 |
Таблица 4.3 – Итерация№3
Ci |
Базис |
Cj |
-1 |
+2 |
+1 |
0 |
0 |
0 |
M |
План |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X8 |
||
2 |
X2 |
1/7 |
0 |
1 |
1/7 |
- 1/7 |
0 |
-3/7 |
1/7 |
M |
X8 |
3 |
0 |
0 |
-1 |
1 |
-1 |
1 |
-1 |
-1 |
X1 |
9/7 |
1 |
0 |
2/7 |
- 2/7 |
0 |
1/7 |
2/7 |
3M-1 |
0 |
0 |
(-)M-1 |
M |
(-)M |
(-)M+1 |
(-)2M |
Таблица 4.4 – Итерация№4
Ci |
Базис |
Cj |
-1 |
+2 |
+1 |
0 |
0 |
0 |
План |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
||
2 |
X2 |
4/7 |
0 |
1 |
0 |
0 |
- 1/7 |
-2/7 |
0 |
X4 |
3 |
0 |
0 |
-1 |
1 |
-1 |
1 |
-1 |
X1 |
15/7 |
1 |
0 |
0 |
0 |
- 2/7 |
3/7 |
-1 |
0 |
0 |
-1 |
0 |
0 |
-1 |
При оптимальных значениях x1=15/7, x2=4/7, x3=0 целевая функция z(x) принимает максимальное значение. Z (max) = 1.
Результаты решения задачи с помощью макроса MC Excel «Поиск решение» представлены в таблице 4.6:
Таблица 4.6 – Результаты решения
Уравнения |
Коэффициенты при переменных |
Контроль ограничений |
Ограничения |
||
1 |
3 |
1 |
1 |
4 |
4 |
2 |
2 |
3 |
0 |
6 |
6 |
3 |
-1 |
2 |
0 |
-1 |
-1 |
Коэффициент в целевой функции |
1 |
-2 |
-1 |
||
15/7 |
4/7 |
0 |
1 |
Вывод: при решении симплексным методом с искусственным базисом получили оптимальное значение, которое соответствует отсутствию положительных значений в индексной строке и эти полученные значения совпадают с решением при помощи макроса MC Excel «Поиск решение».
Используя уже готовую дескриптивную модель, содержащую переменные и ограничения модели, требуется сформулировать целевую функцию оптимизационной модели.
При проектировании участка комплексной механизации погрузочно-разгрузочных работ прокатного цеха были выбраны два варианта строительства склада, различных по конструктивным решениям. На строительстве используется два одинаковых экскаватора и десять одинаковых кранов. Известны затраты машино-смен на строительство 10 м2 склада (приведены в таблице). Требуется определить площадь строительства складов каждого типа, если продолжительность работ по проекту составляет 200 дней при двухсменной работе.
Определить площадь строительства складов каждого типа так, чтобы суммарная площадь была максимальной.
Таблица 5.1 – Начальные условия
Тип склада |
Затраты машино-смен на строительство 10 м2 склада |
|
экскаваторов |
кранов |
|
1 |
0,2 |
2 |
2 |
0,3 |
1 |
Пусть x1 – площадь 1-го склада, x2 – площадь 2-го склада.
Составим систему уравнений:
0,02 x1 + 0,03 x2 £ 800;
0,2 x1 + 0,1 x2 £ 4000.
Z= x1+ x2 → max;
Z – целевая функция, показывающая максимальную суммарную площадь складов.
Результаты решения представлены в таблице 5.2:
Таблица 5.2 – Результаты решения
Тип склада |
Затраты машино-смен на строительство 1 м2 |
Кол-во экскаваторов |
Кол-во кранов |
Кол-во смен |
|
экскаваторов |
кранов |
||||
1 |
0,02 |
0,2 |
2 |
10 |
400 |
2 |
0,03 |
0,1 |
2 |
10 |
400 |
Площадь складов |
Ограничения |
Контроль ограничений |
Плановые затраты машино-смен |
||
X1 |
X2 |
||||
20000 |
26667 |
1200 |
800 |
экскаваторов |
|
0 |
4000 |
кранов |
|||
Суммарная площадь складов |
46667 |
При оптимальных значений переменных x1=20000 м2 и x2=26667 м2 целевая функция z(x) достигает максимального значения и равна 46667 м2
Интерпретация полученных результатов:
Определили площадь 1-го склада равную 20000 м2 и 2-го равную 26667м2 при соответствующих затратах машино-смен и в итоге получили суммарную площадь обоих складов, которая соответствует максимуму.
Вывод: Поскольку система уравнений, описывающая условия дескриптивной модели, имеет дополнительные ограничения и содержит целевую функцию то найденные значения переменных, являются оптимальным решением данной системы.
Требуется найти объемы поставок от каждого поставщика каждому потребителю, чтобы суммарные затраты на все перевозки были минимальными.
Условие:
Ai =137 122 103 105 100
Bj = 102 115 115 121
Таблица 6.1 – Тарифы на перевозку
Cij= |
16 |
4 |
20 |
6 |
3 |
22 |
8 |
10 |
|
19 |
9 |
21 |
13 |
|
2 |
16 |
6 |
5 |
|
3 |
2 |
11 |
8 |
Математическая модель:
Целевая функция:
Определение типа задачи:
;
Исходя из того, что продукция производится больше, чем потребляется, следовательно, задачу следует привести к закрытому типу, добавив фиктивного потребителя, как это показано на таблице 6:2.
Таблица 6.2 – Начальный план
39 |
27 |
13 |
5 |
0 |
||||||||
-23 |
16 |
4 |
20 |
30 |
6 |
24 |
0 |
23 |
137 |
|||
102 |
35 |
|||||||||||
-5 |
3 |
-31 |
22 |
8 |
10 |
10 |
0 |
5 |
122 |
|||
80 |
42 |
|||||||||||
8 |
19 |
-28 |
9 |
-26 |
21 |
13 |
0 |
-8 |
103 |
|||
73 |
30 |
|||||||||||
0 |
2 |
-37 |
16 |
-11 |
6 |
-7 |
5 |
0 |
105 |
|||
91 |
14 |
|||||||||||
0 |
3 |
-36 |
2 |
-25 |
11 |
-2 |
8 |
3 |
0 |
100 |
||
100 |
||||||||||||
105 |
115 |
115 |
121 |
114 |
||||||||
Fн(x) = 16 * 102 + 4 * 35 + 22 * 80 + 8 * 42 + 21 * 73 + 13 * 30 + 5 * 91 + 0 * 14 + 0 * 100 = 6246
Следующий этап, представленный на таблицах 6.3-6.10, заключается в составлении такого плана перевозок, чтобы суммарные затраты на все перевозки были минимальны.
Таблица 6.3 – Цикл №1
2 |
-10 |
-24 |
5 |
0 |
||||||||
14 |
16 |
4 |
20 |
30 |
6 |
-13 |
0 |
-14 |
137 |
|||
29 |
108 |
|||||||||||
32 |
3 |
-31 |
22 |
8 |
10 |
-27 |
0 |
-32 |
122 |
|||
7 |
115 |
|||||||||||
8 |
19 |
9 |
9 |
11 |
21 |
37 |
13 |
0 |
-8 |
103 |
||
103 |
||||||||||||
0 |
2 |
16 |
26 |
6 |
30 |
5 |
0 |
105 |
||||
73 |
18 |
14 |
||||||||||
0 |
3 |
1 |
2 |
12 |
11 |
35 |
8 |
3 |
0 |
100 |
||
100 |
||||||||||||
105 |
115 |
115 |
121 |
114 |
||||||||
F(x) = 3545
Таблица 6.4 – Цикл №2
16 |
4 |
-10 |
6 |
14 |
||||||||
0 |
16 |
4 |
20 |
30 |
6 |
0 |
-14 |
137 |
||||
11 |
108 |
18 |
||||||||||
18 |
3 |
-31 |
22 |
8 |
10 |
-14 |
0 |
-32 |
122 |
|||
7 |
115 |
|||||||||||
7 |
19 |
-4 |
9 |
-2 |
21 |
24 |
13 |
0 |
-21 |
103 |
||
103 |
||||||||||||
-14 |
2 |
16 |
26 |
6 |
30 |
5 |
13 |
0 |
105 |
|||
91 |
14 |
|||||||||||
-14 |
3 |
1 |
2 |
12 |
11 |
35 |
8 |
16 |
0 |
100 |
||
100 |
||||||||||||
105 |
115 |
115 |
121 |
114 |
||||||||
F(x) = 3311
Таблица 6.5 – Цикл №3
2 |
11 |
-3 |
13 |
0 |
||||||||
-7 |
16 |
21 |
4 |
20 |
30 |
6 |
0 |
7 |
137 |
|||
108 |
29 |
|||||||||||
11 |
3 |
-10 |
22 |
8 |
10 |
-14 |
0 |
-11 |
122 |
|||
7 |
115 |
|||||||||||
0 |
19 |
17 |
9 |
-2 |
21 |
24 |
13 |
0 |
103 |
|||
92 |
11 |
|||||||||||
0 |
2 |
16 |
5 |
6 |
9 |
5 |
-8 |
0 |
105 |
|||
102 |
3 |
|||||||||||
0 |
3 |
1 |
2 |
-9 |
11 |
14 |
8 |
-5 |
0 |
100 |
||
100 |
||||||||||||
105 |
115 |
115 |
121 |
114 |
||||||||
F(x) = 3080
Таблица 6.6 – Цикл №4
2 |
2 |
-12 |
4 |
0 |
||||||||
2 |
16 |
12 |
4 |
20 |
30 |
6 |
0 |
-2 |
137 |
|||
16 |
121 |
|||||||||||
20 |
3 |
-19 |
22 |
8 |
10 |
-14 |
0 |
-20 |
122 |
|||
7 |
115 |
|||||||||||
0 |
19 |
17 |
9 |
7 |
21 |
33 |
13 |
9 |
0 |
103 |
||
103 |
||||||||||||
0 |
2 |
16 |
14 |
6 |
18 |
5 |
1 |
0 |
105 |
|||
102 |
3 |
|||||||||||
0 |
3 |
1 |
2 |
11 |
23 |
8 |
4 |
0 |
100 |
|||
92 |
8 |
|||||||||||
105 |
115 |
115 |
121 |
114 |
||||||||
F(x) = 2252
Таблица 6.7 – Цикл №5
2 |
2 |
8 |
4 |
0 |
||||||||
2 |
16 |
12 |
4 |
20 |
10 |
6 |
0 |
-2 |
137 |
|||
16 |
121 |
|||||||||||
0 |
3 |
1 |
22 |
20 |
8 |
10 |
6 |
0 |
122 |
|||
115 |
7 |
|||||||||||
0 |
19 |
17 |
9 |
7 |
21 |
13 |
13 |
9 |
0 |
103 |
||
103 |
||||||||||||
0 |
2 |
16 |
14 |
6 |
-2 |
5 |
1 |
0 |
105 |
|||
102 |
3 |
|||||||||||
0 |
3 |
1 |
2 |
11 |
3 |
8 |
4 |
0 |
100 |
|||
99 |
1 |
|||||||||||
105 |
115 |
115 |
121 |
114 |
||||||||
F(x) = 2112
Таблица 6.8 – Цикл №6
4 |
2 |
8 |
4 |
0 |
||||||||
2 |
16 |
10 |
4 |
20 |
10 |
6 |
0 |
-2 |
137 |
|||
16 |
121 |
|||||||||||
0 |
3 |
-1 |
22 |
20 |
8 |
10 |
6 |
0 |
122 |
|||
112 |
10 |
|||||||||||
0 |
19 |
15 |
9 |
7 |
21 |
13 |
13 |
9 |
0 |
103 |
||
103 |
||||||||||||
-2 |
2 |
16 |
16 |
6 |
5 |
3 |
0 |
2 |
105 |
|||
102 |
3 |
|||||||||||
0 |
3 |
-1 |
2 |
11 |
3 |
8 |
4 |
0 |
100 |
|||
99 |
1 |
|||||||||||
105 |
115 |
115 |
121 |
114 |
||||||||
F(x) = 2106
Таблица 6.9 – Цикл №7
3 |
2 |
8 |
4 |
0 |
||||||||
2 |
16 |
11 |
4 |
20 |
10 |
6 |
0 |
-2 |
137 |
|||
16 |
121 |
|||||||||||
0 |
3 |
22 |
20 |
8 |
10 |
6 |
0 |
122 |
||||
102 |
10 |
10 |
||||||||||
0 |
19 |
16 |
9 |
7 |
21 |
13 |
13 |
9 |
0 |
103 |
||
103 |
||||||||||||
-2 |
2 |
1 |
16 |
16 |
6 |
5 |
3 |
0 |
2 |
105 |
||
105 |
||||||||||||
0 |
3 |
0 |
2 |
11 |
3 |
8 |
4 |
0 |
100 |
|||
99 |
1 |
|||||||||||
105 |
115 |
115 |
121 |
114 |
||||||||
F(x) = 2004
Таблица 6.10– Оптимальный план грузоперевозок
3 |
4 |
8 |
6 |
0 |
||||||||
0 |
16 |
13 |
4 |
20 |
12 |
6 |
0 |
137 |
||||
15 |
121 |
1 |
||||||||||
0 |
3 |
22 |
18 |
8 |
10 |
4 |
0 |
122 |
||||
102 |
10 |
10 |
||||||||||
0 |
19 |
16 |
9 |
5 |
21 |
13 |
13 |
7 |
0 |
103 |
||
103 |
||||||||||||
-2 |
2 |
1 |
16 |
14 |
6 |
5 |
1 |
0 |
2 |
105 |
||
105 |
||||||||||||
-2 |
3 |
2 |
2 |
11 |
5 |
8 |
4 |
0 |
2 |
100 |
||
100 |
||||||||||||
105 |
115 |
115 |
121 |
114 |
||||||||
F(x) = 4*15 + 6*121 + 0*1 + 3*102 + 8*10 + 0*10 + 0*103 + 6*105 + 2*100 = 2002
Т. к. не осталось ни одной положительной сдвижки, то F=2002 – оптимальный план перевозок.
Результаты решения задачи с помощью макроса MC Excel «Поиск решение
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.