Основные положения симплекс-метода

Пусть дана целевая функция вида

и ограничения вида

Вводим набор дополнительных переменных, называемых слабыми, так, чтобы дополнить неравенства до равенств:

.

При этом , а все остальные коэффициенты .

Таким образом, мы получаем матрицу системы следующего вида:

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

В системе MathCad реализован очень удобный способ поиска максимума (минимума) целевой функции при установленных ограничениях. Для этого применяются команды Minimize и Maximize.

Функции Maximize и Minimize могут успешно применяться при реше­нии задач линейного программирования, которые широко использу­ются в экономических и производственных расчетах. Рассмотрим та­кую задачу.

Вычисление максимума данной функции имеет следующий вид - произвольные начальные значения Given Блок решения Given Ограничивающие условия Полученные решения - Рис.7

Пример. Пусть цех должен изготовить 100 штук изделий трех типов, причем не менее 20 штук каждого типа. На изделия уходят соответственно 4,3,4 и 2 кг металла при его общем запасе в 340 кг. Кроме того, на изделия ухо­дят соответственно 4,75, 11 и 2 кг пластмассы при ее общем запасе в 700 кг. Сколько изделий каждого типа (x _l, x ₂, x ₃) надо выпустить для получения максимума в рублях, если цена изделий каждого типа со­ставляет соответственно 4, 3 и 2 рубля?

Фрагмент документа Mathcad, реализующий решение данной задачи, представлен на рис. 7. Очевидно, что введение в Mathcad функций опти­мизации Maximize и Minimize расширяет круг решаемых системой задач при минимальных затратах времени на подготовку средств их решения.

 

Теоретические вопросы, выносимые на обсуждение

1. Как в общем виде формулируется задача линейного программирования.

2. Какая функция называется целевой.

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

4. Сформулируйте основные постулаты графического метода.

5. Что такое опорное решение.

6. Запишите вид линий уровня целевой функции задачи линейного программирования.

7. В чем заключается графический способ решения задачи линейного программирования.

8. В чем заключается экономическая интерпретация задач линейного программирования.

9. Всегда ли существует максимум (минимум) целевой функции в некоторой области.

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

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

12. Сформулируйте основные положения симплекс-метода.

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

14. Какие команды применяются в системе MathCad для реализации поиска максимума (минимума) целевой функции при установленных ограничениях.

 

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

 

I. Найти минимум и максимум целевой функции f (x ₁, x ₂) геометрическим методом при заданной системе ограничений:

1. 2. 3.

4. 5. 6.

7. 8. 9.

10. 11. 12.

13. 14. 15.

16.

II. Составить математическую модель и используя функций опти­мизации Maximize и Minimize найти оптимальное решение.

1. Фабрика Wild West производит два типа ковбойских шляп. Производство шляпы первого типа требует в два раза больше временных ресурсов, чем производство шляпы второго типа. Если фабрика будет производить только шляпы второго ти­па, то в день она сможет изготовить 400 таких шляп. Рынок накладывает ограни­чения на производство шляп: не более 150 шляп первого типа и 200 шляп второго типа. Доход от производства шляп составляет $8 на единицу первого типа и $5 — второго типа.

a) Примените графический метод для определения ежедневного оптимального производства шляп обоих типов.

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

c) Используя метод стоимости единицы ресурса, определите, на сколько изменится максимальный доход фабрики, если ежедневное производство шляп первого типа не будет превышать 120 единиц.

d) Чему равна стоимость возрастания предельного спроса на одну шляпу второго типа?

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

a) Найдите оптимальную структуру производства этой компании.

b) Определите стоимость единицы сырья и интервал изменения потребляемого сырья, при котором справедлива данная стоимость.

c) С помощью графического анализа чувствительности определите, как изменит­ся значение целевой функции при изменении максимального уровня производ­ства продукта А на ±10 единиц.

3. Компания на производство двух продуктов в день затрачивает 10 часов. Произ­водство каждого продукта состоит из последовательного выполнения трех про­цессов. Данные по этим продуктам и процессам приведены в следующей таблице.

	Процесс 1	Процесс 2	Процесс 3
(количество минут выполнения процесса на единицу продукта)
				$2
				$3

a) Найдите структуру оптимального производства.

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

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

а) Разработайте оптимальный бюджет для рекламы на радио и телевидении.

