Методы принятия решений

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

Далее без комментариев повторяем итерацию с перемещением перевозки (15) по циклу в клетку a1b4 с отрицательной характеристикой (-3). Получаем третий план (табл. №3).

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

Zопт = Zmin =  6950 ден. ед.

Построение оптимального плана методом Фогеля.

При определении опорного плана методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находим разность между двумя записанными в них минимальными затратами. Эти разности записаны в специально отведенных для этого строках и столбцах для каждого шага. Среди указанных разностей выбрана максимальная. В строке (или в столбце), которой данная разность соответствует, определён минимальный тариф и клетка, в которой он записан, заполнена на данной итерации (выделено жирным шрифтом).

Например, на первом шаге в первой строке минимальные затраты 17 и 12, разность – 5, во 2-ой строке 11 и 6, разность 5, в 3-ей 19 и 10, разность 9, в 4-ой 14 и 7, разность 7.

В 1-ом столбце минимальные затраты 10 и 6, разность 4, во 2-ом 12 и 11, разность 1, в 3-ем 20 и 17, разность 3, в 4-ом 21 и 7, разность 14.

Наибольшая из этих разностей – 14 соответствует 4-му столбцу. В этом столбце минимум затрат – 7 в строке 4. Заполняем клетку а4b4 объёмом поставок 85 единиц, который может быть поставлен от четвёртого поставщика и строку 4 из дальнейшего рассмотрения исключаем. По аналогии заполнены остальные клетки таблицы и получен опорный план.

Цена этого плана:

Z1 = 90∙12 + 15·21 + 70∙11 + 95∙10 + 135∙22 + 10·27 + 85·7 = 6950 д.е.

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

Задача 7.2. Решить транспортную задачу. Первичный опорный план необходимо найти тремя способами: методом северо-западного угла, методом минимальной стоимости, методом Фогеля. Для каждого найденного опорного плана, произвести перепланировку поставок с помощью метода потенциалов.

Решение: Общий объём запасов:

Общая потребность:

Т.к. , то это транспортная задача открытого типа.

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

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

Порядок составления опорного плана этим методом описан в задаче 7.1.

Стоимость перевозок по этому плану:

Z1 = 95·17 + 10∙12 + 70∙11 + 55∙19 + 135∙22 + 50·27 + 60·7 = 8290 д.е.

Число заполненных клеток должно быть m + n –1 = 4 + 5 – 1 = 8, что имеет место в действительности, т.е. план не вырожден.

Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U1 = 0. Потенциалы других строк и столбцов определяем по формулам:

Ui = Cij – Vj;   Vj = Cij  – Ui;

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

Eij = Cij – (Vj + Ui)  (вписаны в правый нижний угол).

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

Строим для клетки а3b1 с отрицательной характеристикой (-14), цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (55), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. №2) с ценой z2 = 7520.

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

Строим для клетки а1b4 с отрицательной характеристикой (-13), цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (40), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. №3) с ценой z3 = 7000.