Симплекс-метод

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

Задание:

1. Построить математическую модель проблемы принятия решения;

2. Решить задачу графическим способом;

3. Исследовать решение на чувствительность.

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

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

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

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

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

1. Небольшая компания “Иванов и сотоварищи” производит двери, которые продаются в строительных магазинах. Компания производит двери двух типов — “Гранд” и “Челси”. Дверь “Гранд” стоит $30, а “Челси” — $40. Рыночная ситуация складывается таким образом, что спрос на продукцию компании практически неограничен. На производстве дверей в компании занято 8 рабочих, которые, по соглашению с профсоюзом, могут работать не более 40 часов в неделю с почасовой оплатой $6. Для производства дверей требуется дерево и стекло. В течение недели компания может закупить 600 кв.м. дерева по цене $4 за кв.м. и 300 кв.м. стекла по цене $16 за кв.м. Для производства одной двери типа “Гранд” требуется 2 кв.м. дерева и 0,5 кв.м. стекла. А для производства одной двери типа “Челси” необходимо 1,5 кв.м. дерева и 1 кв.м. стекла. На производство (обработка и сборка) одной двери, независимо от типа, рабочий затрачивает 1 час. Руководство хотело бы знать: как можно оптимизировать работу компании.

2. Фирма Giapetto’s Woodcarving Inc. производит два вида деревянных моделей-игрушек: солдатиков и локомотивы. Каждый деревянный солдатик продается по $27 и для своего производства требует расходных материалов на $10. Производство одного солдатика увеличивает расходы фирмы (налоги, накладные расходы, зарплата) на $14.

Деревянный локомотив продается по $21 и для своего производства требует расходных материалов на $9. Производство одного локомотива увеличивает расходы фирмы (налоги, накладные расходы, зарплата) на $10.

При производстве этих игрушек выполняются две технологические операции: сборка и покраска. Для производства одного солдатика необходимо 2 часа на покраску и 1 час на сборку. Для производства одного локомотива — 1 час на покраску и 1 час на сборку.

В настоящий момент фирма не испытывает недостатка в расходных материалах, но на сборку в течение недели может быть выделено только 80 часов, а на покраску — 100 часов, что вызвано производственными ограничениями. Отдел маркетинга утверждает, что локомотивы раскупаются в неограниченном количестве, а солдатиков продается не более 40 штук в неделю.

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

3. Компания Case Chemicals Co. производит 2 типа промышленных растворов С1 и С2. Завод по производству растворов работает по 40 часов в неделю, на нем на 7 производственных комплексах заняты 5 рабочих на полной ставке и 2 на временной, работающих по 15 часов в неделю. В соответствии с соглашением с профсоюзом на подобном вредном производстве может быть использовано 230 рабочих часов в неделю.

После производства продукция поступает на участок очистки, на котором занято на 7 комплексах 6 рабочих на полной ставке и 1 рабочий на временной, работающий по 10 часов в неделю. Всего, в соответствии с соглашением с профсоюзами, на участке очистки может быть использовано 250 рабочих часов в неделю.

Расход времени (в часах) на производство и очистку приведен в Табл. 6

Табл. 6 Данные компании Case Chemicals Co

	С1	С2
Производство
Очистка

Расходных материалов достаточно для производства любого количества растворов, спрос на раствор С1 практически неограничен, а спрос на С2 — 120 000 л. в неделю. Цена продажи раствора С1 — $3 на 1000 л., а С2 — $5. Так как все рабочие получают фиксированную зарплату независимо от количества отработанных часов, то эти расходы фиксированы и не включены в доход фирмы.

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

4. Небольшая фирма Sunglass производит по заказу партиями стеклянную посуду — наборы фужеров для сока и коктейлей. Для производства этой посуды фирма закупила специальное оборудование, производственная линия которого которое может быть настроено на производство либо фужеров для сока, либо для коктейлей. Переключение оборудования с одного на другой тип продукции происходит достаточно быстро, так что этим временем можно пренебречь при планировании. При производстве фужеров для сока — за 6 часов может быть изготовлено 100 наборов. Если производить фужеры для коктейлей — производительность составляет 100 наборов за 5 часов. В течение недели, в соответствии с трудовым соглашением, оборудование может быть занято не более чем на 60 часов. Произведенная продукция хранится на складе фирмы емкостью 1 500 кубических метров. Упаковка с набором фужеров для сока занимает 1 м³, а упаковка с набором для коктейлей — 2 м³.

Наборы для сока продаются по цене $5, наборы для коктейлей стоят $4,5. Однако спрос на наборы для сока не превышает 800 штук в неделю, в то время как все произведенные наборы для коктейлей продаются в течение недели.

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

