Файл: Тихомиров В.И. Линейное программирование в организации и планировании путевого хозяйства конспект лекций для студентов специальности Стр-во ж. д., путь и путевое хоз-во учеб. пособие.pdf

столбец исключаем из рассмотрения. В оставшейся матрице опять находим минимальный элемент. Он находится в клет­ ке 2.4. В эту клетку помещаем максимум перевозки — 15 еди­ ниц. Вторую строку исключаем из рассмотрения. Процесс пов­ торяем до тех пор, пока не распределим весь объем перевозок.

Общая стоимость по данному плану получилась: 2ММ= = 905 единиц.

мечены двумя знаками— XX. В данном случае такими клет­ ками являются 3.3; 2.4; 4.6; 5.5. Помещаем в эти клетки мак­ симально возможную корреспонденцию. Остальные распреде­ ляем в клетках с одним знаком, а также в неотмеченных с воз­ можно меньшей стоимостью, соблюдая при этом баланс от­ правления и прибытия.

Суммарная стоимость перевозок по этому плану составляет 2Дп = 905 единиц. Получилось совпадение со стоимостью пе­ ревозок по плану, построенному методом минимального эле­ мента матриц. Это случайное совпадение.

Сравнение методов построения опорного плана

При решении задач вручную можно выбрать любой из опи­ санных методов построения опорного плана. Однако следует отдать предпочтение методу наименьшей стоимости по столб­ цам (строкам). Этот метод прост и хорошо поддается авто­ матизации.

84

что им следовало. Однако, число занятых клеток равно 8 вместо 10. Следовательно, необходимо назначить две нулевые тщставки. Для выбора клеток'следует обратиться к записямсправа матрицы: третья строка вычеркивалась одновременно с первым столбцом, пятая строка — с пятым столбцом. Выбе­ рем столбец, где находится корреспонденция, назначенная в последнюю очередь, и найдем клетки пятой и третьей строк; или выберем строку последнего распределения и в ней найдем

Остановимся на первых двух наиболее эффективных методах.

Метод потенциалов

Метод потенциалов — первый точный метод решения транспортной задачи — был предложен в 1949 г. Л. В. Канто­ ровичем и М. К- Гавуриным.

Покажем нахождение оптимального плана методом потен­

86

Алгоритм решения задачи следующий:

1.По одному из известных методов находим опорный план ;{в данном случае по методу минимального элемента столбца).

2.Определяем потенциалы строи и столбцов.

ciJ-

Задача заключается в отыскивании такой системы потен­ циалов, при которой соблюдаются условия оптимальности плана:

при % > 0.

Для определения значения потенциалов столбца и строки составляем уравнение вида V] — ut = Сц для каждой занятой клетки

В этих десяти уравнениях содержится одиннадцать неиз­ вестных:

« 1 , * > 2 , V3t. V i, t ) 3 , U 6 , UU U2, a 3 , « 4 , « 5 -

Одну из них примем за нуль. Для того чтобы меньше было отрицательных потенциалов за нуль примем потенциалы чет­ вертой строки ц4 с большей стоимостью из всех . занятых клеток.

В связи с этим остальные потенциалы определятся так:

87

Соответствующие потенциалы проставлены Ь левой и верх­ ней части таблицы. Пользуясь значениями потенциалов строк

истолбцов, исследуем каждую свободную клетку матрицы.

3.Исследуем свободные клетки на оптимальность. При о тимальном плане должны соблюдаться условия

Vj — «, < C[j.

При несоблюдении данного условия план считается не оп­

5:3 У3—«5— ;8—19 = —11 < 29

5.4 у4—«5=15— 19 = — 4<26.

Проверка показала, что условие оптимальности нарушено в клетке 3.5 и поэтому план не Я'вляется оптимальным. Его можно улучшить, перераспределив поставки.

Перераспределение поставок производим с помощью так называемой цепи Шли замтсИутого -контура. К.о'нтур должен представлять собой прямоугольный многоугольник с четным

числом чйфйшн, ‘Йрйчем одна из нйх должна обязательно на­

88