Решение транспортной задачи – онлайн калькулятор
Онлайн калькулятор для решения транспортной задачи методом потенциалов. Расчет первого опорного плана осуществляется методом наименьшей стоимости или методом северо-западного угла. Решение выполняется как для закрытой, так и для открытой модели.
Онлайн калькулятор
Исходные данные задачи
Метод ввода данных:
Вручную Из электронной таблицы
Редактировать Рассчитать Копировать Удалить все
Идут вычисления .
Достигнуто максимальное число шагов, но задача не решена. Можно продолжить вычисления, добавив желаемое количество шагов.
Руководство по использованию калькулятора
Математическая модель задачи
Пусть некоторый продукт, который будем называть грузом, нужно перевезти от m поставщиков к n потребителям. При этом у поставщика с номером i имеется ai единиц груза, ; потребителю с номером j требуется bj единиц груза, . Величины ai и bj мы будем называть, соответственно, мощностью i — го поставщика и мощностью j — го потребителя. Известны величины стоимости cij перевозки единицы груза от i — го поставщика к j — му потребителю. Пусть xij – количество груза, перевезенного от i — го поставщика к j — му потребителю. Организовать перевозки можно различными способами, то есть величины xij можно выбрать с помощью различных вариантов. Требуется определить такие значения величин xij , при которых суммарные затраты F на перевозки будут минимальными: .
Таким образом, математическая модель задачи имеет следующий вид:
.
Предлагаемый калькулятор позволяет решить транспортную задачу онлайн методом потенциалов.
Ввод исходных данных
Исходными данными являются мощности поставщиков ai , мощности потребителей bj и затраты на перевозки cij . Все исходные данные вводятся в таблице, у которой m + 1 строк и n + 1 столбцов. При этом либо первая слева клетка (1, 1) , либо клетка (m + 1, n + 1) справа в последнем ряду, пустая.
Существует два способа ввода данных:
1. Вручную, вводом значений в соответствующие поля.
2. Загружая данные из электронной таблицы.
Ввод данных вручную
Чтобы ввести исходные данные вручную нужно выполнить следующие действия.
1. В строке ′Метод ввода данных′ ⇑, нужно поставить переключатель в положение ′Вручную′.
2. Ввести число поставщиков a , число потребителей b , и нажать кнопку ′Применить′.
3. В появившейся таблице заполнить столбец мощностей поставщиков ai , строку мощностей потребителей bj , и матрицу затрат cij .
4. Выбрать метод расчета начального опорного плана – отметить либо ′Метод наименьшей стоимости′, либо ′Метод северо-западного угла′.
5. Нажать кнопку ′Рассчитать′. В результате появится подробное решение задачи.
6. После расчета можно сохранить исходные данные. Для этого в строке ′Метод ввода данных′ ⇑, нужно отметить ′Из электронной таблицы′. В текстовом поле будут исходные данные задачи. Их можно скопировать в буфер обмена и вставить в электронную таблицу или текстовый документ. Для этого нужно нажать кнопку ′Копировать′. Данные будут скопированы в буфер обмена. Далее можно открыть электронную таблицу или текстовый документ, и вставить данные из буфера обмена, нажимая Ctrl-V . После чего сохранить изменения в документе.
Ввод данных из электронной таблицы
Исходные данные можно ввести из электронной таблицы. При этом разделителем строк является перенос строки. В качестве разделителя столбцов может быть символ табуляции, запятая ′,′, точка с запятой ′;′, двоеточие ′:′ или пробел ′ ′. Вводить мощности поставщиков и потребителей можно двумя способами.
В первом способе, первое поле первой строки должно быть пустым. Далее, в первой строке следуют величины мощностей потребителей bj . В следующих строках, первым элементом является мощность поставщика ai . За ним следуют элементы матрицы затрат cij .
Транспортная задача – основные понятия, определения и теоремы
Основные понятия, определения и теоремы, относящиеся к транспортной задаче линейного программирования. Рассмотрены следующие вопросы: математическая модель транспортной задачи, открытия и закрытая модели, построение первого опорного плана методами северо-западного угла и наименьшей стоимости, переход от одного опорного плана к другому с помощью цикла, оценки свободных клеток и выбор новых базисных переменных методом потенциалов, множественность решения.
Математическая модель транспортной задачи
Постановка задачи
Пусть некоторый продукт, который мы будем называть грузом, нужно перевезти с одних складов в другие. Склады, в которых первоначально находится груз, мы будем называть поставщиками. Склады, в которые нужно перевести груз, будем называть потребителями. То есть весь груз нужно перевезти от поставщиков к потребителям. Считаем, что есть m поставщиков и n потребителей. Пронумеруем поставщиков от единицы до m . Пусть в i -ом складе поставщика имеется ai единиц груза, . И пусть каждый j -ый потребитель может принять только определенное количество груза bj , . Известна стоимость cij перевозки единицы груза от i -го поставщика к j -му потребителю. Требуется составить такой план перевозок, то есть определить количество груза xij , которое нужно перевести от i -го поставщика к j -му потребителю, при котором весь груз от поставщиков будет перевезен к потребителям с минимальными затратами на перевозки.
Построим математическую модель транспортной задачи. Затраты на перевозку груза от i -го поставщика к j -му потребителю равны произведению стоимости перевозки единицы груза на количество перевозимого груза. Суммируя по всем поставщикам и потребителям, получим суммарную стоимость перевозок:
.
Задача состоит в том, чтобы подбором величин , сделать суммарную стоимость перевозок минимальной:
.
Если просуммировать xij по всем потребителям j , то получим суммарное количество груза, перевезенного от i -го поставщика ко всем потребителям. Оно должно равняться запасам ai этого поставщика:
.
Если просуммировать xij по всем поставщикам i , то получим суммарное количество груза, доставленного j -му потребителю от всех поставщиков. Оно должно равняться потребностям bj этого потребителя:
.
Также мы должны учесть, что количество перевезенного груза не может быть отрицательным:
.
В результате, мы получаем математическую модель транспортной задачи:
.
Определение транспортной задачи
Транспортная задача – это задача линейного программирования следующего вида:
(М.1)
(М.2)
(М.3)
(М.4) ,
где .
В транспортной задаче требуется определить количество груза , которое нужно перевезти от -го поставщика к -му потребителю, чтобы перевезти весь груз от поставщиков к потребителям, и при этом суммарные затраты на перевозки были минимальны.
Здесь – стоимость перевозки единицы груза от -го поставщика к -му потребителю; – мощность -го поставщика, то есть максимальное количество груза, которое может отправить этот поставщик; – мощность -го потребителя, то есть максимальное количество груза, которое может принять этот потребитель; m – число поставщиков; n – число потребителей.
Матрица транспортных издержек – это матрица, составленная из элементов , каждый из которых равен затратам на перевозку единицы груза от -го поставщика к -му потребителю.
План перевозок транспортной задачи – это совокупность переменных , каждая из которых равна количеству груза, перевозимого от -го поставщика к -му потребителю. Эти переменные удовлетворяют условиям (М.2), (М.3) и (М.4). План перевозок обычно записывают в виде матрицы.
Исследование математической модели
По сравнению со стандартной формой записи задачи линейного программирования, транспортная задача имеет свои отличия. Если в стандартной форме переменные нумеруются одним индексом: , то в транспортной задаче наиболее естественно изменить систему нумерации, и использовать два индекса: . При этом общее число N переменных равно произведению числа поставщиков на число потребителей: .
Закрытая и открытая модели
Согласно теореме о существовании решения ⇑, чтобы транспортная задача имела решение, сумма мощностей поставщиков должна равняться сумме мощностей потребителей:
.
Такая задача называется задачей с правильным балансом, а ее математическая модель – закрытой.
Транспортная задача с правильным балансом – это задача, у которой сумма запасов (мощностей) поставщиков равна сумме потребностей (мощностей) потребителей. Математическая модель такой задачи называется закрытой. Транспортная задача с неправильным балансом – это задача, у которой сумма запасов (мощностей) поставщиков не равна сумме потребностей (мощностей) потребителей. Математическая модель такой задачи называется открытой.
Открытая модель
Если задача с неправильным балансом, то система ограничений (М.2), (М.3), (М.4) не имеет решений, поскольку, или часть потребителей не получат требуемое количество, или часть поставщиков не смогут реализовать все грузы. То есть уравнения системы ограничений не будут выполняться ни при каком плане перевозок . Чтобы исправить ситуацию, мы должны или в (М.2), или в (М.3), заменить равенства равенствами.
Пусть сумма мощностей поставщиков меньше суммы мощностей потребителей:
.
Тогда часть потребителей не получат требуемого количества груза. При этом все поставщики смогут реализовать груз в полном объеме. Это означает, что количество полученного потребителем j груза, , может быть меньше его потребности . В этом случае, нам надо заменить равенства (М.3) неравенствами:
(Т.1) .
Аналогичным образом, пусть сумма мощностей поставщиков больше суммы мощностей потребителей:
.
В этом случае, можно составить такой план перевозок, при котором все потребители получат требуемое количество груза, но часть поставщиков не реализуют свой груз в полном объеме. То есть количество отправленного поставщиком i груза, , может быть меньше имеющегося запаса . Тогда, чтобы получить решение задачи, нужно заменить равенства (М.2):
(Т.2) .
Таким образом, в открытой задаче всегда подразумевается, что если сумма мощностей поставщиков меньше суммы мощностей потребителей, то вместо уравнений (М.3) стоят неравенства (Т.1). Если сумма мощностей поставщиков больше суммы мощностей потребителей, то вместо (М.2) будут неравенства (Т.2).
Приведение открытой модели к закрытой
Открытую модель можно легко привести к закрытой, если добавить фиктивного поставщика или потребителя с нулевыми затратами на перевозки.
Так, если , то мы вводим фиктивного поставщика с мощностью , и нулевыми затратами .
Если , то вводим фиктивного потребителя с мощностью , и нулевыми затратами .
Решение транспортной задачи методом потенциалов
Транспортную задачу можно решить различными методами, применяемыми в линейном программировании. При этом наиболее широко используются методы, которые позволяют получить решение, используя специфический вид системы ограничений (М.2) – (М.3).
Одним из таких методов является метод улучшения плана, примененный к транспортной задаче. Он называется методом потенциалов. Как и в симплексном методе, в методе потенциалов сначала строится первый опорный план, то есть определяется состав базисных переменных. Затем производятся оценки свободных переменных. Если хотя бы одна оценка свободной переменной приводит к уменьшению целевой функции, то ее вводят в состав базисных переменных. После чего переходят к новым базисным переменным, определяя переменную, выходящую из базиса.
Существует еще венгерский метод, являющийся методом сокращения невязок, но мы не будем его здесь рассматривать.
Таблицы для расчетов
Выполнение решения транспортной задачи удобно проводить в таблицах. Обычно их заполняют следующим образом.
Верхняя левая клетка является пустой. Под ней расположен столбец из m клеток со значениями мощностей поставщиков . В верхнем ряду расположена строка из n клеток со значениями мощностей потребителей . В остальных клетках записывают значения элементов матрицы издержек и плана перевозок . Обычно величины записывают в правом верхнем углу клетки мелким шрифтом, а величины – крупным шрифтом в нижней части. При этом отображают только значения базисных переменных . Клетки с небазисными переменными остаются пустыми. Такая таблица содержит строк и столбцов.
При вычислении оценок, таблицу дополняют еще одним столбцом и строкой, в которые записывают значения потенциалов и . В таких таблицах строки и столбца.
При обращении к определенной клетке, указывают ее номер, состоящий из двух цифр, точно так, как и при обращении к элементам матрицы издержек . То есть, например, когда мы говорим, что это клетка (1, 2) , то тем самым подразумеваем, что это клетка, в которой записано значение . Первой строкой считается строка, относящаяся к первому поставщику . А первым столбцом – к первому потребителю .
Открытая транспортная задача. Как решить?
Будем считать, что мы уже знаем, что такое транспортная задача, как решить закрытую транспортную задачу, как составить первоначальный опорный план и как бороться с вырожденностью плана. Если что — то из этого Вам незнакомо, то при желании можно изучить тут:
Транспортная задача называется открытой, если не соблюдается баланс между объемом спроса и объемом предложения. Например, если запасы на всех складах меньше или больше потребностей всех магазинов — потребителей, то имеем дело с открытой транспортной моделью.
Для того, чтобы применить к задаче метод потенциалов, необходимо привести открытую транспортную задачу к закрытой модели. Т.е. необходимо выполнить преобразования, при которых , «то, что есть, станет равным, тому, что надо».
Все очень просто. Если не хватает товара, чтобы удовлетворить потребности магазинов, нужно добавить мнимого (фиктивного) поставщика. Если предложение превышает над спросом, добавим мнимого (фиктивного) потребителя.
В открытой транспортной задаче это реализуется добавлением строки или столбца, в зависимости от того,чего не хватает. Так как в реальности фиктивный поставщик (потребитель) не существует, то стоимость доставки до него от любого пункта равна нулю.
Чтобы привести открытую транспортную задачу к закрытому (замкнутому) виду, добавляем столбец (строку) с нулевыми стоимостями.
Если превышают запасы — добавляем фиктивного потребителя (столбец)
Если превышает спрос — добавляем фиктивного поставщика (строку)
Рассмотрим подробно на примере.
Открытая транспортная задача — пример 1:
Решить транспортную задачу с исходными данными:
Общие потребности (спрос) = 40 + 180 + 80 + 60 = 360
Общие запасы (предложение) = 120 + 100 = 220
Видим, что спрос превышает над предложением.
Следовательно добавляем фиктивного поставщика А3 с объем запасов 360 — 220 = 140.
Получили закрытую транспортную задачу: спрос = предложению.
Построим первоначальный план методом северо-западного угла:
Шаг 1 :
Проверим первоначальный план на оптимальность:
Подробно о том, как были заполнены таблицы можно посмотреть тут: Как решить транспортную задачу?
Среди оценочных значений правой таблице есть отрицательные, следовательно план не оптимален.
Построили замкнутую цепочку знаков » + » и » — «.
Среди ячеек, помеченных » — » выберем ячейку с минимальным значением:
Это значение 80 перенесем в пустую ячейку, помеченную » + «, далее, к значениям в ячейках с » + » прибавим К, из значений в ячейках с » — » вычтем К.
Определим стоимость перевозки на первом шаге:
S1 = 40 · 4 + 80 · 9 + 100 · 11 + 0 · 0 + 80 · 0 + 60 · 0 = 1980
Шаг 2 :
Среди оценочных значений правой таблице есть отрицательные, следовательно план не оптимален.
В ячейках с » + » прибавим данное значение, в ячейках с » — » вычтем.
Общая стоимость перевозки на данном шаге:
S2 = 40 · 4 + 80 · 9 + 20 · 11 + 80 · 3 + 80 · 0 + 60 · 0 = 1340 < S1
Видим, что стоимость перевозки на текущем шаге меньше чем на предыдущем.
Шаг 3 :
Среди оценочных значений правой таблице есть отрицательные, следовательно план не оптимален.
Общая стоимость перевозки на данном шаге:
S3 = 40 · 4 + 80 · 9 + 80 · 3 + 20 · 4 + 100 · 0 + 40 · 0 = 1200 < S2
Видим, что стоимость перевозки на текущем шаге меньше чем на предыдущем.
Шаг 4 :
Среди оценочных значений нет отрицательных, следовательно решение оптимально.
S4 = 40 · 4 + 40 · 9 + 40 · 2 + 40 · 3 + 60 · 4 + 140 · 0 = 960 < S3
Задача решена, получен оптимальный план перевозок.
Открытая транспортная задача — пример 2:
Решить открытую транспортную задачу с исходными данными:
Общие потребности (спрос) = 40 + 40 + 20 = 100
Общие запасы (предложение) = 20 + 30 + 40 + 20 = 110
Видим, что предложение превышает над спросом.
Следовательно добавляем фиктивного потребителя В4 с потребностями 110 — 100 = 10.
Получили закрытую транспортную задачу: спрос = предложению.
Как решить транспортную задачу?
В данной статье разберемся с решением транспортной задачи. Все действия будем выполнять пошагово с очень подробными пояснениями. Дадим определение, аналогичное тому, которое дано в ваших учебниках или лекциях.
Определение:
Транспортная задача — это математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов с минимизацией затрат на перемещение.
Чтобы не загромождать страницу большим объемом пояснений, разобью весь материал на несколько частей — блоков.
Ну, начнем! Далее Вводная часть, с которой желательно ознакомиться.
Вводная часть, с которой желательно ознакомиться
Существует несколько методов решения транспортной задачи. Мы будем подробно рассматривать два из них:
- решение транспортной задачи методом потенциалов (рассмотрен в данной статье)
- решение транспортной задачи с использованием симплекс метода.
Решение задачи методом потенциалов происходит в несколько этапов:
- Определение опорного решения.
- Применение к найденному опорному решению самого метода потенциалов.
- Проверка единственности решения.
Определение опорного плана, в свою очередь, можно выполнить несколькими способами. Мы рассмотрим два из них:
- метод северо-западного угла
- метод минимальных стоимостей
(не путать с методами решения самой транспортной задачи. )
О чем говорится в определении транспортной задачи?
У нас есть некоторый груз, который находится на складах: склад 1, склад 2, . склад — это пункты отправления.
Этот груз нам необходимо развести по магазинам: магазин 1, магазин 2, . магазин k — это пункты назначения.
Нам выгоднее как можно эффективнее выполнить работу, т.е. найти такой вариант перевозки, при котором затраты будут минимальными.
Рассмотрим пример решения транспортной задачи подробно.
Транспортная задача задается следующей таблицей:
Далее, что означают числа в условии транспортной задачи?
Что означают числа в условии транспортной задачи?
Рассмотрим постановку транспортной задачи, т.е. что дано в условии и переведем ее с математического языка на язык, понятный нам.
Это наши «склады» — пункты отправления: два склада с товаром: А1 и А 2
Это объем товара — количество груза, соответственно на складах А1 и А2:
Далее имеем дело с пунктами назначения — с «магазинами». В нашем случае их 4 штуки: В1, В2, В3 и В4.
И соответственно потребности каждого из магазинов — потребности пунктов назначения:
Числа внутри таблицы — матрица стоимостей, или по другому, расценки перевозки 1 единицы груза из соответствующих пунктов. Эти значения также могут интерпритироваться как расстояния между соответствующими пунктами. Подробности — в условии решаемой задачи.
Например, для перевозки 1 единицы груза из пункта отправления («склада») А2 в пункт назначения («магазин») В3 надо заплатить 4 условные единицы стоимости, например 4 руб.
Аналогично, мы заплатим 6 рублей за перевозку 1 единицы груза из «склада» А1 в «магазин» В4.
Или та же самая задача может быть задана сразу в более понятном виде:
Возможна текстовая постановка задачи. В этом случае необходимо самим заполнять все ячейки таблицы, исходя из заданных в условии значений.
Далее — Методы определения первоначального плана транспортной задачи.
Методы определения первоначального плана транспортной задачи.
Рассмотрим самый распространенный метод получения опорного плана — метод северо-западного угла.
Называется он так потому, что заполнение таблицы начинается с самой верхней левой (северо-западной) ячейки.
Перед тем, как распределять ресурсы по «магазинам», проверим, равны ли общие потребности имеющимся ресурсам?
Потребности: 50 + 100 + 75 + 75 = 300
Ресурсы: 100 + 200 = 300
В этом случае говорят, что транспортная задача закрытая. Решение открытой транспортной задачи рассмотрим чуть позже.
Начнем нахождение опорного решения:
Заполним клетку (1;1).
В магазин В1 требуется 50 единиц товара. Со склада А1 отправим в этот магазин 50 единиц.
Потребности магазина В1 выполнены, следовательно, нет необходимости везти туда груз со склада А2.
На складе А1 еще осталось 50 единиц груза. Эти остатки можем направить в магазин В2. Ресурсы склада А1 исчерпаны.
Переходим к складу А2.
Так как потребности магазина В1 выполнены полностью, рассмотрим магазин В2, которому требуется 100-50=50 единиц товара. Направим их туда.
Заметим, на складе А2 осталось еще 200-50=150 единиц груза, которые мы распределим по магазинам В3 и В4, полностью удовлетворяя и их потребности.
Потребности магазинов в товаре полностью выполнены!
Получен опорный (первоначальный) план транспортной задачи.
Рассмотрели северо-западный метод построения первоначального плана (опорного решения).
Далее опишем метод минимальных стоимостей получения опорного плана.
Метод минимальных стоимостей получения опорного плана
Суть метода состоим в том, чтобы в первую очередь направлять груз в те пункты, где «расценки» в матрице стоимостей минимальны. Если клеток с наименьшими тарифами несколько, то заполняется любая из них.
Направляем 100 единиц груза из склада А2 в магазин В2.
Остатки на складе А 2 — 100 единиц. Потребности магазина В 2 выполнены.
Груз со склада А2 отправим в магазин, у которого стоимость перевозки ниже — магазин В3, так как мин(4;7)=4
Размер поставки равен потребности магазина — 75. Остатки со склада 200-100-75=25 перенесем в магазин В4.
Остается только раскидать груз со склада А1 по магазинам: В1 — 50 единиц, В4 — 75-25=50 единиц.
Получили два опорных плана: методом северо-западного угла и методом минимальных стоимостей.
Первый опорный план (по методу северо-западного угла):
Второй опорный план (по методу минимальных стоимостей):
Далее проверим правильность вычисления первоначального плана.
Проверка правильности вычисления первоначального плана
Перед тем как перейти к дальнейшему решению задачи проверим условие:
Правило:
Количество заполненных клеток (базисных клеток) в первоначальном плане ВСЕГДА должно быть равно m + n — 1, где m — количество строк, n — количество столбцов
В нашем случае условие выполняется: 2 + 4 — 1 = 5
Что же делать, если количество заполненных ячеек меньше необходимого?
Во избежании случайных вычислительных ошибок проверим, равны ли суммарные значения каждой строки и каждого столбца соответствующим значениям условия.
200 = 100 + 75 + 25
Видим, суммарные значения элементов каждого столбца равны соответствующим потребностям магазинов.
Несмотря на то, что опорные планы разные, оба приведут к одному оптимальному решению или же к решениям, имеющим одну стоимость перевозки.
Далее применим метод потенциалов к обоим опорным планам и сравним получившиеся ответы.
Метод потенциалов решения транспортной задачи — шаг 1.
Описанную ниже последовательность действий будем повторять несколько раз, с каждым шагом приближаясь к оптимальному решению. Начнем с проверки опорного плана на оптимальность.
Выпишем матрицу стоимостей, данную в условии задачи.
Далее строим рядом две таблицы. Размерность таблиц как и в матрице стоимостей:
количество строк = количеству складов, количество столбцов = количеству магазинов.
Заполняем первую — левую таблицу в соответствии с полученным опорным планом.
Переходим в правую таблицу.
Переносим из матрицы стоимостей значения, которые соответствуют занятым клеткам левой таблицы.
В матрице стоимости эти значения подчеркнуты.
Припишем каждой строке правой таблице потенциалы u1, u2. Каждому столбцу — потенциалы v1, v2, v3, v4.
Для вычисления этих потенциалов в некоторых учебниках составляют систему и из нее определяют неизвестные (покажу на данном шаге).
Мы будем определять значения потенциалов непосредственно из правой таблицы.
Составим систему уравнений по следующему правилу:
Каждое из значений в ячейке (правая таблица) равно сумме потенциалов соответствующей строки и соответствующего столбца.
Например: значение 4 находится в 1-й строке и 1-м столбце. Тогда сумма потенциалов 1-й строки (u1) и 1-ого столбца(v1) равна 4.
Первое уравнение системы: u1 + v1 = 4
Рассмотрим следующее значение таблицы.
Значение 3 находится в первой строке (потенциал u1), втором столбце (потенциал v2).
Второе уравнение системы: u1 + v2 = 3
Аналогично для каждого значения таблицы составим уравнение.
Получим систему уравнений:
Для того, чтобы система имела единственное решение, примем значение одного из потенциалов равным нулю.
Для удобства в качестве этого потенциала всегда будем брать v4.
Тогда система уравнений будет выглядеть:
Решим систему уравнений и получим значения потенциалов:
Так как система очень проста, то значения потенциалов можно получить и устно.
Сумма отмеченных потенциалов равна 7, следовательно, потенциал u2 = 7
Значение 4 базисной ячейки находится во 2-й строке, 3-м столбце, тогда рассмотрим сумму соответствующих потенциалов.
Далее все аналогично:
Значение 2 равно сумме потенциалов 2-й строки и 2-го столбца:
В итоге получили:
Далее приступим к заполнению пустых ячеек (свободные ячейки) правой таблицы.
Свободные ячейки подчиняются тому же правилу суммирования потенциалов.
Вычислим оценочную матрицу, по которой узнаем, оптимален ли рассматриваемый план.
Из каждого элемента матрицы стоимостей вычтем соответствующий элемент правой таблицы:
Получили оценочную матрицу. Заметим, что в базисных ячейках всегда получим нули.
Критерий оптимальности:
если в оценочной матрице нет отрицательных элементов, то решение оптимально, в противном случае решение не оптимально.
Согласно критерию оптимальности, решение выше не оптимально, так как в оценочной таблице присутствует отрицательное значение.
Дабы не загромождать решение множеством таблиц, оценочная матрица в нашем решении будет «вписана» в правую таблицу.
Подчеркнутые значения — базисные ячейки, как сказано выше, значения оценочной матрицы в базисных ячейках равны нулю, нули писать не будем. Выделенные значения — значения оценочной матрицы в свободных ячейках, среди них ищем отрицательные значения.
Для перехода к следующему опорному решению выполним следующее (построим цикл пересчета):
— найдем среди отрицательных значений оценочной матрицы максимальный по модулю (или по другому, минимальный среди отрицательных)
— в соответствующей ячейке левой таблицы ставим знак » + «
В нашем примере наименьшее отрицательное значение -2.
Знак » + » ставим в ячейке 1-й строки, 4-го столбца левой таблицы — ячейка соответствующая значению (-2).
Необходимо расставить чередующиеся значения «+ » и » — » в левой таблице так, чтобы получился замкнутый цикл и выполнялись правила:
— остальные знаки цикла (все кроме уже поставленного первого » + «) ставим только в заполненных (базисных) ячейках таблицы,
— если в строке есть «плюс» («минус»), то в этой строке должен быть и «минус» («плюс»),
— если в столбце есть » плюс» («минус»), то в этом столбце должен быть и «минус» («плюс»).
Применим к нашей таблице:
В столбце В4 есть «плюс», следовательно в этом столбце должен быть и «минус».
Аналогично, в строке А2 есть «минус», следовательно должен быть и «плюс».
Если мы поставим этот «плюс» в столбце В3, то цепочка порвется, так как в этом же столбце невозможно поставить «минус» — нет заполненной ячейки.
Ставим » + » в столбце В2 и продолжаем чередовать знаки.
Получили замкнутый цикл чередующихся знаков. Цикл пересчета найден!
Далее обратимся к ячейкам, содержащим «минусы». Среди значений этих ячеек найдем минимальное: Δ = мин = 50
К «плюсам» прибавим найденное Δ = 50, в ячейках с «минусами» — вычтем Δ = 50.
Ячейка, в которой находилось значение Δ = 50 останется пустой. В ячейке в которой мы поставили первый плюс появится значение, равное Δ = 50.
Общее количество заполненных (базисных) ячеек при пересчете не должно изменится!
Получили следующий опорный план:
Вычислим стоимость перевозки на первом шаге.
Для этого найдем сумму произведений значений опорного плана и матрицы стоимостей.
S1 = 50 · 4 + 100 · 2 + 75 · 4 + 25 · 7 + 50 · 6 = 1275
На первом шаге решения транспортной задачи получили опорный план:
Общая стоимость перевозки S1 = 1275
Метод потенциалов — шаг 2
Алгоритм проверки плана на оптимальность и построение цикла пересчета очень подробно расписан в шаге 1.
Далее решение задачи будем излагать менее детально.
Для полученного опорного решения строим вспомогательную — правую таблицу и заполняем значениями из матрицы стоимостей базисные ячейки.
Вычисляем потенциалы строк и столбцов:
По правилу суммирования соответствующих потенциалов, заполняем свободные ячейки.
Вычисляем оценочные значения в свободных ячейках.
Для этого из значений матрицы стоимостей вычитаем найденные значения соответствующих свободных ячеек.
Среди оценочных значений нет отрицательных, следовательно план перевозки оптимален.
Получили оптимальный план. Итоговая стоимость перевозки S1 = 1275