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

Введение

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

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

Содержание

Задача 7.1.

Задача 7.2.

Список литературы

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

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

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

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

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

Здесь в верхнем правом углу клеток записана стоимость перевозки.

Заполнять таблицу первоначального опорного плана начинаем с клетки а1b1 – это северо-западный угол.

Закрываем потребности b1 поставкой из а1 и этот столбец исключаем из дальнейшего рассмотрения. Остаток груза из а1 отправляем потребителю b2 и строку а1 исключаем из дальнейшего рассмотрения. Затем весь груз из а2 отправляем в b2, исключая строку а2 и частью груза из а3 закрываем потребность b2, исключая столбец b2. Далее закрываем потребность b3 поставкой из а3, а остаток груза из а3 отправляем потребителю b4. Груз из а4 отправляем потребителю b4. Опорный план составлен.

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

Z1 = 95·17 + 10∙12 + 70∙11 + 80∙19 + 135∙22 + 25·27 + 85·7 = 8265 д.е.

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

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

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

V1 = C11 – U1 = 17 – 0 = 17;   V2 = C12 – U1 = 12 – 0 = 12;  U2 = C22 – V2 = 11 – 12 = -1;

U3 = C32 – V2 = 19 – 12 = 7;     V3 = C33 – U3 = 22 – 7 = 15;    V4 = C34 – U3 = 27 – 7 = 20.

U4 = C44 – V4 = 7 – 20 = -13;    

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

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

Е13 = С13 – (V3 + U1) = 17  – (15 + 0) = 2;   Е14 = С14 – (V4 + U1) = 21 – (20 + 0) = 1;

  Е21 = С21 – (V1 + U2) = 6 – (17 - 1) = -10;    Е23 = С23 – (V3 + U2) = 20 – (15 - 1) = 6;   

Е24 = С24 – (V4 + U2) = 28 – (20 - 1) = 9;    Е31 = С31 – (V1 + U3) = 10 – (17 + 7) = -14;

Е41 = С41 – (V1 + U4) = 18 – (17 - 13) = 14;   Е42 = С42 – (V2 + U4) = 14 – (12 - 13) = 15;

Е43 = С43 – (V3 + U4) = 23 – (15 - 13) = 21;                 

Среди характеристик свободных клеток есть две отрицательные (Е21 = -10 и Е31 = -14), значит полученный план не оптимален.

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

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

Z2 = 15·17 + 90∙12 + 70∙11 + 80∙10 + 135∙22 + 25·27 + 85·7 = 7145 д.е.

что меньше первого плана на 1120 ден. ед.

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

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

Его цена:

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

что меньше второго плана на 195 ден. ед.

Этот план оптимальный, т.к. все характеристики свободных клеток положительны.

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

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

Минимальная стоимость перевозок (6) в клетке а2b1 – отправляем весь груз из а2 потребителю b1 и строку а2 исключаем из дальнейшего рассмотрения.

Следующий минимум (7) в клетке а4b4 – отправляем весь груз из а4 потребителю b4 и строку а4 исключаем из дальнейшего рассмотрения.

Следующий минимум (10) в клетке а3b1 – закрываем потребность b1 поставкой из а3 и столбец b1 исключаем из дальнейшего рассмотрения.

Следующий минимум (12) в клетке а1b2 – весь груз из а1 отправляем в b2 и строку а1 исключаем из дальнейшего рассмотрения.

Следующий минимум (19) в клетке а3b2 – закрываем потребность b2 поставкой из а3 и столбец b2 исключаем из дальнейшего рассмотрения.

Поставкой остатка груза из а3 закрываем потребности b3 и b4.

Опорный план составлен.

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

Z1 = 105·12 + 70∙6 + 25∙10 + 55∙19 + 135∙22 + 25·27 + 85·7 = 7215 д.е.

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

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

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

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

Среди характеристик свободных клеток есть одна отрицательная (Е22 = -4), значит полученный план не оптимален.

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