Классическая транспортная задача

Рассмотрим простейшую задачу, возникающую при моделировании транспортных потоков. Для простоты рассматривается вопрос об организации перевозок лишь какого-то одного продукта от пунктов, в которых он производится (или складируется), к потребителям, расположенным в других пунктах. Пусть имеется m пунктов производства и n пунктов потребления. Известно, что в i-ом пункте производства имеется a _i единиц рассматриваемого продукта, а объем его потребления в j-ом пункте потребления составляет b _j единиц. Для простоты предположим, что затраты на перевозку продукта из i-го пункта производства в j-й пункт потребления пропорциональны объему поставки, а значит, легко вычисляются, если заданы величины с _ij, указывающие стоимость перевозки единицы продукта. Пусть эти величины известны. Требуется спланировать перевозки так, чтобы суммарные затраты на реализацию предлагаемого плана были как можно меньше. Ясно, что задачу имеет смысл рассматривать лишь в предположении, что суммарный объем производства не меньше суммарного объема потребления, т.е. Обозначим через y _ij объем планируемой поставки продукта из i-го пункта производства в j-й пункт потребления. Тогда суммарный объем вывоза из i-го пункта производства будет равен
 а суммарный объем поставки в j-й пункт потребления составит Затраты на реализацию всех перевозок будут задаваться формулой

В результате получаем следующую классическую транспортную задачу:

Первое неравенство означает, что количество продукта, вывезенного со склада, не должно превышать запаса, второе – что потребности каждого пункта должны быть удовлетворены. Несмотря на кажущееся полное внешнее отличие получаемой математической задачи от той, которую мы получили при рассмотрении рационов кормления, на самом деле это задачи одного класса: требуется минимизировать некоторую линейную функцию при линейных ограничениях на переменные.

Если выполнено условие = , то это гарантирует, что все заявки будут выполнены полностью и из каждого пункта отправления будет вывезен весь груз. В этом случае транспортная задача называется закрытой (сбалансированной). Это условие обеспечивает существование оптимального решения задачи. В противном случае задача называется открытой. Математическая формулировка закрытой транспортной задачи будет иметь вид

,

,

,

 

 

Пример 6. Имеются два склада А₁ и А₂ и три магазина В₁, В₂ и В₃. Наличие товара на складах и запросы магазинов, а также стоимость доставки указаны в следующей таблице:

bj ai	50	20	30
50	10	15	25
60	20	30	30

Составим экономико-математическую модель транспортной задачи.

Проверим условие сбалансированности: 50+60≠50+20+30. То есть, задача будет открытой. Тогда транспортная задача будет иметь вид:

Вектор неизвестных транспортной задачи имеет  вид .

Пример 7. Имеются два склада А₁ и А₂ и два магазина В₁ и В₂. Наличие товара на складах и запросы магазинов, а также стоимость доставки указаны в следующей таблице:

 

bj ai	20	20
25	3	4
15	5	2

Составим экономико-математическую модель транспортной задачи.

Проверим условие сбалансированности: 20+20=25+15=40. То есть, задача будет закрытой. Тогда транспортная задача будет иметь вид:

Вектор неизвестных транспортной задачи имеет вид .

 

 

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

Для решения задач ЛП произвольной размерности рекомендуем воспользоваться компьютером надстройкой «Поиск решения» для Microsoft Office Excel. На страницах Microsoft Office Online доступны сведения об установке этой настройки и примеры использования.

Задача о контракте

Предположим, что некий предприниматель обдумывает вопрос о заключении контракта на выполнение определенного заказа. Для выполнения всего объема работ нужно привлечь специалистов разного профиля. Допустим нужно n различных специалистов. Пронумеруем их и будем отождествлять каждого специалиста с его номером. Таким образом, {1, 2,..., n} − множество всех требуемых специалистов. Известно, что специалисты могут объединяться в различные творческие коллективы − коалиции, и каждая такая коалиция S Ì{1, 2,..., n} может сама организовывать свое дело и получать при этом доход V(S). Будем для простоты считать, что любая коалиция допустима, но если коалиция S «плохая», то V(S)=0.

Ясно, что если наш предприниматель предложит участникам коалиции S такие оклады, что в сумме они получат меньше, чем V(S), то они не согласятся участвовать в деле предпринимателя, а организуют свое дело. Предпринимателю необходимо знать, какая минимальная сумма контракта позволит заинтересовать всех требуемых специалистов.

Обозначим через x _j величину оклада, который предприниматель намерен предложить j-му специалисту. Тогда задача предпринимателя примет вид:

 

! Задания для самостоятельного решения:

 

