Численный метод

Метод наименьших стоимостей.

Данный метод находит лучшее начальное решение транспортной задачи по сравнению с методом северо-западного угла, т.к выбирает переменные, которым соответствуют наименьшие стоимости.

Пункт 1. Сначала во всей транспортной таблице выбирается клетка с наименьшей стоимостью. Переменной в этой клетке присваивается максимально допустимое значение, допускаемое ограничениями на заявки и запасы, т.е. .

Пункт 2. Если полностью реализован запас, т.е. , то вычеркивается i-тая строка. Если же полностью выполнена заявка, т.е. , то вычеркивается j-тый столбец. Если одновременно удовлетворяет заявка и исчерпывается запас, то обычно вычеркивается j-тый столбец. Затем корректируются значения запасов или заявок, уменьшая их величину на .

Пункт 3. Процесс заканчивается, если осталась одна невычеркнутая строка или один столбец. В противном случае, возвращаемся к пункту 1.

Пример:

Имеется m пунктов отправления , в которых сосредоточен однотипный груз в количестве . Имеется и n пунктов назначения . Каждый пункт подает заявку на груз в количестве . Сумма всех заказов равна сумме всех заявок.

Стоимость перевозки одного груза из i-го пункта отправления в j-ый пункт назначения задается . Требуется составить такой план перевозок, чтобы все запасы были исчерпаны и все заявки были удовлетворены, а общая стоимость всех перевозок должна быть минимальной.

Обозначим через количество единицы груза, отправляемого из i-го пункта отправления в j-ый пункт назначения.

Получим матрицу перевозок

Рисунок 3.1 – Матрица перевозок

А вершины называют перевозками.

>0

Перевозки удовлетворяют двум условиям:

1. Суммарное количество груза, вывозимого из каждого пункта отправления во все пункты назначения, равно запасу груза в каждом пункте отправления.

Рисунок 3.2 – Суммарное количество груза из каждого пункта отправления во все пункты назначения

2. Суммарное количество груза, привозимого в каждый пункт назначения из всех пунктов отправления должно быть равно заявке, равной каждому пункту назначения.

Рисунок 3.3 –Суммарное количество груза, привозимого в каждый пункт назначения из всех пунктов отправления

Суммарная стоимость всех перевозок должна быть минимальной.

Особенностью данной задачи является то, что все коэффициенты при неизвестных системах равны единице. Это значительно упрощает решение задачи.

Все уравнения этой системы можно решить количеством базисных переменных, выразив их через свободные. Количество свободных переменных равно (m-1)*(n-1).

План перевозок называется допустимым, если все заявки удовлетворены и все запасы исчерпаны.

Допустимый план называется оптимальным, если среди всех планов он приводит к минимальной стоимости.

При решении транспортной задачи повторяются решение симплексного метода. Но способ проверки видоизменен.

Основные шаги алгоритма решения транспортной задачи:

Найти начальное допустимое решение, выделить из свободных переменных переменную, вводимую в базис, если все свободные переменные удовлетворяют условию оптимальности, то закончить вычисления. Иначе выбрать выводимую из базиса переменную. Процесс ввода и вывода переменных продолжается до тех пор, пока не будет получен оптимальный план.