Главная страница
Навигация по странице:

  • Цель работы

  • Этап 1. Определение начального базисного допустимого решения.

  • Этап 2. Поиск оптимального решения транспортной задачи.

  • Использование среды Excel для решения транспортных задач

    		•

    шпоргалка. Лабораторная работа 4 Исследование и определение оптимального распределения поставок и минимальных затрат при решении транспортных задач


    Скачать 44.42 Kb.
    НазваниеЛабораторная работа 4 Исследование и определение оптимального распределения поставок и минимальных затрат при решении транспортных задач
    Анкоршпоргалка
    Дата07.05.2022
    Размер44.42 Kb.
    Формат файлаdocx
    Имя файлаlab4_prikladnaya_matematika.docx
    ТипЛабораторная работа
    #515901

    Министерство образования Республики Беларусь

    Белорусский национальный технический университет

    Кафедра “Тепловые электрические станции”

    Группа 10604119

    Исследование и определение оптимального распределения

    поставок и минимальных затрат при решении транспортных
    Отчёт по лабораторной работе №4

    по дисциплине “Методы математического программирования”

    Исполнитель: Пиртань А.А.

    Руководитель: Бадак Б.А

    Минск-2022

    Лабораторная работа № 4
    Исследование и определение оптимального распределения

    поставок и минимальных затрат при решении транспортных задач
    Цель работы: Приобретение студентами практических навыков решения транспортных задач и использования инструмента Поиск решения среды Excel для нахождения оптимального распределения поставок и минимальных затрат.

    Вариант 2

    Транспортная компания занимается перевозкой зерна специальными

    зерновозами от трех элеваторов к четырем мельницам. Максимально

    возможное количество отгружаемых зерновозов в сутки составляет 100, 120, 150, 130. Суточные потребности мельниц составляют 100, 130, 90 и 140 зерновозов. Затраты на перевозку зерна от i -го элеватора к j -ой мельнице в тыс. руб. представлены в виде матрицы.

    Требуется определить структуру перевозок между элеваторами и

    мельницами с минимальной стоимостью.

    Решение:

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

    Таблица 1 – Транспортная таблица

    Элеваторы
    Мельницы
    Предложение

    1
    2
    3
    4



    1


    4


    5


    5


    7
    100

    2


    8


    7


    5


    4
    120

    3


    9


    6


    4


    4
    150

    4


    3


    2


    9


    5
    130

    Спрос
    140
    130
    90
    140




    Решение транспортной задачи состоит из двух этапов.

    1. Определение начального базисного допустимого решения.

    2. Поиск оптимального решения транспортной задачи.

    Этап 1. Определение начального базисного допустимого решения.

    Используем метод северо-западного угла. Выполнение начинается с

    верхней левой ячейки (северо-западного угла) транспортной таблицы, т.е. с

    переменной .

    Шаг 1. Переменной присваивается максимальное значение, допускаемое ограничениями на спрос и предложение.

    Шаг 2. Вычеркивается строка (или столбец) с полностью

    реализованным предложением (с удовлетворенным спросом). Это означает,

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

    Если одновременно удовлетворяются спрос и предложение, вычеркивается

    только строка или только столбец.

    Шаг 3. Если не вычеркнута только одна строка или только один столбец, процесс останавливается. В противном случае переходим к ячейке справа, если вычеркнут столбец, или к нижележащей ячейке, если вычеркнута строка. Затем возвращаемся к первому этапу. Применив описанную процедуру, получим начальное базисное решение, представленное в табл. 2. В этой таблице стрелками показана последовательность определения базисных переменных.
    Таблица 2 – Базисное решение транспортной задачи
    1
    2
    3
    4
    Предложение

    1
    4[100]
    5
    5
    7
    100

    2
    8[40]
    7[80]
    5
    4
    120

    3
    9
    6[50]
    4[90]
    5[10]
    150

    4
    3
    2
    9
    3[130]
    130

    Спрос
    140
    130
    90
    140




    Получено следующее начальное базисное решение:



    Соответствующая суммарная стоимость перевозок равна:
    Z =4 ⋅ 100 + 8 ⋅40 + 7 ⋅ 80 + 6 ⋅50 + 4 ⋅ 90 +4 ⋅10+5 ⋅130 = 2380 руб.
    Этап 2. Поиск оптимального решения транспортной задачи.

    Используя полученное начальное базисное решение, произведем

    улучшение плана перевозок. В таблице 3.2 назначим потенциалы строк и

    столбцов. В методе потенциалов каждой i -ой строке и каждому j -му

    столбцу транспортной таблицы ставятся в соответствие числа (потенциалы) и , которые для базисных переменных удовлетворяют уравнению

    .

    Примем , тогда


    Используя найденные значения потенциалов, для каждой небазисной

    переменной вычислим величины оценки

    Найденные значения поместим в таблицу 3.

    Таблица 3 – Модифицированная транспортная таблица
    v1=4
    v2=3
    v3=1
    v4=2
    Предложение

    u1=0
    4[100]
    5
    5
    7
    100

    u2=4
    8[40]
    7[80]
    5
    4
    120

    u3=3
    9
    6[50]
    4[90]
    5[10]
    150

    u4=1
    3
    2
    9
    3[130]
    130

    Спрос
    140
    130
    90
    140




    Среди небазисных переменных выберем переменную, имеющую

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

    Построим замкнутый цикл перерасчета, включающий базовое распределение поставок и выбранную нами ячейку (табл. 4).

    Таблица 4 – Замкнутый цикл перерасчета для переменной .
    1
    2
    3
    4
    Предложения

    1
    4[100]
    5
    5
    7
    100

    2
    8[40]
    7[80][-]
    5
    4[+]
    120

    3
    9
    6[50][+]
    4[90]
    5[10][-]
    150

    4
    3
    2
    9
    3[130]
    130

    Спрос
    140
    130
    90
    140




    Для удовлетворения ограничения по спросу и предложению, нужно поочередно отнимать и прибавлять к значениям базисных переменных, выбрав из грузов  стоящих в минусовых клетках наименьшее, т.е. , в результате получим новое базисное решение (табл. 5):


    Таблица 5 – Транспортная таблица для второго базисного решения
    1
    2
    3
    4
    Предложения

    1
    4[100]
    5
    5
    7
    100

    2
    8[40]
    7[70]
    5
    4[10]
    120

    3
    9
    6[60]
    4[90]
    5
    150

    4
    3
    2
    9
    3[130]
    130

    Спрос
    140
    130
    90
    140




    Произведем вычисление новых значений потенциалов для строк и

    столбцов, по описанной выше методике. Определим для каждой небазисной

    переменной величины оценки . Результаты приведены в табл. 6
    Таблица 6 – Модифицированная транспортная таблица (2)
    v1=4
    v2=3
    v3=1
    v4=0
    Предложения

    u1=0
    4[100]
    5
    5
    7
    100

    u2=4
    8[40]
    7[70]
    5
    4[10]
    120

    u3=3
    9
    6[60]
    4[90]
    5
    150

    u4=3
    3
    2
    9
    3[130]
    130

    Спрос
    140
    130
    90
    140




    Выбираем максимальное значение величины оценки, соответствующее ячейке . Строим замкнутый цикл (табл. 7).

    Таблица 7 – Замкнутый цикл перерасчета для переменной




    1
    2
    3
    4
    Предложения

    1
    4[100]
    5
    5
    7
    100

    2
    8[40][-]
    7[70]
    5
    4[10][+]
    120

    3
    9
    6[60]
    4[90]
    5
    150

    4
    3[+]
    2
    9
    3[130][-]
    130

    Спрос
    140
    130
    90
    140




    Новое решение показано в табл. 8.
    Таблица 8 – Транспортная таблица для третьего базисного решения
    1
    2
    3
    4
    Предложения

    1
    4[100]
    5
    5
    7
    100

    2
    8
    7[70]
    5
    4[50]
    120

    3
    9
    6[60]
    4[90]
    5
    150

    4
    3[40]
    2
    9
    3[90]
    130

    Спрос
    140
    130
    90
    140




    Произведем вычисление новых значений потенциалов для строк и

    столбцов, по описанной выше методике. Определим для каждой небазисной

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

    Таблица 9 – Модифицированная транспортная таблица (3)
    v1=4
    v2=7
    v3=5
    v4=4
    Предложения

    u1=0
    4[100]
    5
    5
    7
    100

    u2=0
    8
    7[70]
    5
    4[50]
    120

    u3=-1
    9
    6[60]
    4[90]
    5
    150

    u4=-1
    3[40]
    2
    9
    3[90]
    130

    Спрос
    140
    130
    90
    140



    Выбираем максимальное значение величины оценки, соответствующее ячейке . Строим замкнутый цикл (табл. 10).
    Таблица 10 – Замкнутый цикл перерасчета для переменной




    1
    2
    3
    4
    Предложения

    1
    4[100]
    5
    5
    7
    100

    2
    8
    7[70][-]
    5
    4[50][+]
    120

    3
    9
    6[60]
    4[90]
    5
    150

    4
    3[40]
    2[+]
    9
    3[90][-]
    130

    Спрос
    140
    130
    90
    140




    Новое решение показано в табл. 8.

    Таблица 8 – Транспортная таблица для третьего базисного решения
    1
    2
    3
    4
    Предложения

    1
    4[100]
    5
    5
    7
    100

    2
    8
    7
    5
    4[120]
    120

    3
    9
    6[60]
    4[90]
    5
    150

    4
    3[40]
    2[70]
    9
    3[20]
    130

    Спрос
    140
    130
    90
    140





    Таблица 9 – Модифицированная транспортная таблица (3)
    v1=4
    v2=3
    v3=1
    v4=4
    Предложения

    u1=0
    4[100]
    5
    5
    7
    100

    u2=0
    8
    7
    5
    4[120]
    120

    u3=3
    9
    6[60]
    4[90]
    5
    150

    u4=-1
    3[40]
    2[70]
    9
    3[20]
    130

    Спрос
    140
    130
    90
    140




    Таблица 10 – Замкнутый цикл перерасчета для переменной





    1
    2
    3
    4
    Предложения

    1
    4[100]
    5
    5
    7
    100

    2
    8
    7
    5
    4[120]
    120

    3
    9
    6[60][-]
    4[90]
    5[+]
    150

    4
    3[40]
    2[70][+]
    9
    3[20][-]
    130

    Спрос
    140
    130
    90
    140




    Новое решение показано в табл. 11.
    Таблица 11 – Транспортная таблица для четвертого базисного решения
    B1
    B2
    B3
    B4
    Предложения

    A1
    4[100]
    5
    5
    7
    100

    A2
    8
    7
    5
    4[120]
    120

    A3
    9
    6[40]
    4[90]
    5[20]
    150

    A4
    3[40]
    2[90]
    9
    3
    130

    Спрос
    140
    130
    90
    140




    Находим значение и исключаем переменную .




    v1=4
    v2=3
    v3=1
    v4=2
    Предложения

    u1=0
    4[100]
    5
    5
    7
    100

    u2=2
    8
    7
    5
    4[120]
    120

    u3=3
    9
    6[40]
    4[90]
    5[20]
    150

    u4=-1
    3[40]
    2[90]
    9
    3
    130

    Спрос
    140
    130
    90
    140




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

    Минимальные затраты составят:
    Z =4 ⋅ 100 + 4 ⋅120 + 6 ⋅ 40 + 4 ⋅90 + 5 ⋅ 20 +3 ⋅40+2 ⋅90 = 1880 руб.
    Использование среды Excel для решения транспортных задач

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


    Рисунок 1

    лаб4.xlsx

    написать администратору сайта