1. С Курского вокзала Москвы ежедневно отправляются скорые и пассажирские поезда. Построить модель задачи, с помощью которой можно определить оптимальное количество поездов обоих типов, обеспечивающих максимальное количество ежедневно отправляемых пассажиров с вокзала, если пассажировместимость и количество вагонов железнодорожного депо станции отправления указаны в таблице.

Тип вагона		Багаж- ный	Почто- вый	Плац- картный	Купей- ный	Мягкий
Количество вагонов в поезде	скорый	1	1	8	4	1
	пассажир- ский	1	0	5	6	3
Пассажировмести - тельность, чел.				58	36	18
Парк вагонов		10	8	80	70	30

2. Правление некоторого банка сочло возможным инвестировать капитал суммой 300 тыс. долл. в 6 конкретных проектов. Эксперты оценили годовую эффективность каждого проекта на два года следующим образом:

 

	Номер проекта
	1	2	3	4	5	6
1 -й год	0,12	0,14	0,15	0,10	0,18	0,25
2 -й год	0,10	0,10	0,12	0,18	0,12	0,15

 

Менеджер по инвестициям считает, что не стоит вкладывать в проект 5 более 40 тыс. долл., а в проекты 4 и 6 более 25% от общей денежной суммы ввиду высокой вероятности риска, соответствующего этим проектам. В то же время не менее 40% денежных средств желательно поместить в проекты 1 и 2. Найти план инвестиций в каждый проект с целью максимизации дохода.

3. Фирма производит и продает столы и шкафы из древесины хвойных и лиственных пород. Расход каждого вида в кубометрах на каждое изделие задан в таблице.

 

	Расход древесины, м3.		Цена изделия,   тыс. руб.
	хвойные	лиственные
Стол	0,15	0,2	0,8
Шкаф	0,3	0,1	1,5
Запасы древесины, м3.	75	40

 

Определите оптимальное количество столов и шкафов, которое следует поставлять на продажу для получения максимального дохода фирмы.

4. Кондитерская фабрика для производства карамели использует три вида основного сырья: сахарный песок, патоку и фруктовое пюре. Нормы расходов сырья каждого вида на производство 1 килограмма карамели каждого вида приведены в таблице.

Сырье	Норма расхода (килограммов на 1 кг карамели)
	«Сахарная»	«Детская»	«Фруктовая»
Сахар-песок	0,8	0,6	0,5
Патока	0,2	0,3	0,4
Фруктовое пюре	0	0,1	0,1

В сутки фабрика получает 800 кг сахара-песка, 600 кг патоки и 120 кг фруктового пюре. Изучение покупательского спроса показало, что суточное производство «Детской» карамели не должно превышать 300 кг. Доход от реализации 1 кг карамели составляет 27 рублей для «Сахарной» карамели, 32 рубля — для «Детской» и 28 рублей — для «Фруктовой». Составьте задачу линейного программирования о производстве с целью получения максимального дохода.

5. Предприятие может выпускать три вида сувенирной продукции, сбыт любого количества которой обеспечен. Для изготовления используются трудовые ресурсы, полуфабрикаты и станочное оборудование. Расход каждого ресурса на единицу выпускаемой продукции, приведен в таблице.

Ресурс	Норма расхода (на единицу продукции)
	«Сибирь»	«Наш край»	«Новосибирск»
Затраты труда (часов)	4	2	2
Сырье (кг)	2	10	6
Станочное оборудование (часов)	1	0	2

В течение недели предприятие может задействовать 4800 часов труда работников, 2400 кг сырья и 1500 часов работы станков. Доход от реализации сувенира составляет 65, 70 и 60 рублей соответственно. Составьте задачу линейного программирования о производстве с целью получения максимального дохода.

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

Участок	Затраты труда на единицу продукции в часах
	«Классический»	«Новый»	«Антикварный»
Лесопильный	1	2	4
Сборочный	2	4	2
Отделочный	1	1	2

В течение недели можно планировать работу на лесопилке на 360 человеко-часов, в сборочном цехе — на 520 человеко-часов, в отделочном цехе — на 220 человеко-часов. Доход от продажи шкафа каждой из моделей составляет, соответственно, 9000, 11000 и 15000 рублей. Составьте задачу линейного программирования о производстве с целью получения максимального дохода.

