Методическая разработка лабораторной работы "Решение транспортной задачи"

Лабораторная работа 3.

Решение транспортной задачи

ЦЕЛЬ РАБОТЫ: научиться определять опорной план транспортной задачи методами «северо-западного угла», минимального элемента и аппроксимации Фогеля; научиться определять оптимальный план транспортной задачи в ПО Microsoft Excel.

ОБОРУДОВАНИЕ: ПК IBM, ПО Microsoft Excel.

ВРЕМЯ ВЫПОЛНЕНИЯ: 90 минут.

КРАТКАЯ ТЕОРИЯ И МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

Для нахождения опорного плана транспортной задачи используются 3 метода:

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

При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шагу рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного х₁₁ («северо-западный угол») и заканчивается клеткой для неизвестного x_mn, т.е. идет как бы по диагонали таблицы. При этом в клетку записывается минимальное значение между запасами и потребностями.

1. Метод минимального элемента

Сущность метода минимального элемента состоит в выборе клетки с минимальным тарифом. Если таких клеток несколько, то можно взять любую из них.

1. Метод аппроксимации Фогеля

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

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

Нахождение оптимального плана транспортной задачи с помощью ПО Microsoft Excel

Рассмотрим следующую транспортную задачу. Для строительства четырех объектов используется кирпич, изготавливаемый на трех заводах. Ежедневно каждый из заводов может изготовить 100, 150 и 50 условных единиц кирпича (предложение поставщиков). Потребности в кирпиче на каждом из строящихся объектов ежедневно составляют 75, 80, 60 и 85 условных единиц (спрос потребителей). Тарифы перевозок одной условной единицы кирпича с каждого из заводов к каждому из строящихся объектов задаются матрицей транспортных расходов С.

Требуется составить такой план перевозок кирпича к строящимся объектам, при котором общая стоимость перевозок будет минимальной.

Решение в программе Microsoft Excel

1. Ввести исходные данные как на рис. 1

рис. 1

1. Заполнить ячейки с помощью формул (результат на рис. 2):

   1. Все ячейки диапазона B10:E12 – числами 0,01

   2. Ячейка G10 – формула =СУММ(B10:E10) (скопировать эту формулу вниз до ячейки G12)

   3. Ячейка B14 – формула =СУММ(B10:B12) (скопировать эту формулу вправо до ячейки E14)

   4. Ячейка В16 – формула =СУММПРОИЗВ(B2:B4;B10:B12)

   5. Ячейка G16 – формула =СУММ(B16:E16)

рис. 2

1. Поставьте курсор в ячейку G16 и выберите команду меню Данные – Поиск решения. Заполните появившееся окно, как показано на рис. 3. В параметрах окна поставьте галочку на переключателе «Линейная модель». Нажмите кнопку Выполнить.

рис. 3

1. Результат решения рис. 4

рис. 4

ПОРЯДОК ВЫПОЛНЕНИЯ И ФОРМА ОТЧЕТНОСТИ

Задание 1. Найти план перевозок транспортной задачи согласно своему варианту методом «северо-западного угла», методом минимального элемента и аппроксимации Фогеля.

I вариант

Н а трех складах А₁, А₂, А₃ оптовой базы сосредоточен однородный груз в количествах 180, 60 и 80 ед. Этот груз необходимо перевезти в четыре магазина В₁, В₂, В₃, В₄. Каждый из магазинов должен получить соответственно 120, 40, 60 и 80 ед. Тарифы перевозок единицы груза из каждого из складов во все магазины задаются матрицей:

II вариант

Производственное объединение имеет в своем составе три филиала А₁, А₂, А₃, которые производят однородную продукцию соответственно в количествах, равных 50, 30 и 10 ед. Эту продукцию получают четыре потребителя В₁, В₂, В₃, В₄, расположенные в разных местах. Их потребности соответственно равны 30, 30, 10 и 30 ед. Тарифы перевозок единицы груза от каждого из филиалов соответствующим потребителям задаются матрицей:

III вариант

Три предприятия данного экономического района А₁, А₂, А₃ могут производить некоторую однородную продукцию в количествах соответственно равных 180, 350 и 20 ед. Эта продукция должна быть поставлена пяти потребителям В₁, В₂, В₃, В_4, В₅ в количествах, соответственно равных 110, 90, 120, 80 и 150 ед. Затраты, связанные с производством и доставкой единицы продукции, задаются матрицей:

IV вариант

На три базы А₁, А₂, А₃ поступил однородный товар в количествах, соответственно равных 115, 175 и 130 ед. Этот груз требуется перевезти в пять пунктов назначения В₁, В₂, В₃, В₄, В₅ соответственно в количествах 70, 220, 40, 30, 60 ед. Тарифы перевозок приведены в виде матрицы:

V вариант

Н а четыре базы А₁, А₂, А_3, А₄ поступил однородный товар в количествах, соответственно равных 280, 175, 125 и 130 ед. Этот груз требуется перевезти в четыре пункта назначения В₁, В₂, В₃, В₄, соответственно в количествах 90, 180, 310, 130 ед. Тарифы перевозок приведены в виде матрицы:

VI вариант

На три базы А₁, А₂, А₃ поступил однородный товар в количествах, соответственно равных 510, 90, 120 ед. Этот груз требуется перевезти в четыре пункта назначения В₁, В₂, В₃, В₄, соответственно в количествах 270, 140, 200, 110 ед. Тарифы перевозок приведены в виде матрицы:

Задание 2. Выполнить задание «Нахождение оптимального плана транспортной задачи с помощью ПО Microsoft Excel» из методических указаний.

Задание 3. Найти оптимальное решение для задачи своего варианта в программе Microsoft Excel.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Что такое транспортная задача?

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