- •Лекция. Транспортная задача План:
- •Ключевые слова:
- •1. Постановка задачи и ее математическая модель
- •2. Обеспечение разрешимости транспортной задачи. Построение начального плана перевозок
- •3. Теоретическое обоснование метода потенциалов
- •4. Алгоритм метода потенциалов
- •5. Пример решения транспортной задачи
- •6. Упражнения для самостоятельной работы
- •Рачковский Николай Николаевич математическое программирование Транспортная задача
- •220086, Минск, ул. Славинского, 1, корп. 3.
2. Обеспечение разрешимости транспортной задачи. Построение начального плана перевозок
Прежде чем приступить к непосредственному решению транспортной задачи, нужно убедиться, что для нее существует оптимальное решение. Для этого нужно вычислить и сравнить совокупные запасы груза у поставщиков и совокупный спрос потребителей – они должны быть равны. Если они не равны друг другу, их следует уравнять, добавив либо фиктивного поставщика с недостающим запасом груза, либо фиктивного потребителя с недостающим спросом.
Как известно, стандартный симплекс-метод представляет собой процедуру последовательного улучшения имеющегося допустимого решения задачи линейного программирования, поэтому для использования симплекс-метода необходимо иметь некоторое допустимое решение, которое и будет улучшено. Для нахождения такого допустимого решения (начального приближения к оптимальному решению) используется так называемый метод искусственного базиса.
Метод потенциалов является разновидностью симплекс-метода, естественно, что при решении транспортной задачи методом потенциалов возникает аналогичная ситуация. Чтобы использовать данный метод, нужно уже иметь какой-нибудь план перевозок, который будет улучшен впоследствии. Для нахождения начального плана перевозок имеются несколько различных методов. Мы будем пользоваться, возможно, не самым эффективным из них, но несомненно наиболее простым – методом северо-западного угла.
Построение начального плана перевозок, а также улучшение имеющегося плана удобно производить на распределительной таблице: в правом верхнем углу каждой ее клетки указывается соответствующий тариф , в левых нижних углах клеток указываются загрузки – это соответствующее количество перевозимых грузов (табл. 2).
Таблица 2
|
Потребители |
Запас груза |
||||
В1 |
В2 |
… |
Вn |
|||
Поставщики |
A1 |
c11 |
c12 |
… |
c1n |
а1 |
А2 |
c21 |
c22 |
… |
c2n |
а2 |
|
… |
… |
… |
… |
|||
Am |
сm1 |
сm2 |
… |
сmn |
||
Спрос |
b1 |
b2 |
… |
bn |
|
При заполнении таблицы следует иметь в виду, что тарифы перевозок, связанные с фиктивным пунктом, должны быть равны 0.
Согласно методу северо-западного угла, загрузка распределительной таблицы (построение начального плана перевозок) начинается с клетки (1; 1), соответствующей поставщику с запасом груза и потребителю со спросом . Загрузку этой клетки требуется выбрать так, чтобы либо полностью вывезти весь накопленный запас груза из пункта поставки , либо полностью удовлетворить спрос потребителя , либо и то, и другое одновременно. Поэтому клетку (1; 1) загрузим минимальным из чисел , , т. е. числом . Затем возникает вопрос о выборе следующей клетки для загрузки. Каждый раз такой выбор должен осуществляться на основе следующего правила: нужно сложить загрузки всех уже загруженных клеток графы, в которой находится последняя загруженная клетка, и сравнить эту сумму со спросом в данной графе (самая нижняя строка). Если окажется, что вычисленная сумма загрузок меньше соответствующего спроса, то следующая загружаемая клетка будет находиться ниже последней загруженной клетки, в противном случае – справа от нее.
Для загрузки очередной клетки таблицы нужно сравнить остаток запаса груза (разность между запасом груза и суммой загрузок клеток строки, в которой находится загружаемая клетка) и остаток спроса (разность между спросом и суммой загрузок клеток графы, в которой находится загружаемая клетка), соответствующие этой клетке, и выбрать из них минимальное число (даже если оно равно нулю). Оно и берется в качестве загрузки очередной клетки. Этот процесс продолжается до тех пор, пока не будет загружена клетка , соответствующая поставщику и потребителю .
Для контроля правильности построения начального плана перевозок нужно иметь в виду следующее:
1) в полностью построенном начальном плане перевозок должно быть загружено ровно клеток;
2) сумма загрузок всех клеток в каждой строке должна быть равна соответствующему запасу груза;
3) сумма загрузок всех клеток в каждой графе должна быть равна соответствующему спросу.