b) Определите стоимость единицы месячного лимита на рекламу по радио.

c) Примените метод нахождения стоимости единицы ресурса для определения порожной эффективности рекламной кампании при увеличении ежемесячного бюджета на рекламу до $15 000.

5. Корпорация Wyoming Electric является собственником электрогенерирующей станции. Поскольку эта корпорация имеет богатые запасы угля, на электростанции для генерации электрического тока используется уголь. Агентство по защите окружающей среды установило следующие ограничения: концентрация выбрасываемого в воздух сернистого газа не должна превышать 0.002, количество выбрасываемых аэрозольных частиц не должно превышать 20 кг в час. Корпорация для генерации электрического тока использует пылевидный уголь двух сортов, С₁ и С₂. Перед сжиганием эти сорта угля обычно смешиваются. Для простоты предположим, что сернистая составляющая в смеси углей определяется как средне взвешенное от доли угля каждого сорта в смеси. Характеристики используемых сортов угля приведены в следующей таблице.

Сорт угля	Концентрация серы	Количество выделяемых аэрозольных частиц (кг/час)	Генерируемая мощность (кг/час)
С1	0.0018	2.1
С2	0.0021	0.9

a) Найдите оптимальную смесь углей обоих сортов.

b) На сколько изменится количество генерируемой энергии (в час), если ослабить на 1 кг в час ограничение на количество выбрасываемых аэрозольных частиц?

6. Факультет послевузовского обучения местного колледжа города Озарк предлагает в общей сложности до 30 курсов каждый семестр. Все курсы условно можно раз­бить на два типа: практические, такие как деревообработка, обучение работе накомпьютере, ремонт и поддержка автомобилей и т.п.; и гуманитарные, например история, музыка и изобразительное искусство. Чтобы удовлетворить запросы обу­чающихся, в каждом семестре должно предлагаться не менее 10 курсов каждого типа. Факультет оценивает доход от одного практического курса в $1500, а гума­нитарного — в $1000.

a) Какова оптимальная структура курсов для факультета?

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

с) Определите доход факультета при увеличении минимального количества гуманитарных курсов на единицу.

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

	Раскрой	Пошив	Пакетирование
(минуты па изделие)
Рубашка				2.50
Блузка				3.20

a) Определите оптимальную структуру еженедельного производства для швейной фабрики.

b) Если магазину Walmark потребуется не менее 2000 рубашек и 3000 блуз в неделю, то сможет ли швейная фабрика выполнить этот заказ при 5-дневной рабочей неделе? Если нет, то какой выход из этой ситуации вы можете предложить и какое оптимальное решение возможно в этом случае?

c) Определите стоимость одного часа рабочего времени, затрачиваемого отдельно на раскрой, пошив и пакетирование.

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

8. Завод бытовой химии производит два вида чистящих средств, А и В, используя при этом сырье I и II. Обработка одной единицы сырья I стоит $8, в результате производится 0.5 единицы средства А и столько же средства В. Обработка одной единицы сырья II стоит $5, в результате получается 0.6 единицы средства А и 0.4 единицы средства В. Ежедневное производство средства А должно быть не менее 10 и не более 15 единиц. Для производства средства В аналогичные ограничения составляют 12 и 20 единиц.

a) Найдите оптимальную структуру выпуска чистящих средств.

b) Определите стоимость единицы изменения граничных значений ежедневного выпуска средств А и В.

9. Конвейер состоит из трех последовательных линий для сборки двух видов радио приемников: HiFi-1 и HiFi-2. Время, необходимое для сборки одного радиоприемника на каждой линии, приведено в следующей таблице.

	Количество минут, затрачиваемых на сборку одного изделия
HiFi-1	HiFi-2

Ежедневные профилактические работы на соответствующих линиях составляют 10%, 14% и 12% от всего рабочего времени, которое для любой линии не превышает 480 минут всмену.

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

b) Определите стоимость одного процента уменьшения времени профилактических работ для каждой линии.

10. Компания производит детское питание с добавлением сахара и без добавления сахара из сырья двух типов: К₁ и К₂. Следующая таблица представляет основные данные для задачи.

	Расходы сырья на тонну
продукт с добавлением сахара	продукт без добавления сахара
К1	6.2	3.8
К2	1.5	2.3
Доход (в $) на тонну продукта

