Решение оптимизационной задачи по грузоперевозкам

3.      Нахождение допустимых планов перевозок

3.1  Метод северо-западного угла

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

Применим данный метод к конкретной задаче (таблица 4).

Таблица 4

Применение метода северо-западного угла

В этом случае транспортные затраты составят С = 1712,65 денежных единиц.

Проанализируем полученное решение: при данном раскладе потребности в продукции первого, второго и третьего потребителя будут полностью удовлетворены, чего не скажешь о четвертом потребителе.  Его потребности в продукции будут удовлетворены примерно на 58 %, что является не самым лучшим раскладом для него.

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

Для того чтобы узнать, является ли план базисным или нет, надо исследовать решение на следующие условия:

1. Число положительных клеток должно быть меньше либо ровно N;

2. Отсутствие циклов.

N = m + n – 1. N = 8. Число положительных клеток данной модели равно 8.Это удовлетворяет условию  8 ≤ N. Из этого следует, что план невырожденный.

Также здесь отсутствует цикл.

В результате данный план является базисным.

Таким образом, в ходе применения метода северо-западного угла мы получили следующее решение (рис. 1) при транспортных затратах в 1712,65 денежных единиц.

Рис. 1 Результат применения метода северо-западного угла

3.2  Метод минимальной стоимости

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

Применим данный метод к конкретной задаче (таблица 5).

Таблица 5

Применение метода минимальной стоимости

В этом случае транспортные затраты составят С=1692 денежных единиц.

Проанализируем полученное решение: сравнивая с предыдущим методом, мы существенно сократили транспортные затраты. В данном случае, в противоположность методу северо-западного угла,  мы в полной мере удовлетворим потребности второго, третьего и четвертого потребителя. Однако  первый не вполне будет удовлетворен, на 52%.

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

Для того чтобы узнать, является ли план базисным или нет, надо исследовать решение на следующие условия:

1. Число положительных клеток должно быть меньше либо ровно N;

2. Отсутствие циклов.

N = m + n – 1. N = 8. Число положительных клеток данной модели равно 8.Это удовлетворяет условию  8 ≤ N. Из этого следует, что план невырожденный.

Также здесь отсутствует цикл.

В результате данный план является базисным невырожденным решением задачи.

Таким образом, в ходе применения метода минимальной стоимости мы получили следующее решение (рис. 2) при транспортных затратах в 1692 денежных единиц.

Рис. 2 Результат применения метода минимальной стоимости.

4.   Проверка наилучшего плана на оптимальность решения  

Оптимальным является базисный план при условии С(х)С(х*).

Проверить план на его оптимальность можно с помощью признака оптимальности базисного невырожденного плана перевозок.

Пусть X=(Xij), где i=1…m, j=1…n является базисным невырожденным решением системы уравнений:

, i=1…m, j=1…n (только для положительных клеток).

Если найденные решения удовлетворяют условию, i=1…m, j=1…n для всех клеток, то Х- оптимальный план перевозок.

Проверим на оптимальность наилучший план перевозок, найденный с помощью применения вышеуказанных методов. В нашем случае лучший результат мы получили с помощью метода минимальной стоимости. Затраты в нем равняются 1692 денежных единиц. Для облегчения расчетов продублируем ниже таблицу, содержащую наилучшее из полученных решений (таблица 6)

Таблица 6

Результаты применения метода минимальной стоимости

Определим значения vj и ui.

Vj – Ui = Cij прихij > 0

Берем произвольно: U1 = 0, тогда