Сборник задач по математическому программированию

Государственный Комитет Российской Федерации по Высшему Образованию

Санкт-Петербургский Государственный Инженерно-Экономический Университет

СБОРНИК ЗАДАЧ ПО МАТЕМАТИЧЕСКОМУ ПРОГРАММИРОВАНИЮ

Раздел I. Линейное программирование и его использование в задачах планирования.

Задача I. (№№ I.I-I.I00).I. Решить симплекс-методом задачу:

-max (или min)

,

,

,

2. Составить двойственную задачу.

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

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

5. Выписать изменение оптимального значения задачи, соответствующее таким

6. Рассмотреть вопросы, аналогичные 4 и 5 относительно приращений коэффициентов целевой функции.

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

8. Выяснить, имеет ли исходная задача оптимальные планы, отличные от найденного в п.I.

Параметры задачи приведены в таблице.

№
			-1															-1
	-2						-2		-1		-3			-5		-1			-8
			-3	-1								-1					-3
		-1				-1						-1
		-1				-2		-1	-2			-1				-2
		-1					-3						-1	-5		-4	-20
				-3				-2				-2					-9
			-1			-1		-3	-1
			-4	-1			-1									-1
	-1						-2							-5			-19		-2
		-4				-1										-1
	-2			-3			-2					-4		-1			-25
	-1			-5					-7								-2	-1
			-3	-1								-2
	-1			-5					-7									-1	-8
		-5					-1	-2					-1					-5
	-2		-1																-1
		-1		-2			-5	-1	-5							-4
	-2		-1
	-2			-1								-1		-1			-5		-1
	-2			-7					-2									-1
	-2			-7					-2									-2
		-3		-1												-13		-9	-1
							-7						-1				-22		-7
				-2										-1			-6
												-1	-5		-10
			-1				-7										-13		-2
							-1		-1			-1		-3		-3	-1
			-7					-3				-1					-3
		-1															-1
			-7					-3				-1				-1			-1
				-1							-1								-1
											-1			-1			-2		-10
												-3
									-2			-1					-3		-5
													-1	-3		-6	-9
						-1			-2							-3	-1		-7
			-1				-1		-1
											-1			-1					-12
	-1							-3			-4			-3		-4			-3
			-1				-1		-2			-1
				-3			-2		-1				-2				-2	-1
	-3		-1			-2			-1				-1			-20
			-2				-3					-1		-2			-10
							-2		-8		-3							-8
			-1			-3		-7				-1				-5		-1
	-2			-1				-1
	-7			-1									-3				-6
		-3						-3					-2					-7
		-6		-2				-5				-2		-5				-5
		-3							-2			-1							-1
			-1			-1			-2								-2
				-3			-1							-1				-1
		-2		-1		-7							-2					-5
		-1			10/3	-1			-3			-1			11/3				-6
		-5						-3		½
		-1						-1	-2
			-8				-6						-3				-8
				-5			-3				-2						-12
		-2		-1									-2					-5

Задача 2. (№№ 2.I-I.50).I. Решить параметрическую задачу:

-max

для всех значений параметра t;

2.Нарисовать график оптимального значения целевой функции;

3.Составить двойственную задачу и найти ее решение.

Коэффициенты ограничений и целевой функции приведены в таблице.

№
									-2		-3			-2
							-4			-1
									-5			-1		-2
												-2
		-2					-5		-3		-5			-1
						-1			-3	-2		-1
									-3		-6			-3
							-4
									-2	-1	-6			-3
												-1		-1
									-6			-3	-4
														-1
		-3					-4		-5			-2	-2
											-2
									-2		-3			-3
						-7						-1	-1
												-1
						-7
		-2					-4		-3	-2		-2	-4
													-3
									-1		-1		-3
									-4			-1		-2
									-3					-1
			-1			-1	-2					-2
											-2
												-1
									-4				-3
									-2		-6		-1
						-1				-1		-3
									-2		-6
		-1	-1									-1
							-5						-6
							-1			-1				-1
							-5					-1	-6
												-1
							-5					-1		-1
										-1			-1
							-5		-2			-1	-1
		-2					-1			-1				-3
			-1			-1								-1
			-1		-1		-2		-5				-4
			-3							-2
		-1					-1
		-7									-10		-5
		-3	-5									-1	-9	-5
		-1								-1				-9
	-4					-1	-3				-4	-4	-8	-2
		-2					-1			-1				-3
			-3			-6					-3		-3	-2

№ 2.5I-I.I00. I. Решить для всех значений t параметрическую задачу:

- max

2.Нарисовать график оптимального значения целевой функции.

3.составить двойственную задачу и найти ее решение (используя п.I.).

