ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 06.11.2023
Просмотров: 23
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Переходим к основному алгоритму симплекс-метода.
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x4 | 850 | 1/5 | 2/5 | 3/5 | 1 | 0 | 0 | 0 |
| x5 | 640 | 3/10 | 1/10 | 1/10 | 0 | 1 | 0 | 0 |
| x6 | 730 | 1/10 | 3/10 | 1/10 | 0 | 0 | 1 | 0 |
| x7 | 1000 | 2/5 | 1/5 | 1/5 | 0 | 0 | 0 | 1 |
| F(X1) | 0 | 696/5 | 1401/10 | 1397/10 | 0 | 0 | 0 | 0 |
Оптимальный план можно записать так:
x1 = 0, x2 = 0, x3 = 0, x4 = 850, x5 = 640, x6 = 730, x7 = 1000
F(X) = -1391/5*0 -1401/10*0 -1397/10*0 + 450940 = 450940
№ 2. Распределить план перевозок однотипного груза от трёх поставщиков к четырём потребителям, обеспечив минимальные затраты на перевозку.
Исходные данные представлены в таблице 2.
Таблица 2. Транспортная задача.
| | Тарифы по перемещению единицы груза, тыс. руб. | ||||
| | Потребитель1 | Потребитель2 | Потребитель2 | Потребитель4 | Возможности поставщика |
| Поставщик1 | 7 | 4 | 9 | 3 | 400 |
| Поставщик2 | 2 | 11 | 8 | 4 | 550 |
| Поставщик 3 | 3 | 8 | 6 | 5 | 300 |
| Потребности потребителя | 450 | 250 | 200 | 350 | |
Значение целевой функции равно:
F(x) = 4*50 + 3*350 + 2*450 + 11*100 + 8*100 + 6*200 = 5250
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 4; 0 + v2 = 4; v2 = 4
u2 + v2 = 11; 4 + u2 = 11; u2 = 7
u2 + v1 = 2; 7 + v1 = 2; v1 = -5
u3 + v2 = 8; 4 + u3 = 8; u3 = 4
u3 + v3 = 6; 4 + v3 = 6; v3 = 2
u1 + v4 = 3; 0 + v4 = 3; v4 = 3
v1=-5 v2=4 v3=2 v4=3
u1=0 7 4[50] 9 3[350]
u2=7 2[450] 11[100] 8 4
u3=4 3 8[100] 6[200] 5
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;3): 7 + 2 > 8; ∆23 = 7 + 2 - 8 = 1 > 0
(2;4): 7 + 3 > 4; ∆24 = 7 + 3 - 4 = 6 > 0
(3;4): 4 + 3 > 5; ∆34 = 4 + 3 - 5 = 2 > 0
max(1,6,2) = 6
Выбираем максимальную оценку свободной клетки (2;4): 4
Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 Запасы
1 7 4[50][+] 9 3[350][-] 400
2 2[450] 11[100][-] 8 4[+] 550
3 3 8[100] 6[200] 5 300
Потребности 450 250 200 350
Цикл приведен в таблице (2,4 → 2,2 → 1,2 → 1,4).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
B1 B2 B3 B4 Запасы
A1 7 4[150] 9 3[250] 400
A2 2[450] 11 8 4[100] 550
A3 3 8[100] 6[200] 5 300
Потребности 450 250 200 350
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 4; 0 + v2 = 4; v2 = 4
u3 + v2 = 8; 4 + u3 = 8; u3 = 4
u3 + v3 = 6; 4 + v3 = 6; v3 = 2
u1 + v4 = 3; 0 + v4 = 3; v4 = 3
u2 + v4 = 4; 3 + u2 = 4; u2 = 1
u2 + v1 = 2; 1 + v1 = 2; v1 = 1
v1=1 v2=4 v3=2 v4=3
u1=0 7 4[150] 9 3[250]
u2=1 2[450] 11 8 4[100]
u3=4 3 8[100] 6[200] 5
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(3;1): 4 + 1 > 3; ∆31 = 4 + 1 - 3 = 2 > 0
(3;4): 4 + 3 > 5; ∆34 = 4 + 3 - 5 = 2 > 0
max(2,2) = 2
Выбираем максимальную оценку свободной клетки (3;1): 3
Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 Запасы
1 7 4[150][+] 9 3[250][-] 400
2 2[450][-] 11 8 4[100][+] 550
3 3[+] 8[100][-] 6[200] 5 300
Потребности 450 250 200 350
Цикл приведен в таблице (3,1 → 3,2 → 1,2 → 1,4 → 2,4 → 2,1).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
B1 B2 B3 B4 Запасы
A1 7 4[250] 9 3[150] 400
A2 2[350] 11 8 4[200] 550
A3 3[100] 8 6[200] 5 300
Потребности 450 250 200 350
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 4; 0 + v2 = 4; v2 = 4
u1 + v4 = 3; 0 + v4 = 3; v4 = 3
u2 + v4 = 4; 3 + u2 = 4; u2 = 1
u2 + v1 = 2; 1 + v1 = 2; v1 = 1
u3 + v1 = 3; 1 + u3 = 3; u3 = 2
u3 + v3 = 6; 2 + v3 = 6; v3 = 4
v1=1 v2=4 v3=4 v4=3
u1=0 7 4[250] 9 3[150]
u2=1 2[350] 11 8 4[200]
u3=2 3[100] 8 6[200] 5
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Минимальные затраты составят: F(x) = 4*250 + 3*150 + 2*350 + 4*200 + 3*100 + 6*200 = 4450