Компания хочет определить оптимальное (наилучшее) соотношение между видами выпускаемой продукции для максимизации общего ежедневного дохода при этом:

a) Ежедневный объем производства детского питания без добавления сахара должен не ме­нее чем на одну тонну превышать ежедневный объем производства детского питания с добавлением сахара.

b) Ежедневное потребление сырья К₂ должно быть не менее 3 т. и не более 6 т.

c) Ежедневный объем производства детского питания без добавления сахара не может быть меньше ежедневного объема производства детского питания с добавлением сахара.

d) Минимальный ежедневный общий объем производства обоих типов со­ставляет 3 т.

e) Отношение ежедневного объема производства питания без добавления сахара к общему объему производства питания обоих типов не должно превышать 1/2.

11. Завод производит заготовки для машин двух видов Ferrari -60 и Ferrari -67 из стали двух марок N₁ и N₂. Следующая таблица представляет основные данные для задачи.

	Расходы стали на 100 шт.
Ferrari -60	Ferrari -67
N1	7.2	3.4
N2	2.5	4.3
Доход (в $) за 100 шт.

Постройте пространство допустимых реше­ний и найдите оптимальное решение, учитывая (независимо) следующие условия.

a) Ежедневный объем производства деталей для Ferrari -60 не должен пре­вышать 2500.

b) Ежедневный объем производства деталей для Ferrari -67 должен быть не менее 2000.

c) Ежедневный объем производства деталей для Ferrari -67 должен превы­шать ежедневный объем производства деталей для Ferrari -60 в точности на 1000 шт.

d) Ежедневный расход сырья N_l должен быть не менее 24 т.

12. Джек — студент-первокурсник. Он пришел к выводу, что одна только учеба, без ежедневной игры в баскетбол, плохо влияет на его умственное, нравственное и физическое развитие. Поэтому он решил распределить свое дневное время (при­мерно 10 часов) для учебы и игры в баскетбол. Привлекательность игрового вре­мени он оценивает в два раза выше, чем привлекательность времени, затраченного на учебу. Но, имея совесть и чувство долга, Джек решил, что время для игры не должно превышать время учебы. Кроме того, он заметил, что если выполнять все учебные задания, на игру останется не более 4 часов в день. Помогите Джеку рас­пределить его личное время так, чтобы он получал максимальное удовольствие и от работы и от игры.

13. Джон, помимо занятий в школе, для поддержания надлежащего финансового уровня должен подрабатывать не менее 20 часов в неделю. Для этого у него есть прекрасная возможность работать в двух розничных магазинчиках. В первом он может работать от 5 до 12 часов в неделю, а во втором — от 6 до 10 часов. Оба магазина предлагают одинаковую почасовую оплату. Джон должен определиться, в каком магазине и сколько ему работать, исходя из фактора "напряженности" ра­боты. Основываясь на сведениях, полученных при общении с работниками этих магазинов, он оценил этот фактор по 10-балльной шкале: для первого и второго магазинов соответственно 8 и 6 баллов. Понятно, что суммарная "напряженность" работы за неделю пропорциональна количеству отработанных часов. Сколько ча­сов Джон должен работать в каждом магазине, чтобы минимизировать общую суммарную "напряженность" работы?

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

a) Сколько банок каждого напитка должен иметь магазин в начале рабочего дня для максимизации дохода?

b) Определите соотношение доходов от напитков А₁ и В&К, при котором сохра­няется оптимальное решение, найденное на предыдущем шаге.

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

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

b) Определите для найденного решения интервал оптимальности для отношения доходов на единицу продукции.

c) Изменится ли найденное выше оптимальное решение, если доходность столов и стульев уменьшится на 10%?

d) Изменится ли найденное выше оптимальное решение, если доходность столов и стульев составит соответственно $120 и $25 на единицу продукции?

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

а) Найдите оптимальное размещение средств по двум описанным видам кредито­вания и определите коэффициент возврата по всем кредитам.

b) Определите интервал оптимальности для отношения процентных ставок по двум видам кредитов для найденного на предыдущем шаге оптимального решения.

c) Предположим, что невозврат кредитов составит 4% и 3% для кредитов частных лиц и кредитов на покупку автомобилей соответственно. Изменится ли при этом оптимальное решение, полученное выше?

 

Практическое занятие № 8