Министерство образования и науки Российской Федерации

Магнитогорский государственный университет

В.Б. Лапшина, В.Н. Макашова

Сборник задач

ОПТИМИЗАЦИЯ И МАТЕМАТИЧЕСКИЕ МЕТОДЫ ПРИНЯТИЯ РЕШЕНИЙ

Магнитогорск

2007

СОДЕРЖАНИЕ

1. МЕТОДЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 3

1.1. Алгебраический симплексный метод 3

1.2 Графический метод 11

1.3 Метод искусственного базиса 22

2. СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 26

2.1.Транспортная задача 26

2.2. Задача о назначениях 30

3. МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 32

3.1. Метод множителей Лагранжа 32

3.2. Градиентные методы выпуклого программирования 32

4. ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ 34

4.1. Задачи выбора оптимальной стратегии обновления оборудования 34

4.2. Задачи выбора оптимальной стратегии обновления оборудования 36

4.3. Задачи распределения ресурсов 37

4.4. Задачи планирования рабочей силы 40

5. ЗАДАЧИ ТЕОРИИ ИГР 41

6. ЗАДАЧИ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ 47

1. Методы линейного программирования

1.1. Алгебраический симплексный метод

1. Для реализации трех товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве 180, 50, 40 единиц. При этом для продажи первой группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве 3 единиц, ресурса второго вида – в количестве 2 единиц, ресурса третьего вида – в количестве 2 единиц. Для продажи второй и третьей групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве 6 и 4 единиц, ресурсов второго вида – в количестве 1 и 2 единиц, ресурсов третьего вида – в количестве 3 и 1 единиц. Доход от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно 6, 5, 5 тыс. руб. Определите плановый объем и структуру товарооборота так, чтобы доход торгового предприятия был максимальным.

2. Конкуренция приводит к необходимости торговым предприятиям заниматься еще и выпуском продукции собственного производства, например салатов, пиццы и т.п. Нормы затрат на производство разных видов пиццы, объемы ресурсов и стоимость приведены в таблице.

Продукты	Нормы затрат на изготовление 100 шт. пиццы, кг			Запасы продуктов, кг
	ассорти	грибная	салями
Грибы	6	7	2	20
Колбаса	5	2	8	18
Тесто	10	8	6	25
Цена за 100 шт., тыс. руб.	9	6	5

3. Компания производит холодильники марок А470 и А370. Модели приносят прибыль: А470 – 70$ каждый и А370 – 60$ каждый. Компания ставит целью максимизировать прибыль. Имеются ограничения по количеству, в котором могут быть произведены эти два холодильника. Так, для производства А470 требуется 3 человека-часа, а для производства А370 – 2 человека-часа. Общее количество человеко-часов для производства этих двух моделей составляет 3000. Стоимость сырья для модели А470 составляет 50$, а для модели А370 – 60$. Потолок недельной сметы по сырью для этих двух моделей составляет 75000$.

4. Для реализации трех товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве 420, 600, 900 единиц. При этом для продажи первой группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве 3 единиц, ресурса второго вида – в количестве 2 единиц, ресурса третьего вида – в количестве 4 единиц. Для продажи второй и третьей групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве 2 и 1 единиц, ресурсов второго вида – в количестве 1 и 3 единиц, ресурсов третьего вида – в количестве 2 и 1 единиц. Доход от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно 3, 3, 4 тыс. руб. Определите плановый объем и структуру товарооборота так, чтобы доход торгового предприятия был максимальным.

5. Для изготовления двух видов продукции P₁ и P₂ используют четыре вида ресурсов S_1, S_2, S_3, S_4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице.

Вид ресурса	Запас ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
		P1	P2
S1	18	1	3
S2	16	2	1
S3	5	-	1
S4	21	3	-

Прибыль, получаемая от единицы продукции P₁ и P₂ – соответственно 2 и 3 руб. Составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

6. Финансовый консультант консультирует клиента по оптимальному инвестиционному портфелю. Клиент хочет вложить средства в два наименования акций крупных предприятий. Цены на акции следующие: 1 тип акций – 6 руб. за акцию; 2 тип акций – 4 руб. за акцию. Всего в наличии 30000 руб., направляемых на инвестиции в эти акции. Клиент уточнил, что он хочет приобрести максимум 6000 акций обоих наименований, при этом акций одного из наименований должно быть не более 5000 штук. Прибыль от инвестиции в эти две акции в следующем году составит: 1 тип акций – 1,2 руб., 2 тип акций – 1,0 руб. Задача консультанта состоит в том, чтобы выдать клиенту рекомендации по оптимизации прибыли от инвестиции.

