Исходя из того, что все свободные члены положительны, можно сделать вывод о том принятое решение является опорным.
Далее нужно выбрать разрешающий элемент. В качестве разрешающего столбца целесообразно принять столбец x1, так как коэффициент при x1 в целевой функции меньше коэффициента при x2. Разрешающей строкой будет строка x5, так как отношение свободного члена этой строки к коэффициенту при x1 минимально. Отметим найденный разрешающий элемент в таблице, а также заполним необходимые клетки:
bi
x1
x2
L
1
-1
-3
x3
2
x4
x5
Перерисуем таблицу с учётом замены x2 на x3:
-4
3
Коэффициент при х2 в целевой функции отрицателен, значит необходимо произвести ещё одну замену. В качестве разрешающей строки примем x3. Таким образом, разрешающим будет элемент, стоящий на пересечении строки x3 и столбца x2.
12
4
-6
-2
В итоге получим:
14
5
-5
0
Коэффициенты при свободных переменных в целевой функции положительны, значит, найденное решение является оптимальным.
Ответ:
x1=4
x2=3
x3=0
x4=-5
x5=0
L=14
Условие задачи задано в виде транспортной таблицы:
ПН
ПО
B1
B2
B3
запасы
A1
50
15
10
300
A2
21
30
20
100
A3
18
40
25
200
A4
23
22
800
A5
32
45
заявки
500
Применим к задаче метод «Северо-Западного угла». Для этого заполним таблицу начиная с левого верхнего угла без учёта стоимости перевозок:
600
В таблице заполнено n+m-1=7 клеток, значит найденное решение является опорным. Далее необходимо улучшить план перевозок в соответствии со стоимостями доставки грузов. Для этого используем циклические перестановки в тех циклах, где цена отрицательна.
В данной таблице в верхней части ячейки указана стоимость перевозки, а в нижней количество перевозимого груза. Прямоугольником выделен отрицательный цикл γ1=25+22-40-12=-5. Минимальное значение перевозок, стоящих в отрицательных вершинах равно k1=100. В итоге получим уменьшение стоимости перевозки:
Страницы: 1, 2, 3
