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

Заявки,тонн

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

Цель работы: научиться решать транспортные задачи и задачи

распределения ресурсов в среде MS Excel

Содержание работы:

1. Изучение видов транспортной задачи и методов её решения.

2. Изучение видов распределительной задачи и методов её решения.

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

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

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

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

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

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

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

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

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

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

2 Решение задачи в программе "Поиск решения"

Вид электронной таблицы 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 усл. ед. кирпича с каждого завода к каждому из строящихся объектов.

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

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

Тип самолета	Число пассажиров	Количество cамолетов	Количество рейсов в сутки на каждом маршруте




Суточный пассажиропоток
Тип самолета	Эксплуатационные расходы на 1 рейс по данному маршруту, $




Убыток от неудовлетворенного спроса (на одного неперевезенного пассажира)

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

Вариант 6. Авиакомпания «Аэрофлот» (Москва) располагает парком в 70 самолетов восьми типов.

Тип самолета	Загрузка пассажирами	Время полета без посадки, ч	Парк самолетов, шт.
минимальная	максимальная
1. ТУ-134
2. ТУ-154
3. ИЛ-62
4. ИЛ-86
5. ИЛ-96		—
6. В-737		—
7. В-777		—
8.А-310

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

Рейс	Протяженность линий, ч (т)	Количество промежуточных посадок	Объем пассажирских перевозок, чел.
I. Египет - Хургада	5,5
II. Испания - Малага	4,5
III. Япония - Токио
IV. Франция - Париж	3,5
V. США - Нью-Йорк

Вариант 7. Сельскохозяйственный кооператив «Ласточка» в области имеет три филиала Ф1, Ф2 и Ф3, которые обеспечивают поставками подсолнечных семян в соответствии с заявками пять заводов производителей подсолнечного масла А, В, С, D и Е. Объемы запасов семян, объемы заказов на поставку и тарифы на перевозку приведены в транспортной таблице.

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

Вариант 8. Фирма «Союз» обеспечивает доставку видео- и аудиокассет с четырех складов, расположенных в разных точках города в четыре магазина. Запас кассет, имеющихся на складах, а также объемы заказов магазинов и тарифы на доставку представлены в транспортной таблице.

Склады	Магазины	Запасы, тыс. шт.
№ 1	№2	№3	№4
Склад № 1
Склад №2
Склад № 3
Склад № 4
Заказы, шт.

Определите объемы перевозок, обеспечивающих их минимальные затраты.

Вариант 9. Московский филиал фирмы «The Coca-Cola Company», выпускающей газированные напитки приблизительно равного спроса (Sprite, Coca-Cola, Fanta), складируемые в разных местах, должен поставить свою продукцию в четыре крупных московских супермаркета: «Рамстор-1», «Рамстор-2». «Седьмой Континент», супермаркет «Арбатский».

Каждая упаковка содержит 12 банок емкостью 0,33 литра. Тарифы на доставку товара, объемы запасов и заказы на продукцию приведены в таблице.

Склады	Супермаркеты	Запасы
«Рамстор-1»	«Рамстор-2»	«Седьмой Континент»	«Арбатский»
Coca-Cola
Sprite
Fanta
Заказы, уп.

Определите оптимальный план поставок газированных напитков в супермаркеты города, а также затраты на перевозку.

Вариант 10. Автотранспортная компания «Астрада» обеспечивает доставку шин «Bridgestone» с трех оптовых складов, расположенных в Москве, Нижнем Новгороде и Покрове в пять магазинов в Чебоксарах, Нижнем Новгороде, Вязниках, Набережных челнах и Казани. Объемы запасов шин на складах, объемы заявок магазинов и тарифы на перевозку приведены в транспортной таблице.

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

Вариант 11. Фирма «Московия» заключила контракт с компанией АЛРОСА (Алмазы России — Саха) на покупку промышленного золота для его реализации в пяти городах в объемах: Самара — 80 кг, Москва — 260 кг, Ростов-на-Дону — 100 кг, Санкт-Петербург — 140 кг. Нижний Новгород — 120 кг.

Компания располагает тремя месторождениями «Мирное», «Удачный» и «Полевое», которые планируют за год выработать соответственно 200, 250 и 250 кг золота.

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

7 9 15 4 18

С = 13 25 8 15 5

5 11 6 20 12

Вариант 12. Составьте оптимальный план перевозки автомобилей из городов Ижевск, Казань, Тольятти в города Москва, Саранск и Ульяновск. Стоимость перевозки одного автомобиля составляет 10 руб. за км. Расстояние между городами, объемы заявок и заказов представлены в таблице.

Города	Города	Запасы, шт.
Москва	Саранск	Ульяновск
Ижевск
Казань
Тольятти
Заказы, шт.

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

Вариант 13. Составьте оптимальный план перевозки лекарств с минимальными затратами из аптечных складов в пять аптек города: больница №15, городские клинические больницы № 7, № 23 и № 50 и институтим. Бурденко. Запасы лекарств на складах, заявки потребителей и тарифы перевозок представлены в таблице.

Вариант 14. Составьте оптимальный план перевозки угля с минимальными транспортными расходами с шахт Варгашорская (В). Западная (3) и Комсомольская (К), еженедельно добывающих соответственно 26, 32 и 17 тыс. т. Покупатели угля расположены в разных городах А, В, С и D, заявки которых составляют 28,19,12 и 16 тыс. т соответственно. Тарифы определяет стоимость перевозки 1 тыс. т между поставщиками и потребителями представлены транспортной таблице.

Шахты	Потребители	Добыча угля, тыс. тонн в неделю
А	В	С	D
Западная
Варгашорская
Комсомольская
Заявки, тыс. тонн

Вариант 15. Составьте оптимальный план завоза хлебобулочной продукции с минимальными транспортными расходами из трех пекарен фирмы «Колос» в четыре булочных города: А, В, С, D. Заказы на поставку хлебобулочных изделий, производительность пекарен и транспортные тарифы представлены в транспортной таблице.

Мини-пекарни	Булочные	Производительность пекарей, кг/сутки
А	В	С	D
№1
№2
№3
Заказы, кг/сутки

Содержание отчёта:

1. Название работы

2. Цель работы

3. Содержание работы

4. Задания (без таблиц)

5. Выводы по работе