5. Магазин продает два вида безалкогольных напитков: Кока–Колу и квас. Доход от одной банки колы составляет 5 центов, а от кваса — 7 центов. В среднем магазин продает не более 500 банок обоих напитков ежедневно. Несмотря на то, что Кока-Кола известная торговая марка, покупатели предпочитают квас, поскольку они значительно дешевле и вкуснее. Отделом продаж определено, что объемы продаж колы и кваса в натуральном исчислении должны соотноситься не менее чем 1:2. Кроме того, известно, что магазин продает не менее 100 банок колы в день.

Как наилучшим образом спланировать руководству магазина запасы напитков в начале дня?

6. Мебельная фабрика для сборки столов и стульев привлекает к работе на 10 дней четырех столяров. Каждый столяр затрачивает 2 часа на сборку стола и 30 минут — на сборку стула. Покупатели обычно приобретают вместе со столом от четырех до шести стульев. Доход от одного стола составляет $135 и $50 — от одного стула. На фабрике установлен 8-часовой рабочий день.

Руководство фабрики хотело бы оптимизировать свое производство.

7. Банк в течение нескольких месяцев планирует вложить до $200 000 в кредитование частных лиц и покупок автомобилей. Банковские комиссионные составляют 14% при кредитовании частных лиц и 12% при кредитовании покупок автомобилей. Оба типа кредитов возвращаются в конце годичного периода кредитования. Известно, что 3% клиентских и 2% автомобильных кредитов никогда не возвращаются. Объемы кредитов на покупку автомобилей обычно более чем в 2 раза превышают объемы кредитов для частных лиц.

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

8. Завод производит 2 типа микросхем, каждый на отдельно линии. Производительность этих линий составляет 600 и 750 микросхем в день. Для производства микросхем первого типа необходимо 10 единиц некоторого комплектующего, а второго типа — 8 единиц этого же комплектующего. Поставщик может обеспечить на день 8 000 единиц этого комплектующего. Доход от микросхем первого типа составляет $60, а второго — $40.

Каким образом можно оптимально спланировать производство?

9. Мебельная фабрика собирает из готовых комплектующих 2 вида кухонных шкафов: обычные и люкс. Обычный шкаф покрывается белой краской, а люкс — лаком. Покраска и покрытие лаком производятся на одном производственном покрасочном участке. Сборочная линия фабрики ежедневно может собирать не более 200 обычных шкафов и 150 шкафов типа люкс. Лакирование шкафа типа люкс требует вдвое больше времени, чем покраска одного простого шкафа. Если покрасочный участок занят только лакированием, то за день здесь можно подготовить 180 шкафов типа люкс. Фабрика оценивает доход от обычных шкафов и шкафов люкс в $100 и $140 соответственно.

Составьте оптимальное ежедневное расписание работы покрасочного участка.

10. Фирма Wild West выпускает ковбойские шляпы двух типов (А и В). Производство шляпы первого типа требует в 2 раза больше временных ресурсов, чем производство шляпы второго типа. Если бы фирма выпускала только шляпы типа В, суточный объем производства мог бы составить 400 таких шляп. Рынок накладывает ограничения: суточный объем сбыта шляп типа А не более 150, а шляп типа В — 200 штук. Доход от производства шляп типа А составляет $8, а шляп типа В — $5. Определить, как наилучшим образом спланировать производство шляп.

11. Компания производит два вида продукции: А и В. Объем продаж продукта А составляет не менее 80% от общего объема продаж продуктов А и В. Вместе с тем компания не может производить более 100 единиц продукта А в день. Для производства этих продуктов используется одно и то же сырье, поступление которого ограничено 240 кг. в день. На изготовление единицы продукта А расходуется 2 кг. сырья, а продукта В — 4 кг. Цена одной единицы продукции А и В составляет $20 и $50 соответственно.

Как руководству составить оптимальную структуру производства компании?

12. Компания имеет возможность рекламировать свою продукцию по местному радио и телевидению. Бюджет на рекламу ограничен $10 000 в месяц. Одна минут рекламного времени на радио стоит $15, а на телевидении — $300. Компания предполагает, что реклама на радио по времени должна превышать рекламу на телевидении не менее чем в 2 раза. Вместе с тем известно, что нерационально использовать более 400 минут рекламы на радио в месяц. Последние исследования показали, что реклама на телевидении в 25 раз эффективнее рекламы на радио.

Как оптимальным образом спланировать рекламу?

13. Компания Woodco производит столы и стулья, которые делаются из дуба и из сосны. Компания имеет в своем распоряжении 150 кв. м. дуба и 210 кв. м. сосны. Для производства одного стола требуется 17 кв.м. дуба и 30 кв.м. сосны. Для производства одного стула необходимо 5 кв.м. дуба и 13 кв.м. сосны. Стоимость одного стола $40, одного стула — $15. Требуется определить: каким образом компания Woodco может максимизировать свою прибыль.

14. Компания Bloomington Brewery производит пиво и эль. Пиво продается по цене $5 за декалитр, а эль — $2. Для производства одного декалитра пива необходимо 5 кг. зерна и 2 кг. хмеля, а для производства эля — 2 кг. зерна и 1 кг хмеля. В распоряжении компании имеется 60 кг. зерна и 25 кг. хмеля. Необходимо определить каким образом компания может увеличить свою прибыль.

