b
L
8
4.5
1
2
0.5
2/3
1/6
-1/3
4/3
5/6
1/3
Полученное решение удовлетворяет системе ограничений!
L* = 8
x*4,x*5=0 – свободные
- базисные
Решение транспортной задачи, все данные приведены ниже в таблице.
B1
B2
B3
B4
B5
ai
A1
0.09
0.12
0.14
0.1
3000
A2
0.08
0.15
0.05
0.07
6000
A3
0.06
8000
bj
1000
4000
Перед тем как приступить к решению, подсчитаем общее количество запасов и общее количество заявок . Понятно что имеем транспортную задачу с избытком заявок . Потребуем, чтобы все пункты назначения были удовлетворены в равной доле. При таком подходе задача сводится к задаче с правильным балансом: необходимо исправить поданные заявки, умножив каждую на коэффициент
k = å ai / å bj . Рассчитаем k.
Тогда получим транспортную задачу с правильным балансом.
17000
Найдем опорное решение с помощью метода северо-западного угла.
r = 3+5-1 =7
Проверим сумму по столбцам, сумму по строкам и количество базисных (заполненных) клеток.
Проверка по столбцам:
Проверка по строкам:
Количество заполненных клеток равно r =7. Найденный план является опорным.
Постараемся улучшить план перевозок
Подсчитаем цены выделенных пунктирными прямоугольниками циклов.
Цикл1
(1;1)-(1;2)-(2;2)-(2;1)
, где цена цикла
Цикл2
(2;3)-(2;4)-(3;4)-(3;3)
Для того чтобы стоимость плана уменьшилась, имеет смысл совершать перевозки только по тем циклам, цена которых отрицательна. Цена Цикла2 отрицательна, поэтому выбираем его. Цикл1 в данном случае рассматривать не будем: так как цена его положительна, поэтому план перевозок с помощью перерасчета этого цикла не улучшится.
После всех рассуждений получим следующее:
Итак, улучшаем план перевозок с помощью Цикла1. Для этого перенесем по циклу мнимальное количество груза, стоящее в отрицательной вершине.
Страницы: 1, 2, 3, 4