№
		-1						-1		-4			-4
					-2			-1
				-3				-1
								-1		-1
			-1			-2				-1			-1
			-1		-2								-1
		-2						-1	-2				-2
		-3				-1			-3	-2		-5
										-1
		-1
							-1		-3			-4
										-1
										-2
			-2			-1				-2			-5
	-3							-1			-4
					-3
										-1
										-2
					-4			-1					-3
	-1						-3			-1		-3
		-1
			-1		-2		-2					-4
					-5			-1					-1
					-5
					-1
					-3
										-1
										-5
		-1										-7
								-2	-1				-3
					-3
					-1								-2
										-2
					-1
			-2							-1			-2
				-5
							-1					-3
							-2					-5
					-2
					-1				-5
									-5
								-1		-1			-5
				-2

Задача 3. (№№ 3.I-3.I00). По условиям задачи составить ее математическую модель, найти оптимальный план с помощью симплекс-метода.

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

3.I. Для сборки двух видов приборов применяются три вида микросхем А,В,С. На один прибор затрачивается одна микросхема А, две микросхемы В и одна микросхема С. Для прибора затраты соответственно равны 3,1,2 микросхем А,В,С. Микросхем А-60-шт., В-35шт., С-40шт. Сколько приборов каждого типа следует собрать для получения максимального дохода если цена одного прибора -17 руб., а -19 руб. Есть ли смысл включить в производство прибор ценой в 45 руб., требующий 5 микросхем А, 3 микросхемы В и 4 микросхемы С?

3.2.В условиях предыдущей задачи приборы объединяются в комплекты, содержащие их в количествах 4, 3,. Продажная цена комплекта 300 руб. Какой максимальный доход можно получить?

3.3.Строительная организация планирует сооружение домов типа с однокомнатными, двухкомнатными и трех комнатными квартирами. Один дом состоит из 10 одно-, 50 двух- и 35 трехкомнатных квартир. Для домов эти данные равны соответственно 20,60,10 и 15,30,5. Годовой ввода жилой площади составляет не менее 700 однокомнатных, 2000 двухкомнатных и 600 трех комнатных квартир. Требуется составить программу строительства так, чтобы выполнить годовой план с наименьшими затратами, если известно, что затраты на возведение одного дома , составляют соответственно 700, 400 и 300 тыс.руб.

3.4.Данные о домах те же, что и в задаче 3.3. Суммарные затраты на строительство не должны превзойти 25 млн.руб. Определить план строительства, обеспечивающий получение максимального числа комнат, при условии, что суммарное число одно- и трехкомнатных квартир не менее 55% от числа двухкомнатных.

3.5.Для выращивания овощей по способу гидропоники необходима питательная смесь, содержащая не менее 1% фосфора, 3% азота, 2% калия и 0,01% смеси микроэлементов. Для составления питательной смеси используют 4 вида удобрений. Содержание указанных питательных веществ в 1 кг удобрения первого вида составляет 4%, 0%,0%,0% соответственно, второго- 2%,1%,4%,0%, третьего- 1%,5%,0%, 0,005%, четвертого- 1%,2%,3%, 0,02%. Стоимость 1 кг удобрения каждого вида составляет 5,7,8 и 10 рублей соответственно. Сколько килограммов удобрений каждого вида надо взять, чтобы приготовить питательную смесь нужного состава при ее минимальной стоимости?

3.6.В мастерской при изготовлении столов, шкафов и тумбочек применяются 2 вида древесины. На один стол расходуется 0,15 древесины первого вида и 0,2 - второго, на один шкаф 0,2 и 0,1 соответственно, а на одну тумбочку 0,05 древесины первого вида. В наличии имеется 60 древесины первого вида и 40 второго. Количество выпущенных шкафов должно быть не менее 200. Выпуск столов и тумбочек не запланирован. Прибыль мастерской от производства одного стола составляет 12 руб., шкафа-15 руб., тумбочки- 3 руб. Сколько столов, шкафов и тумбочек должна изготовить мастерская, чтобы получит наибольшую прибыль? Имеет ли смысл начать выпуск стульев, если затраты составляют 0,03 древесины первого типа и 0,01 второго, а прибыль равна 4 руб.(на один стул)?

3.7.Данные о затратах материалов, их запасах и получаемой прибыли те же, что в задаче 3.6. Изучение спроса показало, что спрос на столы превосходит спрос на тумбочки, а последний превосходит спрос на шкафы. Можно ли при соблюдении этих условий получит прибыль большую 4650 руб.?

3.8.Хлебозавод выпускает кексы, бисквиты, сдобные булочки и сухари. Расход муки двух видов и различных добавок в центнерах, на центнер каждого вида изделий приведен в таблице.

Вид сырья   Вид изделия	Мука высш. сорт.	Мука 1 сорт	Сахар	Изюм	Др. компоненты
Кексы Бисквиты Сдобные булочки Сухари	0.2 0.4 0.1 -	0.3 - 0.4 0.6	0.1 0.2 0.1 0.2	0.001 - 0.001 -	0.1 0.2 - 0.1