7.  Караван Марко Поло использует для перевозки сухого инжира из Багдада в Мекку дромадеров (одногорбых верблюдов) и обычных (двугорбых) верблюдов. Верблюд может нести 1000 фунтов груза, а дромадер — 500 фунтов. За время пути верблюд потребляет 3 тюка сена и 100 галлонов воды, а дромадер — 4 тюка сена и 80 галлонов воды. Вдоль пути Марко Поло имеются пункты снабжения, расположенные в оазисах. Общая емкость запасов на этих участках 1600 галлонов воды и 60 тюков сена. Верблюды и дромадеры нанимаются у пастуха около Багдада. Стоимость аренды верблюда составляет 11 монет, а дромадера — 5 монет. Караван должен доставить из Багдада в Мекку не менее 10000 фунтов инжира. Составьте задачу линейного программирования о минимальных издержках на аренду верблюдов и дромадеров. Решить задачу графическим методом. Сколько потребуется верблюдов и дромадеров, чтобы арендная плата пастуху была минимальной?

8. Рацион кормления домашнего животного может состоять из трех имеющихся концентратов: «Вкусного», «Полезного» и «Питательного». Содержание полезных веществ — белка, кальция и витаминов — в килограмме каждого концентрата приведено в таблице.

Полезное вещество	Затраты труда на единицу продукции в часах
	«Вкусный»	«Полезный»	«Питательный»
Белок	50	70	180
Кальций	10	6	3
Витамины	2	3	1

Суточные нормы потребления белка, кальция и витаминов составляют, соответственно, 20 г, 2,1 г и 87 мг. Килограмм концентрата стоит, соответственно, 30, 40 и 120 рублей. Составьте задачу линейного программирования о рационе минимальной стоимости.

9. Средства очистки пола оценивают по трем показателям: очищающие свойства, дезинфицирующие свойства, раздражающее воздействие на кожу. Каждый из этих показателей измеряется по линейной шкале от 0 до 100 единиц. Смесь для очистки пола составляется из трех основных очистителей, характеристики которых приводятся в таблице.

Свойства	Основной очиститель
	А	Б	В
Очищающие	90	65	45
Дезинфицирующие	70	50	10
Раздражающие	30	85	70

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

10. Решить следующую задачу линейного программирования графическим методом  

11. Решить следующую задачу линейного программирования графическим методом  

12. Решить следующую задачу линейного программирования используя теорию двойственности 

13. Решить следующую задачу линейного программирования используя теорию двойственности 

14. Решить следующую задачу линейного программирования используя теорию двойственности 

1. Три предприятия выпускают товары в количествах равных 200 т, 250 т, 350 т соответственно. Эти товары следует доставить на четыре базы, потребности которых составляют 170 т, 120 т, 280 т и 230 т соответственно. Тарифы перевозок товаров с каждого предприятия в соответствующие пункты назначения заданы матрицей . Составить экономико-математическую модель транспортной задачи.

16. На трех элеваторах находится зерно в количествах 225 т, 250 т, 25 т соответственно, которое необходимо доставить в четыре фермерских хозяйства, заявки которых составляют 120 т, 150 т, 110 т, 135 т соответственно. Стоимость доставки зерна от элеваторов к соответствующим хозяйствам задана матрицей тарифов . Составить экономико-математическую модель транспортной задачи.

 

Контрольные вопросы и задания

1. Какие задачи линейного программирования решаются графическим методом?

2. Что называется областью допустимых решений?

3. Как найти область допустимых решений?

4. С какой целью определяется градиент целевой функции?

5. Как определяется положение линии уровня?

6. Как составляются целевая функция, ограничения и условия для двойственных задач?

7. Сформулируйте теорему равновесия.

8. Сформулируйте задачу о диете.

9. Сформулируйте классическую транспортную задачу.

10. В чем отличие открытой и закрытой транспортной задачи?

 

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

1. Красс, М.С. Математика для экономистов: Учеб. пособие / М. С. Красс, Б. П. Чупрынов. - СПб.: Питер, 2004. - 464 с.,с.344-421.

2. Шикин, Е.В., Чхартишвили, А.Г. Математические методы и модели в управлении: Учеб. Пособие.−2-е изд., испр.−М.: Дело, 2002.−440 с., с.65-79.

3. Сборник задач по высшей математике для экономистов: учеб. пособие / Под ред. В.И. Ермакова. – 2-е изд., испр. – М.: ИНФРА-М, 2007. – 575 с., с.412-497.

4. Осипов, А.Л. Математика: учеб. пособие для дистанц. обучения и самост. работы / А. Л. Осипов, Е. А. Рапоцевич; СибАГС. - Новосибирск, 2005. - 276 с.- То же [Электронный ресурс]. – Доступ из Б-ки электрон. изданий / Сиб. ин-т упр. – филиал РАНХиГС. – Режим доступа: http://www.sapanet.ru, требуется авторизация (дата обращения: 19.03.2013). - Загл. c экрана.