7. Для реализации трех товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве 520, 140, 810 единиц. При этом для продажи первой группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве 16 единиц, ресурса второго вида – в количестве 7 единиц, ресурса третьего вида – в количестве 9 единиц. Для продажи второй и третьей групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве 18 и 9 единиц, ресурсов второго вида – в количестве 7 и 2 единиц, ресурсов третьего вида – в количестве 2 и 3 единиц. Доход от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно 8, 6, 4 тыс. руб. Определите плановый объем и структуру товарооборота так, чтобы доход торгового предприятия был максимальным.

8. Компании необходимо принять решение относительно производства номенклатурного ряда из трех моделей холодильников: А470, А370 и В270. Прогнозируемая прибыль от продажи единицы изделия составляет: А470 – 70$, А370 – 60$, В270 – 50$. Количество человеко-часов, необходимое для производства единицы изделия, составляет: А470 – 3 ч, А370 – 2 ч, В270 – 2,5 ч. Стоимость сырья, необходимого для производства единицы изделия, составляет: А470 – 50$, А370 – 60$, В270 – 40$. Компания имеет 3000 человеко-часов и смету в 75000$ для производства этих моделей. Спрос на модель А470 вряд ли превысит 250 штук.

9. В таблице указано время, необходимое для производства двух наименований товаров последовательно в каждом из трех производственных циклов:

Товар	Количество минут на цикл
	Цикл А	Цикл Б	Цикл В
1	20	10	40
2	30	20	30

Компания получает прибыль в 40$ за единицу товара 1 и 50$ за единицу товара 2. На каждый из циклов имеется всего: цикл А – 1600 мин.; цикл Б – 1000 мин.; цикл В – 2400 мин. Определите, в каком количестве необходимо выпускать каждый из товаров, чтобы максимизировать общую прибыль.

10. Для реализации трех товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве 116, 240, 432 единиц. При этом для продажи первой группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве 4 единиц, ресурса второго вида – в количестве 3 единиц, ресурса третьего вида – в количестве 12 единиц. Для продажи второй и третьей групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве 8 и 2 единиц, ресурсов второго вида – в количестве 8 и 4 единиц, ресурсов третьего вида – в количестве 4 и 6 единиц. Доход от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно 8, 6, 6 тыс. руб. Определите плановый объем и структуру товарооборота так, чтобы доход торгового предприятия был максимальным.

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

Вид ресурса	Вид товара				Объем ресурсов
	1	2	3	4
Сырье, кг	3	5	2	4	60
Рабочая сила,	22	14	18	30	400
Оборудование, станко-ч	10	14	8	16	128
Прибыль на ед. товара, руб.	30	25	56	48

Какой ассортимент товара надо выпускать, чтобы прибыль была максимальной?

12. Владелец розничного магазина по продаже электроники должен принять решение по ассортименту запасов компьютеров. Он решил выбрать модели А и Б. Складские помещения рассчитаны максимум на 30 компьютеров. Обе модели занимают одинаковое место. Цена приобретения составляет: модель А – 500 руб., модель Б – 800 руб. У владельца магазина имеется в месяц 20100 руб. свободных средств на приобретение этих компьютеров. Он получает прибыль в размере 200 руб. за каждый компьютер модели А и 300 руб. за каждый компьютер модели Б. Из прошлого опыта известно, что месячный объем продаж модели Б не превысит 20 единиц. Порекомендуйте владельцу магазина, сколько и какой модели ему ежемесячно следует приобретать, чтобы максимизировать ожидаемую прибыль.

13. Для реализации трех товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве 180, 50, 40 единиц. При этом для продажи первой группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве 3 единиц, ресурса второго вида – в количестве 2 единиц, ресурса третьего вида – в количестве 2 единиц. Для продажи второй и третьей групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве 6 и 4 единиц, ресурсов второго вида – в количестве 1 и 2 единиц, ресурсов третьего вида – в количестве 3 и 1 единиц. Доход от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно 6, 5, 5 тыс. руб. Определите плановый объем и структуру товарооборота так, чтобы доход торгового предприятия был максимальным.

14. Мебельная фабрика выпускает столы, стулья, бюро и книжные шкафы. При изготовлении этих товаров используются два различных типа досок, причем фабрика имеет в наличии 1500 м досок I типа и 1000 м досок II типа. Кроме того, заданы трудовые ресурсы в количестве 800 чел-ч. В таблице приведены нормативы затрат каждого из видов ресурсов на изготовление 1 ед. изделия и прибыль на 1 ед. изделия.

