Постановка задачи

Задания для самостоятельного работы.

Пример задачи о назначениях

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

Табл. 28 Результаты собеседования

	Работа 1	Работа 2	Работа 3
Студент 1
Студент 2
Студент 3

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

Задание:

1. Написать математическую модель;

2. Найти допустимое решение методом минимального элемента и методом Фогеля;

3. Проверить оптимальность найденного решения;

4. Найти оптимальное решение;

5. Провести анализ решения на чувствительность.

Результаты работы необходимо оформить в виде отчета, который должен содержать:

1. Описание проблемы принятия решения;

2. Математическую модель проблемы в виде задачи линейного программирования транспортного типа, транспортную матрицу;

3. Сеть с оптимальным планом транспортировки.

4. Результаты анализа на чувствительность, выводы.

1. В течение 4-х месяцев фирма Sailco, производящая яхты, должна обеспечить потребности клиентов в своей продукции. Величины спроса в каждом месяце приведены в Табл. 29. В на­чале месяца 1 фирма имела в запасе (на складе) 10 яхт. Фирма хотела бы опре­делить количество яхт, которое следует производить в течение каждого из месяцев. Произведенные в текущем месяце яхты могут быть поставлены в этом же месяце потребителю или отправлены на склад для поставки потребителю в последующие месяцы. В месяц Sailco может производить 40 яхт на основном производ­стве и неограниченное количество яхт сверхпланово. Выпуск яхты на основ­ном производстве стоит $400, производство каждой сверхплановой яхты стоит $450. Хранение одной яхты на складе стоит $20 в месяц. Необходимо составить план производства и хранения яхт, удовлетворяющий весь спрос на яхты и минимизирующий суммарные затраты на производство и хране­ние.

Табл. 29 Спрос на яхты фирмы Sailco

Месяц	Спрос (шт.)
Январь
Февраль
Март
Апрель

2. Фирма TransportСo поставляет свою продукцию трем клиентам, потребность каждого из которых составляет 30 единиц продукции. У компании есть 2 склада. На первом находится 40 единиц продукции, на втором — 30 единиц. Стоимость доставки одной единицы продукции с каждого склада различным клиентам приведена в Табл. 30. За недопоставку каждой единицы продукции клиенту 1 штраф равен $90, клиенту 2 — $80, клиенту 3 — $110. Необходимо найти план поставок продукции, имеющейся на складах, минимизирующий общие затраты.

Табл. 30 Стоимость поставки единицы продукции фирмы TransportCo

Отправитель	Получатель
Клиент 1	Клиент 2	Клиент 3
Склад 1	$15	$35	$25
Склад 2	$10	$30	$40

Дополнительно. Предположим, что фирма Transportco имеет возможность закупить и доставить на склады дополнительную продукцию по цене $100 за единицу. Найти план поставок, минимизирующий стоимость поставки и дополнительной закупки продукции, при условии, что вес спрос клиентов должен быть удовлетворен.

3. Фирма Wingtip производит обувь. По оценкам менеджеров фирмы в течении следующего полугодия ожидается следующий спрос на ее продукцию (количество пар):

· Месяц 1 — 200;

· Месяц 2 — 260;

· Месяц 3 — 240;

· Месяц 4 — 340;

· Месяц 5 — 190;

· Месяц 6 — 150.

Производство одной пары на основном производстве стоит $7, а сверхплановое производство одной пары — $11. Мощность основного производства ограничена 200 парами в месяц, сверх плана можно произвести до 100 пар в месяц. Хранение одной пары на складе в течение месяца стоит $1. Необходимо найти план производства (и хранения) продукции, минимизирующий общую стоимость при условии удовлетворения всего спроса в течение полугодия.

4. Правительственным комитетом выставлены на аукцион контракты на аренду 2-х нефтеносных участков. На каждом из участков выставляется по 100 000 кв. км. земли. На аукцион подано 3 заявки — от Клифа Ивинга, Блэйка Барнса и Алекса Пайкенса. По правилам аукциона никакой из участников не должен получить более 40% участков, выставленных на аукцион. Были сделаны следующие заявки: Клиф — $1000 за кв. км. участка 1 и $2000 за кв. км. участка 2, Блэйк — $900 за кв. км. участка 1 и $2200 за кв. км. участка 2, Алекс — $1100 за кв. км. участка 1 и $1900 за кв. км. участка 2. Комитету необходимо определить, каким образом можно максимизировать свой доход.

5. Управление лесного хозяйства получило 4 заявки от подрядчиков на лесозаготовки в трех сосновых лесах округа. Эти массивы имеют площадь 10 000, 20 000 и 30 000 кв. км. Каждый подрядчик может получить для разработки не более половины всех отводимых для лесозаготовки площадей. Предлагаемые подрядчиками цены на разрешение на лесозаготовки (за 1 кв. км.) приведены в Табл. 31.

Табл. 31 Цены на разрешение лесозаготовок (за 1 кв. км.)

	Лесной массив
