Задание №3
Составить такой план перевозок, при котором общая себестоимость перевозок является минимальной. Задачу решить методом потенциалов.
Пусть
–
количество сырья вида
,
которое нужно доставить -ому предприятию,
а
– стоимость перевозки сырья
-ому
предприятию. Тогда математическая
модель основной задачи будет иметь вид:
.
Составляем
двойственную задачу. Вводим дополнительные
переменные
,
,
– потенциалы поставщиков,
,
,
,
,
– потенциалы потребителей. Система
ограничений двойственной задачи будет
иметь вид:
; 
; 
;
.
Составляем начальный план методом двойного предпочтения:
Проверяем
вырожденный ли план:
m+n-1=4+3-1=6,
количество заполненных клеток – 6,
6=6, следовательно, план невырожденный.
Проверяем оптимальность опорного плана:
Условие
выполняется для всех заполненных клеток.
Опорный
план является оптимальным, так все
условие
выполняется для всех незаполненных
клеток таблицы.
Общая себестоимость перевозок составит:
Задание №4
Решить задачи целочисленного программирования геометрическим методом
Формируем уравнения граничных прямых и отображаем область допустимых решений.
Строим
линию уровня и вектор направления,
который указывает направление возрастания
целевой функции F=3
–2
.
Двигаем прямую до последнего касания области допустимых решений.
Прямая
F пересекает область в точке A.
Так как точка A
получена в результате пересечения
прямых
,
то ее координаты удовлетворяют уравнениям
этих прямых:
Решив
систему уравнений, получим:
= 2.5,
= 0.
Решение получилось не целое.
Отметим на графике возможные целые решения задачи.
Перемещение линии уровня целевой функции показывает, что наибольшее значение она примет в точке (2, 0).
Задание №5
Целочисленное линейное программирование
Составим математическую модель.
Пусть
– объем производства изделий (
где
–
количество видов изделий,
).
То есть,
– количество изделий первого вида,
– количество изделий второго вида и
т.д.
Получим
задачу максимизации F=3.7
+3
+6
+2
при условиях
Приводим поставленную задачу к канонической форме и решаем симплексным методом:
=>
|
№ |
Базис |
|
|
|
|
|
|
|
|
|
|
0 |
|
5 |
8 |
3 |
8 |
1 |
0 |
0 |
85 |
28 1/3 |
|
|
7 |
6 |
9 |
3 |
0 |
1 |
0 |
100 |
11 1/9 (min) |
|
|
|
3 |
7 |
10 |
5 |
0 |
0 |
1 |
150 |
15 |
|
|
|
-3.7 |
-3 |
-6 |
-2 |
0 |
0 |
0 |
|
|
Получим первый опорный план: X1 = (0,0,0,0,85,100,150). Он неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
|
№ |
Базис |
|
|
|
|
|
|
|
|
|
|
1 |
|
2.67 |
6 |
0 |
7 |
1 |
-0.33 |
0 |
51.67 |
|
|
|
0.78 |
0.67 |
1 |
0.33 |
0 |
0.11 |
0 |
11.11 |
|
|
|
|
-4.78 |
0.33 |
0 |
1.67 |
0 |
-1.11 |
1 |
38.89 |
|
|
|
|
0.97 |
1 |
0 |
0 |
0 |
0.67 |
0 |
66 2/3 |
|
Конец итераций: индексная строка не содержит отрицательных элементов – найден оптимальный план: X = (0,0,11.11,0,51.67,0,38.89).
Переменная
принимает дробное значение (11.11). Поэтому
к системе F=3.7
+3
+6
+2
добавляется неравенство.
0.11–
0.78
–
0.67
–
0.33
–
0.11
0
Вводим
и записываем: 0.11–
0.78
–
0.67
–
0.33
–
0.11
+
=0
|
№ |
Базис |
|
|
|
|
|
|
|
|
|
|
|
2 |
|
2.67 |
6 |
0 |
7 |
1 |
-0.33 |
0 |
0 |
51.67 |
8.6 |
|
|
0.78 |
0.67 |
1 |
0.33 |
0 |
0.11 |
0 |
0 |
11.11 |
16.6 |
|
|
|
-4.78 |
0.33 |
0 |
1.67 |
0 |
-1.11 |
1 |
0 |
38.89 |
117.8 |
|
|
|
0.78 |
0.67 |
0 |
0.33 |
0 |
0.11 |
0 |
-1 |
0.11 |
0.16 (min) |
|
|
|
0.97 |
1 |
0 |
0 |
0 |
0.67 |
0 |
0 |
66 2/3 |
|
|
№ |
Базис |
|
|
|
|
|
|
|
|
|
|
|
3 |
|
-4,32 |
0 |
0 |
4,04 |
1 |
-1,32 |
0 |
8,96 |
50,68 |
|
|
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
11 |
|
|
|
|
-5,16 |
0 |
0 |
1,51 |
0 |
-1,16 |
1 |
0,49 |
38,84 |
|
|
|
|
1,16 |
1 |
0 |
0,49 |
0 |
0,16 |
0 |
-1,49 |
0,16 |
0.14 |
|
|
|
-0,19 |
0 |
0 |
-0,49 |
0 |
0,51 |
0 |
1,49 |
66,50 |
|
|
№ |
Базис |
|
|
|
|
|
|
|
|
|
|
|||||||||
|
5 |
|
-13,88
|
-8,21 |
0 |
0
|
1 |
-2,66 |
0 |
21,2 |
49,34 |
|
|||||||||
|
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1,00 |
11 |
|
||||||||||
|
|
-8,73 |
-3,06 |
0 |
0 |
0 |
-1,67 |
1 |
5,06 |
38,33 |
|
||||||||||
|
|
2,36 |
2,03 |
0 |
1 |
0 |
0,33 |
0 |
-3,03 |
0,33 |
|
||||||||||
|
|
0,97 |
1 |
0 |
0 |
0 |
0,67 |
0 |
0,00 |
66,67 |
|
||||||||||
|
№ |
Базис |
|
|
|
|
|
|
|
|
|
|
|
4 |
|
0 |
3,71 |
0 |
5,87 |
1 |
-0,70 |
0 |
3,42 |
51,29 |
8,73 |
|
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
11 |
|
|
|
|
0 |
4,43 |
0 |
3,69 |
0 |
-0,43 |
1 |
-6,12 |
39,56 |
10,71 |
|
|
|
1 |
0,85 |
0 |
0,42 |
0 |
0,14 |
0 |
-1,28 |
0,14 |
0,33 (min) |
|
|
|
0 |
0,16 |
0 |
-0,41 |
0 |
0,53 |
0 |
1,24 |
66,52 |
|
Оптимальный план: X = (0, 0,11,0.33,49.34,0,38.33).
Переменная
принимает дробное значение (0.33). Поэтому
к системе
добавляется неравенство.
0,33–2,36
–2,03
–0,33
–(–3,03
0
0.16–
1.16
–
0.49
–
0.16
–(–1.49
0
|
№ |
Базис |
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
-13,88
|
-8,21 |
0 |
0
|
1 |
-2,66 |
0 |
21,2 |
0 |
49,34 |
|
|
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1,00 |
0 |
11 |
|
|
|
|
-8,73 |
-3,06 |
0 |
0 |
0 |
-1,67 |
1 |
5,06 |
0 |
38,33 |
|
|
|
|
2,36 |
2,03 |
0 |
1 |
0 |
0,33 |
0 |
-3,03 |
0 |
0,33 |
1 |
|
|
|
0,36 |
0,03 |
0 |
0 |
0 |
0,33 |
0 |
0,97 |
-1 |
0,33 |
1 |
|
|
|
0,97 |
1 |
0 |
0 |
0 |
0,67 |
0 |
0 |
0 |
66,67 |
|
Вводим
и записываем: 0,33–0,36
–0,03
–0,33
–0,97
0
|
№ |
Базис |
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
-10,9 |
-7,96 |
1 |
0 |
1 |
0 |
0 |
29,01 |
-8,06 |
52 |
|
|
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
11 |
|
|
|
|
-6,9 |
-2,9 |
0 |
0 |
0 |
0 |
1 |
9,96 |
-5,06 |
40 |
|
|
|
|
2 |
2 |
0 |
1 |
0 |
0 |
0 |
-4 |
1 |
0 |
|
|
|
|
1,09 |
0,09 |
0 |
0 |
0 |
1 |
0 |
2,93 |
-3,03 |
1 |
|
|
|
|
0,23 |
0,93 |
0 |
0 |
0 |
0 |
0 |
1,96 |
2,03 |
66 |
|
Получен оптимальный план. Все значения являются целыми.
=3.7*0+3*0+6*11+2
=66