Ресурсы	Затраты на единицу изделия
	столы	стулья	бюро	книжные шкафы
Доски I типа, м	5	1	9	12
Доски II типа, м	2	3	4	1
Трудовые ресурсы, чел-ч	3	2	5	10
Прибыль, руб	12	5	15	10

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

15. Рекламное агентство решает вопрос о размещении рекламных материалов в средствах массовой информации. Рекламу можно разместить на местном радио, в местной газете и на щитах. По оценкам, в каждом из случаев реклама может дойти до 3000 человек (радио), 6000 человек (газета) и 2500 человек (щиты). Стоимость размещения одного рекламного материала составляет: местное радио – 800 руб., местная газета – 500 руб., щиты – 400 руб. Всего на рекламу выделено 15000 руб., и не более 15 рекламных материалов может быть размещено в одном из средств. Определите, сколько рекламных материалов и где следует разместить, чтобы максимизировать охват населения рекламой товара.

16. Для реализации трех товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве 36, 50, 80 единиц. При этом для продажи первой группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве 8 единиц, ресурса второго вида – в количестве 4 единиц, ресурса третьего вида – в количестве 2 единиц. Для продажи второй и третьей групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве 10 и 20 единиц, ресурсов второго вида – в количестве 13 и 8 единиц, ресурсов третьего вида – в количестве 0 и 5 единиц. Доход от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно 6, 16, 25 тыс. руб. Определите плановый объем и структуру товарооборота так, чтобы доход торгового предприятия был максимальным.

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

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

Виды ресурсов	Объем ресурсов	Производительность и нормы расхода
		1	2	3
Станки I типа	30	20	10	25
Станки II типа	45	8	20	10
Пряжа	30	120	180	210
Красители	1	10	5	8
Цена		15	15	20

18. Производитель хочет определить оптимальные дневные объемы выпуска трех товаров – А, Б и В, которые максимизируют прибыль. Имеются следующие ограничения:

Товар	Количество персонала, требуемого для выпуска единицы товара	Количество сырья на единицу товара	Машино-часы
А	4	5	1
Б	3	8	1
В	3	6	2
Всего имеется в наличии	700	1200	300

Оценочная валовая прибыль от единицы товара составляет: товар А – 50$, товар Б – 40$, товар В – 30$. Порекомендуйте производителю оптимальные дневные объемы выпуска этих товаров.

19. Для реализации трех товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве 850, 1120, 1060 единиц. При этом для продажи первой группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве 17 единиц, ресурса второго вида – в количестве 8 единиц, ресурса третьего вида – в количестве 4 единиц. Для продажи второй и третьей групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве 5 и 5 единиц, ресурсов второго вида – в количестве 6 и 6 единиц, ресурсов третьего вида – в количестве 2 и 4 единиц. Доход от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно 8, 7, 4 тыс. руб. Определите плановый объем и структуру товарооборота так, чтобы доход торгового предприятия был максимальным.

20. Производитель моющих средств производит три наименования товаров: А, В и С. На единицу товара компания получает следующую прибыль: А – 40 руб., В – 30 руб., С – 25 руб. Потребности для производства одной партии приведены в таблице:

Товар	Химические вещества (мг)	Машинное время (мин)	Человеко-часов (мин)
А	20	8	10
В	16	7	10
С	22	6	8
Всего в наличии в день	1000	400	400

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

21. Для производства двух видов изделий А и В предприятие использует три вида сырья. Другие условия задачи приведены в таблице.

Вид сырья	Нормы расхода сырья на одно изделие, кг		Общее количество сырья, кг
	А	В
I	12	4	300
II	4	4	120
III	3	12	252
Прибыль, ден. ед.	30	40

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

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

	Кофеварка	Кастрюля	Запас ресурса
Листовой металл	1	4	100
Полосовой металл	5	3	160
Заклепки	4	6	180
Цена изделия	8	10

Максимизировать доход производителя.

23. Компания производит два товара – А и Б. Товары требуют большого объема работ, проводимых в два приема. В таблице показано количество часов, затрачиваемое на выпуск единицы товара на каждом из этапов:

Товар	Человеко-часов на единицу
	Этап 1	Этап 2
А	3	4
Б	2	5

В неделю общее количество часов, которое можно затратить на каждом из этапов, составляет: этап 1 – 60 ч, этап 2 – 100 ч. От продажи единицы каждого из товаров компания получает прибыль в размере 50 руб. Сколько единиц каждого наименования должна производить компания, чтобы максимизировать общую прибыль?