Избыток перерабатывающей способности пунктов перевалки 450, 250 и 75 заносится в клетки фиктивной диагонали левой нижней части матрицы. Далее заполняется левая верхняя часть матрицы.
Число загруженных клеток должно быть равно (т+п-1). План, имеющий число загруженных клеток (т+п-1), является базисным. Согласно доказанной Канторовичем Л.В. теореме, оптимальный план находится среди базисных решений.
Однако, нередки случаи, когда сумма ресурсов равна сумме потребностей не только по матрице в целом, но и по части столбцов и строк, а поэтому число загруженных клеток получается меньше, чем (т+п-1). Для последующих действий надо дополнить число занятых клеток до (т+п—1). Для этого назначаем дополнительные корреспонденции бесконечно малой величины, обозначенные «0».
«Искусственный ноль» вводится в одну из клеток матрицы:
- клетку на пересечении строки, содержащей последнюю за полненную клетку, со столбцом, содержащим признак вырождения;
- клетку на пересечении столбца, содержащего последнюю за груженную клетку, со строкой, содержащей признак вырождения.
В таблице 4 загруженных клеток 9, поэтому необходимо ввести два «искусственных нуля» (в клетки 7?i772 и Я\Щ).
По теореме, доказанной Канторовичем Л.В., условия оптимальности плана формулируются следующим образом:
Допустимый план оптимален тогда и только тогда, когда каждому поставщику Rt (i=l,2,...,m) и каждому потребителю Pj (j=l,2,...,n) могут быть присвоены некоторые числа Utи Vj, называемые потенциалами, для которых соблюдаются условия:
Для определения значений потенциалов строк и столбцов из потенциала одной произвольной строки или столбца пользуются равенствами из выражения (12):
15
Начальный потенциал строки или столбца выбирается произвольно, но, чтобы не получить отрицательных потенциалов, рекомендуется принимать его для строчки с наибольшим показателем оптимальности в загруженной клетке.
Задаемся потенциалом первой строки Ј/i=0. Затем по правилу оптимизации определяем остальные потенциалы (через загруженные клетки); например: при U\=0 потенциал V\ определяется:
Us= V3 ~ с53 = 50 - ° = 50 и Т-Д-
После определения всех потенциалов проверяем оптимальность плана по условию (11).
Величиной нарушения будем считать
H = Vj- Ut- cij9т.е. Н>0 (13)
Наличие хотя бы одного нарушения свидетельствует о том, что проверяемый план не оптимален и должен быть улучшен. Улучшение целесообразно начинать после просмотра всех свободных клеток с клетки, имеющей наибольшее нарушение.
Единственное нарушение равное Н31=20,5 имеем в клетке R]P<$. Выявив величину нарушения, вводим поправки в ранее принятый план путем изменения значений Ху.
Для этого из выбранной клетки с нарушением проводим замкнутую ломаную линию, двигаясь аналогично ходу шахматной ладьи, при этом изменение движения производим в загруженных клетках на угол 90°. Эта линия носит название контура. Там где линия меняет направление, корреспонденции подлежат изменению. Поставим знаки «+» и «—» у вершины контура, начиная с «+» в клетке с нарушением («+» означает, что корреспонденция должна быть увеличена , а «-» - уменьшена).
Величина потока улучшения должна быть равна минимальной корреспонденции со знаком «-», т.е. xyjl=minХу(-). Такая корреспонденция у нас в клетке R2Pф=25. Перемещаем эту величину по контуру и получаем новый план (таблица 5), который не имеет нарушений и является оптимальным.
16
Таблица 5 — Результат первой итерации (оптимальный план)
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.