Лимит сырья в центнерах, данный заводу на месяц, составляет соответственно 500ц, 900ц, 700ц, 10ц и 250ц. Сколько центнеров изделий каждого вида должен выпускать хлебозавод для получения максимальной прибыли, если при реализации 1ц кексов завод получает 50руб. прибыли, 1ц бисквитов- 55 руб., 1ц сдобных булочек- 20 руб., 1ц сухарей- 30 руб.

3.9.Сохраняются все условия предыдущей задачи. Изучение спроса показало, что спрос на сдобные булочки больше спроса на кексы,

3.17.Сохраняются все условия предыдущей задачи. Продукты А,В,С объединяются в комплекты, содержащие их в пропорции 5:3:4. Составит план максимизирующий число производимых комплектов.

3.18.Столовая предприятия имеет 14 кг муки, 75 шт. яиц, 11 кг маргарина, 6 кг сахарного песка и 10 кг сметаны. Расход этих продуктов на одно кондитерское изделие каждого вида указан в таблице (в килограммах на 1 шт.).

Вид изделия	Мука	Яйца	Маргарин	Сах. песок	Сметана
Бисквит Песочный торт Кекс	0,2 0,5   1/3	25/3	0,5   1/3	0,2 0,15   1/3	0,5   1/3

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

3.19. Сохраняются все условия предыдущей задачи. Цены на продукты таковы (уровень 1990 г.): мука 0,5 руб., яйца- 1 руб. за десяток, маргарин- 2 руб., сах. песок- 1 руб., сметана- 2 руб. Составить план, максимизирующий прибыль столовой при следующих отпускных ценах (за единицу продукции): бисквит- 1руб.30коп., песочный торт- 3руб.60коп., кекс-2руб.50 коп. Есть ли смысл включить в производство торт «Новый», расход продуктов на который описывается строкой, а отпускная цена которого 4 руб.

Новый

0,6

0,4

0,25

0,7

3.20.С помощью трех технологических способов выпускаются три вида продукции. При использовании первого технологического способа в течение всего рассматриваемого периода выпускается одновременно 9 ед. первого вида, 16- второго и 17- третьего, при использовании 2-го технологического способа -12,21 и 18, 3-го технологического способо-21,18 и 25, затраты труда при этом для каждого из них составляют17,20 и 24 человеко-дней. Плановый выпуск продукции каждого вида 15,15 и 8 ед.соответственно. Найти продолжительности использования технологических способов так, что бы выполнить или перевыполнить план при наименьших затратах труда.

3.21.Сохраняются все условия предыдущей задачи, кроме плана выпуска продукции. Изделия объединяются в комплекты, содержащие их соответственно в количествах 3,5,6. Составит план использования технологических способов, обеспечивающий получение максимального числа комплектов за один период работы, при условии, что суммарные затраты труда не более 22 человеко-дней.

3.22.Для изготовления тортов к выпускному вечеру студентов отпущено для закупки продуктов 26 руб.44коп. Предполагается изготовить бисквитные (Б) и песочные (П) торты и кексы(К). Количество бисквитных тортов не должно превосходить суммарного количества других кондитерских изделий, а песочных тортов должно быть не меньше кексов. Какие продукты и в каких количествах необходимо закупить, что бы обеспечить изготовление максимального количества кондитерских изделий, если стоимость 1 кг муки 46 коп., десятка яиц- 90 коп., 1 кг маргарина- 1 руб.80 коп., сахарного песка- 90 коп., сметаны- 1 руб.70 коп., а расход продуктов на одно изделие каждого вида в килограммах или штуках задан в таблице.

Изделие	Мука	Яйца	Маргарин	Сах. песок	Сметана
Б П К	0,2 0,5 1/3	25/3	0,5 1/3	0,2 0,15 1/3	0,15

Расчет вести с точностью до копеек.

3.23.Для изготовления пластмассовых втулок, шестеренок и шайб требуется стеклоткань, эпоксидная смола и отвердитель. Их запасы равны соответственно 480 ед., 444 ед. и 570 ед. На изготовление одной втулки затрачиваются 4 ед. стеклоткани, 3 ед.- эпоксидной смолы и 2 ед. отвердителя. Для шестеренок и шайб эти затраты соответственно выражаются числами 3,4,6 и 1,1,2. Все изделия проходят через прессовое устройство, которое может быть использовано в течение двух часов. За одну минуту можно обработать две втулки, или одну шестеренку, или четыре шайбы. Прибыль от каждого из этих изделий составляет соответственно 2 руб., 4 руб., 0,5 руб. составить план выпуска продукции, максимизирующий прибыль.

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