Критерий оптимальности плана перевозок
-
Если среди оценок оптимальности все отрицательные, то опорный план является оптимальным и единственным.
-
Если среди оценок оптимальности есть только отрицательные и нулевые, то опорный план является оптимальным, но не единственным.
-
Если среди оценок оптимальности есть хотя бы одна положительная, то опорный план не является оптимальным.
Переход от одного опорного плана к другому производят заполнением клетки для которой нарушено условие оптимальности. Таким образом, для построения цикла перераспределения груза нужно выбирать клетку с самой большой положительной оценкой.
Замечание. Если есть несколько таких оценок, то выбирают клетку с меньшим тарифом.
Для этой выбранной клетки строим цикл перераспределения поставок. Цикл изображается ломаной линией, все углы поворота которой прямые, одна вершина его находится в выбранной клетке, а другие – в заполненных. Для перераспределения поставок в выбранной клетке ставим знак “+”, затем знаки чередуем. Среди клеток со знаком “–” выбираем наименьшее количество груза и в клетки со знаком “+” будем прибавлять это число, а в клетках со знаком “–” будем это число отнимать. В результате такого перераспределения поставок получаем новый опорный план транспортной задачи.
Замечание. Цикл перераспределения поставок может иметь различный вид, например, как на рисунке 3.
Рисунок 3 – Циклы перераспределения поставок
Замечание. Грузы, которые не принимали участие в перераспределении, переписываются без изменений.
Решение транспортной задачи рассмотрим на примере.
Пример 2.6.1. Найти оптимальный план перевозок.
-
B
A
B1
B2
B3
10
20
20
А1
20
А2
40
А3
35
Решение. Вначале необходимо проверить наличие баланса между спросом и предложением: 20 + 40 + 35 = 95; 10 + 20 + 30 = 50. Баланса нет.
Для того, чтобы данную транспортную задачу закрыть, необходимо ввести фиктивного потребителя В4 с потребностью 45 единиц груза (95 – 50 = 45) и нулевыми тарифами.
Для построения начального опорного плана транспортной задачи воспользуемся методом северо-западного угла.
Таблица 2.6.1
-
B
A
B1
B2
B3
B4
10
20
20
45
А1
20
10
10
А2
40
10
20
10
А3
35
35
В нашем случае число заполненных клеток должно быть
т + п – 1 = 3 + 4 – 1 = 6.
Все 6 клеток являются заполненными, т.е. опорный план транспортной задачи является невырожденным.
Опорный план, соответствующий таблице 1, имеет вид
.
В таблице 1 сумма затрат на перевозку составляет
z1 = 10 · 6 + 10 · 3 + 10 · 2 + 20 · 6 + 10 · 0 + 35 · 0 = 230.
Найдем оценки оптимальности для каждой клетки таблицы 1 и запишем их в таблицу 1а.
Таким образом, таблица 2.6.1 примет вид:
Таблица 2.6.2
-
B
A
B1
B2
B3
B4
ui
10
20
20
45
А1
20
– 10
+ 10
(3)
(-)
0
А2
40
(2)
– 10
20
+ 10
-1
А3
35
(5) +
(-)
(-)
– 35
1
vj
6
3
5
–1
Опорный план Х1, который соответствует таблице 2.6.2 оптимальным не является.
Для построения цикла перераспределения груза нужно выбирать клетку с самой большой положительной оценкой. В нашем случае это (А3, В1). Таким образом цикл начинается в клетке (А3, В1), затем он продолжается к клетке (А3,В4), в которой поворачивает в клетку (А2, В4), затем – в клетку (А1, В2), затем – в клетку (А1, В1), и возвращается в начальную клетку (А3, В1).
В клетке (А3, В1) ставим знак “+”, далее чередуем знаки: в клетке (А3, В4) – знак “–”, в клетке (А2, В4) – знак “+”, в клетке (А2, В2) – знак “–”, в клетке А1, В2) – знак “+”, в клетке (А1, В1) – знак “–”.
В нашем случае наименьшее количество груза в клетках со знаком “–” это 10, которое клетки со знаком “+” будем прибавлять, а от клеток со знаком “–” будем отнимать.
Количество грузов, которые не принимали участие в цикле, переписываем без изменений. В нашем случае это клетка (А2, В3).
Таким образом, таблица 2.6.3 имеет вид:
Таблица 2.6.3
-
B
A
B1
B2
B3
B4
ui
10
20
20
45
А1
20
(-)
- 20
(5) +
(1)
0
А2
40
(-)
+
0
–
20
20
-1
А3
35
10
(2)
(-)
25
-1
vj
3
3
7
1
В таблице 2.6.3 число заполненных клеток равно 5, что меньше т + п – 1 = 6, т.е. нужно заполнить пустую клетку нулем, тогда их будет 6. В клетку (А2, В2) с наименьшим тарифом 2 поставим нуль и будем считать ее заполненной.
Далее расписываем потенциалы и находим оценки оптимальности, отражая эти действия в таблице 2.6.3.
Опорный план, соответствующий таблице 2.6.3, имеет вид
.
Опорный план Х2 оптимальным не является, сумма затрат на перевозку составляет при этом
z2 = 20 · 3 + 0 · 2 + 20 · 6 + 20 · 0 + 10 · 2 + 25 · 0 = 200.
Для построения цикла перераспределения груза нужно выбирать клетку с самой большой положительной оценкой (А1, В3).
В нашем случае цикл начинается в клетке (А1, В3), затем он продолжается до клетки (А1, В2), в которой поворачивает в клетку (А2, В2), затем – в клетку (А2, В3), и возвращается в исходную клетку (А1, В3).
В клетке (А1, В3) ставим знак “+”, далее чередуем знаки: в клетке (А1, В2) – знак “–”, в клетке (А2, В2) – знак “+”, в клетке (А2, В3) – знак “–”.
В нашем случае наименьшее количество груза в клетках со знаком “–” это 20. Тогда в клетках со знаком “+” это количество груза будем прибавлять к уже имеющемуся, а в клетках со знаком “–” будем отнимать.
Грузы, которые не принимали участие в цикле, переписываются без изменений.
В нашем случае это грузы, находящиеся в клетках (А1,В3), (А2,В4), (А3,В4).
Таким образом, таблица 2.6.4 имеет вид:
Таблица 2.6.4
-
B
A
B1
B2
B3
B4
ui
10
20
20
45
А1
20
(-)
(-)
20
0
0
А2
40
(-)
20
(-)
20
0
А3
35
10
(-)
(-)
25
0
vj
2
2
2
0
В таблице 3 число заполненных клеток равно 5, что меньше 6, т.е. нужно заполнить незагруженную клетку нулем, тогда их будет 6. В клетку (А1,В4) с наименьшим тарифом 0 поставим нуль и будем считать ее заполненной.
Далее расписываем потенциалы и находим оценки оптимальности, отражая эти действия в таблице 3. Опорный план, соответствующий таблице 2, имеет вид
.
Опорный план Х3 является оптимальным, сумма затрат на перевозку в этом случае равна
z3 = 20 · 2 + 0 · 0 + 20 · 2 + 20 · 0 + 10 · 2 + 25 · 0 = 60.
Литература – [5].
- Рецензенты:
- Содержание
- 1. Программа курса Введение
- Математические основы программирования
- Общий вид задачи линейного программирования
- Методы решения общей задачи линейного программирования
- Двойственные задачи линейного программирования
- Распределительные методы
- Элементы нелинейного программирования
- Элементы теории игр
- Введение
- Классификация задач математического программирования
- 2. Математическое программирование
- 2.1. Постановка задач линейного программирования
- Алгоритм графического метода решения злп
- 2.3. Симплекс-метод решения задачи линейного программирования
- Алгоритм симплекс-метода решения злп
- Пример 2.3.1. Решить злп (2.2.1), (2.2.5) симплекс-методом.
- Критерий оптимальности опорного плана:
- Переход к следующей симплекс-таблице осуществляют по правилам:
- 2.4. Двойственная задача линейного программирования
- 2.5. Элементы теории матричных игр
- Алгоритм принципа максимина (минимакса)
- Решение. Эта матричная игра имеет размерность (3х4), т.Е. Игрок а имеет три стратегии, а игрок в – четыре. Запишем ее в нормальной форме.
- Последовательность действий при решении игры
- 2.6. Транспортная задача. Метод потенциалов
- Алгоритм метода потенциалов состоит из следующих этапов:
- Критерий оптимальности плана перевозок
- 2.7. Задача о назначениях
- Алгоритм метода Фогеля
- Алгоритм венгерского метода решения задачи о назначениях
- 2.8. Дробно-линейное программирование
- Правила решения задачи дробно-линейного программирования графическим методом
- 2.9. Целочисленное программирование
- 2.10. Параметрическое программирование
- Алгоритм решения задачи параметрического программирования
- 3. Задания для самостоятельной работы