Транспортная задача линейного программирования

Транспортная задача линейного программирования

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

Транспортная задача – это задача, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов. Примером типичной транспортной задачи является распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям.

Стандартная ТЗ определяется как задача разработки наиболее экономичного плана перевозки продукции одного вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции.

Пример 1. Три поставщика одного и того же продукта располагают в планируемый период следующими запасами этого продукта: первый- 120 условных единиц, второй- 100 и третий 80 единиц. Этот продукт должен быть перевезен к трем потребителям, спросы которых соответственно равны 90, 90 и 120 условных единиц. Приведенная ниже таблица содержит показатели затрат, связанных с перевозкой продукта из i -го пункта отправления в j -й пункт потребления.

Требуется перевезти продукт с минимальными затратами.

Поставщики	Потребители и их спрос	Запасы
	А	Б	В
I
II
III
Спрос

Составим математическую модель задачи.

Пусть –I поставщиком, А-му потребителю, тогда , – количество единиц продукта перевозимого этим же поставщиком Б-му и В-му потребителю соответственно.

Целевая функция в этом случае имеет вид:

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

Вид электронной таблицы Excel, созданной для решения задачи, в режиме отображения формул, представлен на рис. 1. Искомые значения находятся в блоке ячеек B4:D6. Адрес данного блока входит в поле ввода Изменяя ячейки в окне “Поиск решения”. Требования к ограничениям по спросу и запасам представлены соответственно в ячейках B7:D7 и E4:E6. Коэффициенты ЦФ, означающие затраты на доставку расположены в блоке ячеек B12:D14.

Формулы целевой функции и ограничений находятся соответственно в ячейке F8 и ячейках B8:D8 (ограничения по спросу), F4:F6 (ограничения по запасам).

Рис.1

Результаты поиска решения представлены на рис. 2. Значение ЦФ=1060.

Рис. 2

Данная задача является сбалансированной, в ней общее наличие продукта у поставщиков равно общей потребности в продукте потребителей. На практике возможны случаи, когда эти параметры не совпадают. Тогда в рассмотрение вводятся фиктивная фабрика или фиктивный магазин, которые позволяют свести задачу к сбалансированной.

Методом транспортной задачи решаются экономические задачи, которые по своему характеру не имеют ничего общего с транспортировкой груза, поэтому коэффициенты целевой функции могут иметь различный смысл (в зависимости от конкретной задачи. Они могут означать стоимость, расстояние время, производительность и т. д. Рассмотрим постановку и математические модели некоторых задач.

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

Требуется распределить самолеты по авиалиниям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по каждой из четырех авиалиний соответственно не менее 300, 200, 1000 и 500 единиц груза.

Тип самолета	Число самолетов	Месячный объем перевозок одним самолетом по авиалиниям
		I	II	III	IV
Тип самолета	Эксплуатационные расходы
	I	II	III	IV

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

Ограничения имеют вид:

Рис. 3

Вид электронной таблицы Excel, созданной для решения задачи, в режиме отображения формул, представлен на рис. 3. Значения переменных располагаются в блоке ячеек B21:E23. Коэффициенты целевой функции, отражающие расходы на перевозку находятся по адресам B37:E39. Данные о месячных объемах перевозок одним самолетом имеются в блоке B29:E31. Задан план перевозок и число самолетов – соответственно блоки B24:E24 и F21:F21. Формулы целевой функции и ограничений находятся соответственно в ячейке F25 и ячейках B25:E25 (ограничения по плану), F21:F23 (ограничения по количеству самолетов). Результаты поиска решения приведены на рис. 4.

Рис.4

Пример 3. Имеются три механизма М1, М2, М3, каждый из которых может быть использован на трех видах работ Р1, Р2, Р3 с производительностью (в условных единицах), заданной в виде таблицы:

Механизмы	Работы
	Р1	Р2	Р3
М1
М2
М3

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

Целевая функция имеет вид:

Ограничения имеют вид:

Вид электронной таблицы Excel, созданной для решения задачи, в режиме отображения формул, представлен на рис. 5. Значения переменных x_ij располагаются в блоке ячеек B45:D47. Коэффициенты целевой функции, отражающие производительность механизмов, находятся по адресам B53:D55. Формулы целевой функции и ограничений находятся соответственно в ячейке E49 и ячейках E45:E47 (каждый механизм может быть назначен только на одну работу), B49:D49 (каждая работа выполняется только на одном механизме)

Рис. 5

Результаты поиска решения приведены на рис. 6. Значение ЦФ=10

Рис. 6

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

Задача 1. В машину необходимо поместить четыре вида предметов, причем могут потребоваться несколько одинаковых предметов. Имеется три вида ограничений такого типа, как вес, объем и т.д. В приведенной ниже таблице даны – i -я характеристика предмета j -го наименования, c_j - полезность одного предмета j-го наименования. Требуется загрузить машину так, чтобы суммарная полезность груза была максимальной.

Ограничения	Предмет1	Предмет2	Предмет3	Предмет4	Значения ограничений
I
II
III
Полезность

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

Ограничения имеют вид:

Ответ: Значение ЦФ=556.

Значения переменных x_ij располагаются в блоке ячеек B4:E4. Коэффициенты целевой функции, отражающие полезности предметов находятся по адресам B7:E7. Данные о характеристиках предметов имеются в блоке B10:E12. Заданы значения ограничений- соответственно блок H10:H12. Формулы целевой функции и ограничений находятся соответственно в ячейке F7 и ячейках F10:E12 (ограничения по свойствам).

Задача 2. Фирма обслуживает 5 клиентов. Каждый день она доставляет своим клиентам товары на грузовых машинах. Существует 3 допустимых маршрута доставки, каждый из которых позволяет обслужить определенное количество клиентов и требует использования в течении дня одного транспортного средства. Каждый маршрут характеризуется определенными расходами (см. табл.). Необходимо выбрать такое множество маршрутов, при котором обеспечивается обслуживание каждого из клиентов и, кроме того, суммарные расходы минимальны, при условии, что каждый клиент обслуживается один раз в день.

Таблица обслуживания клиентов по маршрутам
Клиенты	Маршруты
Расходы по маршруту

Целевая функция имеет вид:

Ограничения имеют вид:

Также задаются ограничения x_ij <=1, и по целочисленности.

Ответ: Значение ЦФ=610

Задача 3. Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140 и 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Задача 4. Для строительства трех объектов используется кирпич, изготовляемый на трех заводах. Ежедневно каждый из заводов может изготовлять 100, 150 и 50 ус. ед. кирпича. Ежедневные потребности в кирпиче на каждом из строящихся объектов соответственно равны 75, 80, 60 и 85 усл. ед. Известны также тарифы перевозок 1 усл. ед. кирпича с каждого завода к каждому из строящихся объектов.

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

Задача 6.. Дано распределения самолетов трех типов по четырем маршрутам. Характеристики парка самолетов и движения по авиалиниям приведены в таблице.

Тип самолета	Число пассажиров	Колич. cамолетов	Количество рейсов в сутки на каждом маршруте
Суточный пассажиропоток
Тип самолета	Эксплуатац. расходы на 1 рейс по данному маршруту, $
Убыток от неудовлетворенного спроса (на одного неперевезенного пассажира)

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

Дата добавления: 2015-11-04