Подрядчик 1	$520	$210	$570
Подрядчик 2	—	$510	$495
Подрядчик 3	$650	—	$240
Подрядчик 4	$180	$430	$710

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

6. Компания Amorco Oil разрабатывает два участка по добыче нефти. Максимальный ежедневный объем добычи на участке 1 составляет 40 миллионов баррелей, на участке 2 — 50 миллионов баррелей. Стоимость добычи и очистки 1 барреля нефти на участке 1 равна $3, на участке 2 — $2. Нефть поставляется в Великобританию и Японию, стоимость доставки (на 1 баррель) приведена в Табл. 32. Великобритания готова покупать до 40 миллионов баррелей ежедневно по цене $6 за баррель, Японии — до 30 миллионов баррелей по $6,50 за баррель. Компании необходимо определить, каким образом максимизировать свою прибыль.

Табл. 32 Стоимость доставки 1 барреля нефти компании Amorco Oil

Поставщик	Потребитель
Великобритания	Япония
Участок 1	$1	$2
Участок 2	$2	$1

7. На фирме Machinco в процессе производства должны быть выполнены 4 технологические операции. Для выполнения этих операций есть 5 различных видов оборудования. Каждый тип оборудования может быть назначен для выполнения любой операции. Время, необходимое для выполнения операций на различных типах оборудования, приведено в Табл. 33. Необходимо назначить оборудование для выполнения технологических операций таким образом, чтобы минимизировать общую продолжительность выполнения указанных операций.

Табл. 33 Время, необходимое для выполнения операций

Тип оборудования.	Операция 1	Операция 2	Операция 3	Операция 4

8. Для выполнения 4-х производственных заданий на фирме имеется 5 рабочих. Время, необходимое каждым из них для выполнения соответствующих заданий, приведено в Табл. 34 (прочерк в таблице означает, что рабочий не может выполнить задание). Необходимо назначить рабочих для выполнения заданий таким образом, чтобы минимизировать общее время выполнения всех 4 заданий.

Табл. 34 Время, необходимое для выполнения заданий

	Время (час.)
Задание 1	Задание 2	Задание 3	Задание 4
Рабочий 1
Рабочий 2		—
Рабочий 3
Рабочий 4			—
Рабочий 5		—

9. Компания принимает заявки подряда на строительство 4 объектов. Заявки подали 3 фирмы–подрядчика. Их предложения (в тысячах долларов) приведены в Табл. 35 (прочерк означает, что фирма–подрядчик не подавала заявки на выполнение соответствующего подряда). Фирма 1 может выполнить только 1 подряд, каждая из фирм 2 и 3 — до 2-х подрядов. Необходимо минимизировать стоимость назначения фирм–подрядчиков на выполнение подрядов по строительству объектов.

Табл. 35 Время, необходимое для выполнения операций

	Объект 1	Объект 2	Объект 3	Объект 4
Фирма 1
Фирма 2				—
Фирма 3	—

10. В компании Touche Young работают 3 аудитора. В течение месяца каждый из них может работать до 160 часов, за этот месяц должно быть выполнено 3 проекта. Для выполнения проекта 1 необходимо 130 рабочих часов, для проекта 2 — 140 часов и для проекта 3 — 160 часов. Вознаграждение каждого из аудиторов за выполнение этих проектов приведено в Табл. 36. Необходимо определить каким образом компания может максимизировать суммарный заработок за месяц.

Табл. 36 Вознаграждение аудиторов фирмы Touche Young

	Проект 1	Проект 2	Проект 3
Аудитор 1	$120	$150	$190
Аудитор 2	$140	$130	$120
Аудитор 3	$160	$140	$150

11. Больнице необходимо приобрести 3 литра скоропортящегося лекарственного физиологического раствора для использования в текущем месяце и 4 литра — для использования в следующем месяце. Так как лекарственные растворы скоропортящиеся, то они должны быть использованы в течение того месяца, в котором они приобретены. Эти растворы продают две компании (Daisy и Laroach), но они имеют ограниченное количество этих растворов. Поэтому, в течение 2 месяцев больница не может покупать более 5 литров раствора у каждой из этих компаний. Цены на растворы приведены в Табл. 37. Необходимо определить, каким образом больница может минимизировать общую стоимость закупаемых растворов.

Табл. 37 Цены на физиологические растворы

Тип раствора	Цена за литр
Текущий месяц	Следующий месяц
Daisy	$800	$720
Laroach	$710	$750

12. Три нефтеперегонных завода с ежедневной производительностью 6, 5 и 6 миллионов тонн бензина снабжают три бензохранилища, ежедневная потребность которых составляет 4, 8 и 7 миллионов тонн бензина соответственно. Бензин транспортируется по бензопроводу. Стоимость транспортировки составляет 10 центов за 1000 тонн на 1 километр длины трубопровода. В Табл. 38 приведены расстояния в километрах между заводами и хранилищами.