15. Компания Burroughs производит мужские рубашки и женские блузки. Торговая сеть принимает всю продукцию, произведенную фирмой. Производство швейного изделия состоит из раскроя, пошива и упаковки готового изделия. На участке раскроя работают 25 человек, непосредственно на пошиве изделий — 35 человек и 5 человек занято на упаковке. Компания работает в одну смену (8 часов) пять дней в неделю. Трудозатраты (в минутах на изделие) на выпускаемые изделия и доход от них приведены в Табл. 1.

Табл. 7 Данные компании Burroughs

Изделие	Операция
Раскрой	Пошив	Упаковка	Доход ($ на изделие)
Рубашка				2,50
Блузка				3,20

Компании необходимо наилучшим образом спланировать свое производство.

16. Завод бытовой химии производит 2 вида чистящих средств, А и В, используя при этом сырье1 и 2. Обработка одной единицы сырья 1 стоит $8, в результате производится 0,5 единицы средства А и столько же средства В. Обработка одной единицы сырья 2 стоит $5, в результате получается 0,6 единиц средства А и 0,4 единицы средства В. Ежедневное производство средства А должно быть не менее 10 и не более 15 единиц. Аналогичные ограничения для средства В составляют 12 и 20 единиц.

Как наилучшим образом спланировать выпуск чистящих средств?

17. Мебельная фирма Red Joiner производит и продает столы и шкафы и древесины хвойных и лиственных пород. Расход каждого вида древесины в кубометрах на каждое изделие приведен в Табл. 8.

Табл. 9 Данные фирмы Red Joiner

	Хвойные	Лиственные	Цена изделия (тыс. руб.)
Стол	0,15	0,2	0,8
Шкаф	0,3	0,1	1,5
Запас древесины

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

18. Farmer Jones bakes two types of cake (chocolate and vanilla) to supplement his income. Each cake can be sold for $1, and each vanilla cake can be sold for 50¢. Each chocolate cake requires 20 minutes of baking time and uses 4 eggs. Each vanilla cake requires 40 minutes of baking and uses 1 egg. Eight hours of baking time and 30 eggs are available. How farmer Jones can maximize the revenue? (A fractional number of cakes is okay.)

Ключевой идеей симплекс-метода является то, что оптимальное решение задачи ЛП всегда связано с угловой точкой пространства допустимых решений. Для перехода от геометрического к алгебраическому методу решения необходимо алгебраически описать крайние точки пространства решений, для чего задачу следует представить в некоторой стандартной форме.

Каноническая форма задачи ЛП

или .

Правила преобразования задачи ЛП в каноническую форму

.

Множество допустимых решений задачи имеет вид

,

называется многогранным и является выпуклым и замкнутым

Задача ЛП, записанная в канонической форме содержит линейных уравнений с переменными ().Если , то существует единственное решение, в котором переменных соответствуют базису матрицы , а остальные равны 0, причем это решение соответствует угловой (крайней) точке множества допустимых решений. При этом соответствующие переменных называют базисными, а остальные нулевых переменных — небазисными. Все вместе эти переменные составляют базисное решение. Если все переменные базисного решения неотрицательны, то такое базисное решение называют допустимым базисным решением.

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

§ Если у системы линейных уравнений (СЛУ) существует решение, то существует и базисное решение этой СЛУ;

§ Если задача ЛП имеет допустимое решение, то она имеет и допустимое базисное решение;

§ Если задача ЛП имеет оптимальное решение, то она имеет и оптимальное базисное решение.

В силу справедливости последнего утверждения, вычислительный алгоритм линейного программирования (симплекс-метод) основан на нахождении именно оптимального базисного решения и оперирует только с допустимыми базисными решениями.

Алгоритм симплекс-метода находит оптимальное решение, перебирая допустимые базисные решения, причем не все подряд, а пытается на каждом шаге найти допустимое базисное решение «улучшающее» значение целевой функции.

Запишем задачу Reddy Mikks в канонической форме

Здесь — дополнительные переменные, добавленные в неравенства для преобразования их в равенства. Заметим, что задача записана в т.н. предпочтительной форме: каждая из переменных входит с коэффициентом 1 только в одно уравнение. В этом случае легко найти начальное допустимое базисное решение (опорный план). Приведенный ниже способ составления и решения симплекс-таблиц справедлив именно для задач линейного программирования, записанных в предпочтительной форме. В других случаях нахождение опорного плана может представлять трудность и требуется введение искусственного базиса (или использование метода штрафов).

Симплексная таблица

Базис	z	x1	x2	S1	S2	S3	S4	Решение
z		-5	-4
s1
S2
S3		-1
S4

Дополнительные переменные образуют начальное допустимое базисное решение, при этом небазисные переменные равны нулю.

Алгоритм симплекс-метода. Симплекс-метод состоит в последовательном выполнении шагов-итераций.

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