Табл. 38 Расстояние между нефтеперегонными заводами и бензохранилищами

	Хранилище 1	Хранилище 2	Хранилище 3
Завод 1			—
Завод 2
Завод 3

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

Необходимо определить оптимальную схему поставок бензина.

13. Мясокомбинат имеет в своем составе четыре завода, на каждом из которых может изготавливаться три вида колбасных изделий. Мощности каждого из заводов соответственно равны 320, 280, 270 и 350 т/сутки. Ежедневные потребности в колбасных изделиях каждого вида составляют 450, 370 и 400 т., соответственно. В Табл. 39 приведена себестоимость производства каждого вида колбасных изделий на каждом заводе.

Табл. 39 Себестоимость производства колбасных изделий

	Колбаса вареная	Колбаса в/к	Ветчина
Завод 1
Завод 2
Завод 3
Завод 4

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

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

Табл. 40 Данные полицейского участка

	Вызов 1	Вызов 2	Вызов 3
Патруль 1
Патруль 2
Патруль 3
Патруль 4
Патруль 5

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

15. В распоряжении торговой компании имеется 6 торговых точек и 6 продавцов. Из прошлого опыта известно, что эффективность работы продавцов в различных точках неодинакова. Коммерческий директор произвел оценку деятельности каждого продавца в каждой торговой точке, результаты этой оценки представлены в Табл. 41.

Табл. 41 Объемы продаж

Продавец	Торговые точки
A
B
C
D
E
F

Как следует назначить продавцов по торговым точкам, чтобы достичь максимального объема продаж?

16. Три торговые фирмы поставляют апельсины в ящиках четырем оптовым покупателям. Ежедневная потребность этих покупателей составляет 150, 150, 400 и 100 ящиков соответственно. Используя только постоянную рабочую силу, фирмы могут ежедневно поставлять 150, 200 и 250 ящиков соответственно. Первые две фирмы могут увеличить поставки апельсинов путем привлечения дополнительных рабочих, третья фирма таких возможностей не имеет. Транспортные расходы в расчете на один ящик апельсинов приведены в Табл. 42.

Табл. 42 Расходы на перевозку апельсинов (в расчете на 1 ящик)

Торговые фирмы	Покупатели

Необходимо найти оптимальный план поставок.

17. Спрос на некоторый скоропортящийся продукт в следующие четыре месяца составляет 400, 300, 420 и 380 тонн соответственно. Предложение этого товара в те же месяцы составляет 500, 600, 200 и 300 тонн. Отпускная цена на этот товар колеблется от месяца к месяцу и равна соответственно $100, $140, $120 и $150 за тонну. Поскольку товар скоропортящийся, он должен быть реализован в течение трех месяцев, включая текущий. Стоимость хранения тонны товара в течение месяца равна $3. Особенности спроса на товар таковы, что не допускается задержка с выполнением заказа. Необходимо определить оптимальный план производства и поставок товара.

18. A shoe company forecasts the following demands during the next six months: month 1 — 200, month 2 — 260, month 3 — 240, month 4 — 340, month 5 — 190, month 6 — 150. It costs $7 to produce a pair of shoes with regular–time labor (RT) and $11 with overtime labor (OT). During each month, regular production is limited to 200 pairs of shoes, and overtime production is limited to 100 pairs of shoes. It costs $1 per month to hold a pair of shoes in inventory. Formulate a balanced transportation problem to minimize the total cost of meeting the next six months of demand on time.

ТЕМА 7. Постановка и решение задач транспортного типа с помощью стандартного программного обеспечения.

У фирмы Powerco есть 3 электростанции, которые снабжают электроэнергией 4 города, причем каждая из станций может поставлять электроэнергию в любой из городов. Мощности электростанций (в млн. квт/ч), пиковые потребности в электроэнергии для каждого из городов (в млн. квт/ч) приведены в Табл. 43 и

Табл. 44 соответственно. В Табл. 45 приведены данные о стоимости поставки 1 млн. квт/ч от каждой из электростанций для каждого города. Фирме Powerco необходимо составить план поставки электроэнергии для обеспечения потребностей городов (с учетом пиковых потребностей) с наименьшими затратами.

Табл. 43 Мощности электростанций Powerco (млн. квт/ч)

Станция	Мощность
Станция 1
Станция 2
Станция 3

Табл. 44 Пиковые потребности городов в электроэнергии (млн. квт/ч)

Город	Пиковая потребность
Город 1
Город 2
Город 3
Город 4

Табл. 45 Стоимость поставки 1 млн. квт/ч

	Город 1	Город 2	Город 3	Город 4
Станция 1
Станция 2
Станция 3

Задание для самостоятельной работы.

1. Записать математическую модель;

2. Построить транспортную таблицу;

3. Найти начальный допустимый план методами минимального элемента и Фогеля;

4. Проверить полученный план на оптимальность и найти, если необходимо, оптимальный план методом потенциалов.

Дата добавления: 2014-12-29