Лабораторная работа №2 «Симплекс-метод».

Цель: изучение и практическое применение симплекс-метода решения задач линейной оптимизации.

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

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

Для решения задачи линейного программирования симплекс-методом студент должен:

• изучить теоретический материал;

• составить математическую модель задачи;

• найти решение (оптимальный план) задачи, используя симплекс-метод;

• проанализировать полученное решение, проверив его правильность на ЭВМ;

• оформить решение задачи в виде отчета по лабораторным работам.

Постановка и методика решения подобных задач рассмотрена в образце оформления отчета лабораторной работы №2 (стр. 30).

Задание: составить математическую модель и решить задачу симплекс-методом.

1. Маленькая кондитерская фабрика должна закрыться на реконструкцию, поэтому надо реализовать оставшиеся запасы сырья, получив максимальную прибыль. Запасы и расход сырья для производства единицы продукции каждого вида, а также получаемая при этом прибыль представлены в таблице.

Ресурсы	Кондитерские изделия			Ограничения
	Батончик	Белка	Ромашка
Темный шоколад	1	2	1,1	1411
Светлый шоколад	0,1	0,1	0,2	149
Сахар	0,6	1,3	0,05	815,5
Карамель	0,3	0,7	0,5	466
Орехи	0,9	1,5	0	1080
прибыль	1,1	2	0,6

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

2. Предприятие может выпускать четыре вида продукции – П₁, П₂, П₃, П₄ без ограничений на количественный выпуск этой продукции. Для изготовления этой продукции предприятие располагает в течение месяца следующими ресурсами: трудовыми ресурсами в количестве 16 чел/нед, полуфабрикатами массой 110 кг, станочным оборудованием в объеме 100 станко/смен. Для изготовления одной штуки продукции П₁, П₂, П₃, П₄ требуется 1 чел/нед для каждого вида продукции, соответственно полуфабрикатов 6, 5, 4, 3 кг и станочного оборудования 4, 6, 10, 13 станко/смен. Цена 1 шт каждого вида продукции равна соответственно 60, 70, 120 и 130 д. ед. Требуется составить такой план выпуска, чтобы получаемый доход был максимальным. Условия данной задачи приведены в таблице:

Ресурс	Продукция				Объем ресурса
	П1	П2	П3	П4
Трудовые ресурсы, чел/нед	1	1	1	1	16
Полуфабрикаты, кг	6	5	4	3	110
Сменное оборудование, станко/смены	4	6	10	13	100
Цена 1 шт д. ед.	60	70	120	130
План выпуска	X1	X2	X3	X4

3. Участок цеха изготавливает три вида запасных деталей, проходящих обработку на двух станках: токарном и фрезерном. Затраты времени в часах на каждую деталь на токарном станке соответственно равны 2, 1, 2 часа; на фрезерном станке – 5, 2, 2 часа. Мощность токарного станка 30, фрезер- ного – 70.

Детали реализуются по следующей цене:

I вид	- 7 д. ед.
II вид	- 3 д. ед.
III вид	- 3 д. ед. за одну деталь.

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

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

Вид корма	Нормы расхода кормов (кг/день)				Ресурс кормов (кг)
	Песец	Лиса	Нутрия	Норка
I	1	2	1	2	300
II	1	4	2	0	400
III	1	1	3	2	600
Прибыль (д. ед./шкурка)	6	12	8	10

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

5. Торговое предприятие планирует организовать продажу четырех видов товара (A, B, C, D), используя при этом только два вида ресурсов: рабочее время продавцов в количестве 840 ч и площадь торгового зала 180 м². При этом известны плановые нормативы затрат этих ресурсов в расчете на единицу товаров A, B, C, и D и прибыль от их продажи, которые приведены в таблице. Требуется определить оптимальную структуру товарооборота, обеспечивающую торговому предприятию максимальную прибыль.

Показатели	Товар				Общее количество ресурсов
	A	B	C	D
Расход рабочего времени на единицу товара (ч)	0,6	0,8	0,6	0,4	840
Использование площади торгового зала на единицу товара (м^2)	0,1	0,2	0,4	0,1	180
Прибыль от продажи единицы товара (д. ед.)	5	8	7	9

6. Рацион кормления коров на молочной ферме может состоять из трех продуктов: сена, силоса и концентраторов. Эти продукты содержат питательные вещества: белок, кальций и витамины. Численные данные приведены в таблице. В расчете на одну корову суточные нормы потребления белка и кальция составляют не менее 200 г и 210 г соответственно. Потребление витаминов строго дозировано, и должно быть равно 87 мг в сутки.

Продукты	Питательные вещества
	Белок (г/кг)	Кальций (г/кг)	Витамины (мг/кг)
Сено	50	10	2
Силос	70	6	3
Концентраты	180	3	1

Составить самый дешевый рацион, если стоимость 1 кг сена, силоса и концентрата равна соответственно 1,5; 2; 6 д. ед.

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

Ресурсы	Нормы затрат на 1 изделие вида			Общее количество ресурсов
	1	2	3
Производительность оборудования (нормо/ч)
I типа	2	-	4	200
II типа	4	3	1	500
Сырье (кг):
1 вида	10	15	20	1495
2 вида	30	20	25	4500
Цена одного изделия (у. е.)	10	15	20

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

8. Для изготовления трех видов изделий A, B, C используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия для каждого из типов используемого оборудования, а также прибыль от реализации одного изделия данного вида указаны в таблице. Требуется определить, сколько изделий и какого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной. Составить математическую модель задачи.

Тип оборудования	Затраты времени (станко/час) на обработку изделия			Общий фонд рабочего времени оборудования (ч)
	A	B	C
Фрезерное	2	4	5	120
Токарное	1	8	6	280
Сварочное	7	4	5	240
Шлифовальное	4	6	7	360
Прибыль (д. ед.)	10	14	12

9. Продукцией городского молочного завода являются молоко, кефир и сметана, расфасованные в бутылки. На производство 1 т молока, кефира и сметаны требуется соответственно 1010, 1010 и 9450 кг молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машино/час. На расфасовке 1 т сметаны заняты специальные автоматы в течение 3,25 часа. Всего для производства цельномолочной продукции завод может использовать 136000 кг молока. Основное оборудование может быть занято в течение 21,4 машино/часов, а автоматы по расфасовке сметаны – в течение 16,25 часа. Прибыль от реализации 1 т молока, кефира, сметаны соответственно равна 30, 22 и 136 д. ед. Завод должен ежедневно производить не менее 100 т молока, расфасованного в бутылки. На производство другой продукции нет ограничений. Определить, какую продукцию и в каком количестве следует ежедневно поставлять заводу, чтобы прибыль от ее реализации была максимальной. Составить математическую модель задачи и решить ее симплекс-методом.

10. Из четырех видов сырья необходимо составить смесь, в состав которой должно входить не менее 26 единиц химического вещества A, 30 единиц вещества B и 24 единицы вещества C. Количество единиц химического вещества, содержащегося в 1 кг сырья каждого вида, указано в таблице. В ней же приведена цена 1 кг сырья каждого вида.

Вещество	Количество единиц вещества, содержащегося в 1 кг сырья вида
	1	2	3	4
A	1	1	-	4
B	2	-	3	5
C	1	2	4	6
Цена 1 кг сырья (д. ед.)	5	6	7	4

11. Объединение «Комфорт» производит холодильники, газовые плиты, морозильные шкафы и электропечи по цене 200, 180, 250, 100 д. ед. соответственно. Постоянным фактором, ограничивающим объем производства, является фиксированная величина трудовых ресурсов – 12000 человеко/часов в месяц. Выяснилось однако, что в ближайший месяц дефицитной будет и листовая сталь для корпусов указанных изделий, поскольку поставщики смогут обеспечить лишь 7000 м² материала. Требуется составить план производства на данный месяц, с тем, чтобы максимизировать стоимость выпущенной продукции. Известно, что для изготовления холодильника требуется 2 м² листовой стали и 3 человеко/часа рабочего времени, для газовой плиты – соответственно 1,5 м² и 3 человеко/часа, для морозильного шкафа – 3 м² и 4 человеко/часа, для электропечи – 1 м² и 2 человеко/часа.

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

Вид ресурсов	Нормы расходов ресурсов на единицу времени			Объем ресурсов
	I	II	III
Сталь (кг)	1	2	1	200
Цветные металлы (кг)	3	4	1	300
Токарные станки (ч)	3	6	5	600
Прибыль от реализации единицы изделия (д. ед.)	10	12	15

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

Станки	Технологические способы					Ресурсы времени станков (минуты)
	1	2	3	4	5
Токарный	2	1	3	0	1	4100
Фрезерный	1	0	2	2	1	2000
Строгальный	1	2	0	3	2	5800
Шлифовальный	3	4	2	1	1	10800

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

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

Ресурсы	Нормы затрат на 1 м ткани артикула			Общее количество ресурсов
	1	2	3
Производительность станков (станко/ч):
I типа	0,02	-	0,04	200
II типа	0,04	0,03	0,01	500
Пряжа (кг)	1,0	1,5	2,0	15000
Красители (кг)	0,03	0,02	0,025	450
Цена 1 м ткани (у. е.)	5	8	8

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

15. Предприятие выпускает четыре вида продукции и использует три типа основного оборудования: токарное, фрезерное, шлифовальное. Затраты времени на изготовление единицы продукции для каждого из типов оборудования приведены в таблице. В ней же указан общий фонд рабочего времени каждого из типов оборудования, а также прибыль от реализации одного изделия данного вида. Определить такой объем выпуска каждого из изделий, при котором общая прибыль от их реализации будет максимальной.

Тип оборудования	Затраты времени (станко/час) на единицу продукции вида				Общий фонд рабочего времени (станко/час)
	1	2	3	4
Токарное	2	1	1	3	300
Фрезерное	1	-	2	1	70
Шлифовальное	1	2	1	-	340
Прибыль от реализации единицы продукции (д. ед.)	8	3	2	1

16. Предприятие должно производить 3 вида продукции, используя при этом различное оборудование на каждой из трех операций. Мощность оборудования на I операции – 80 ч, на II – 50 ч, на III – 210 ч. Технические коэффициенты использования оборудования на одной операции для единицы каждой продукции равны соответственно:

I	- 2;	5;	0
II	- 3;	1;	1
III	- 13;	4;	4

Прибыль предприятия от единицы продукции каждого вида равна соответственно 13, 8, 4 д. ед. Определить, сколько продукции каждого вида должно выпустить предприятие, чтобы получить максимальную прибыль.

17. Предприятие выпускает три вида продукции. Уровень выпуска ее лимитируется ограниченностью имеющихся в распоряжении предприятия ресурсов (сырья, материалов, оборудования). Предприятие заинтересованно в определении такого уровня выпуска продукции по видам, при котором достигает максимума ее общая стоимость. Норма затрат ресурсов и стоимость единицы продукции каждого вида указаны в таблице:

Вид ресурсов	Норма затрат на единицу продукции			Объем ресурсов
	I	II	III
Сырье	5	7	4	860
Материал	5	2	1	300
Оборудование	2	1	1	200
Стоимость единицы продукции (д. ед.)	18	12	8

18. Стальные прутья длиной 110 см необходимо разрезать на заготовки длиной 45, 35 и 50 см. Требуемое количество заготовок данного вида составляет соответственно 40, 30 и 20 шт. Возможные варианты разреза и величина отходов при каждом из них приведены в следующей таблице:

Длина заготовки (см)	Варианты разреза
	1	2	3	4	5	6
45	2	1	1	-	-	-
35	-	1	-	3	1	-
50	-	-	1	-	1	2
Величина отходов (см)	20	30	15	5	25	10

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

19. Для изготовления различных изделий A, B, C предприятие использует три различных вида сырья. Норма расхода сырья на производство одного изделия каждого вида, цена одного изделия A, B, C, а также общее количество сырья каждого вида, которое может быть использовано предприятием, приведены в таблице. Изделия A, B, C могут производиться в любых соотношениях (сбыт обеспечен), но производство ограничено выделенным предприятию сырьем каждого вида. Составить план производства изделий, при котором общая стоимость всей произведенной предприятием продукции является максимальной.

Вид сырья	Нормы затрат сырья (кг)			Общее количество сырья (кг)
	A	B	C
I	18	15	12	360
II	6	4	8	192
III	5	3	3	180
Цена 1 шт (д. ед.)	9	10	16

20. Максимальная площадь, которая согласно перспективному плану может быть отведена под плодовые деревья, составляет 1000 га. На этой площади предполагается посадить три вида деревьев: семечковые, косточковые, ягодники. Обозначим их соответственно P₁, P₂, P₃. В хозяйстве имеется следующие три вида ограниченных ресурсов: пашня S₁, трудовые ресурсы S₂, денежно-материальные S₃. Запасы указанных ресурсов таковы: b₁, b₂, b₃. Известно, что на 1 га j-го вида посадок (j=1, 2, 3) затрачивается a_ij единиц i-го ресурса (i=1, 2, 3). Цена продукции с 1 га j-й культуры составляет c_ij д. ед. Численные значения исходных данных представлены в таблице:

Вид ресурсов	Вид продукции			Запас ресурсов
	P1	P2	P3
S1 (тыс. га)	a11=1	a12=1	a13=1	b1=1
S2 (тыс. чел/дней)	a21=100	a22=60	a23=200	b2=200
S3 (д. ед.)	a31=400	a32=200	a33=800	b3=600
Цена продукции с 1 га (д. ед.)	3	2	5

Требуется определить такие площади X₁, X₂, X₃ посадок каждого вида, чтобы обеспечить общий максимум продукции в стоимостном выражении.

21. При откорме животных каждое животное ежедневно должно получать не менее 60 единиц питательного вещества A, не менее 50 единиц вещества B и не менее 12 единиц вещества C. Указанные питательные вещества содержат три вида корма. Содержание единиц питательных веществ в 1 кг каждого из видов корма приведены в таблице. Составить дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах, если цена 1 кг корма I вида составляет 9 д. ед., корма II вида – 12 д. ед., и корма III вида – 10 д. ед.

Питательные вещества	Количество питательных веществ в 1 кг корма вида
	I	II	III
A	1	3	4
B	2	4	2
C	1	4	3

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

Наименование ресурса	Марка холодильника					Объем ресурса
	1	2	3	4	5
Трудозатраты (чел.)	2	3	5	4	4	9000
Металл (м^2)	2	2	4	5	0	8500
Пластик (м^2)	1	3	2	0	4	4000
Краска (кг)	1	2	3	3	2	5000
Прибыль (д. ед.)	40	70	120	120	50

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

23. Кондитерская фабрика для производства трех видов карамели A, B, C используют три вида основного сырья: сахарный песок, патоку и фруктовое пюре. Нормы расхода сырья на производство 1 т карамели данного вида приведены в таблице. В ней же указано общее количество сырья каждого вида, которое может быть использовано фабрикой, а также приведена прибыль от реализации карамели данного вида. Найти план производства карамели, обеспечивающий максимальную прибыль от ее реализации.

Вид сырья	Норма расхода сырья на 1 т карамели (т)			Общее количество сырья (т)
	A	B	C
Сахарный песок	0,8	0,5	0,6	800
Патока	0,4	0,4	0,3	600
Фруктовое пюре	-	0,1	0,1	120
Прибыль от реализации 1 т продукции (д. ед.)	108	112	126

24. Из листового проката необходимо вырезать заготовки двух видов A и B для производства 60 штук изделий. Для одного изделия требуется три заготовки типа A и восемь заготовок типа B. Размеры листа, а также размеры и конфигурация заготовок позволяют выбрать четыре рациональных варианта раскроя листа.

Заготовка	Вариант раскроя				Потребность
	1	2	3	4
A	4	3	2	1	180
B	0	4	6	10	480
Отходы	12	5	3	0

25. При производстве трех видов кабеля выполняется четыре группы технологических операций. Нормы затрат на 1 км кабеля данного вида на каждой из групп операций, прибыль от реализации 1 км каждого вида кабеля, а также общий фонд рабочего времени, в течение которого могут выполняться эти операции, указаны в таблице:

Технологическая операция	Нормы затрат времени на обработку 1 км кабеля (ч) вида			Общий фонд рабочего времени (ч)
	1	2	3
Волочение	1,2	1,8	1,6	7200
Наложений изоляций	1,0	0,4	0,8	5600
Освинцовывание	3,0	-	1,8	3600
Испытание в контроль	2,1	1,5	0,8	4200
Прибыль от реализации 1 км кабеля	1,2	0,8	1,0

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

26. Перед проектировщиками автомобиля поставлена задача: сконструировать самый дешевый кузов, используя листовой металл, стекло и пластмассу. Основные характеристики материалов представлены в таблице:

Характеристики	Материалы
	Металл	Стекло	Пластмасса
Стоимость (д. ед./м^2)	25	20	40
Масса (кг/м^2)	10	15	3

Общая поверхность кузова (вместе с дверьми и окнами) должна составить 14 м², из них не менее 4 м² металла и не более 5 м² следует отвести под стекло. Масса кузова не должна превышать 150 кг. Сколько металла, стекла и пластмассы должен использовать наилучший проект?

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

Виды ресурсов	Затраты ресурсов на изготовление единицы товара			Объем ресурсов
	I	II	III
Сырье (кг)	3	5	2	70
Рабочая сила (чел.)	6	5	8	160
Оборудование (ч)	16	14	18	400
Стоимость единицы товара (д. ед.)	17	35	20

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

28. Цех выпускает три вида деталей, которые изготавливаются на трех станках. Основные данные, связанные с выпуском и реализацией деталей, указаны в следующей таблице:

№ станка	Затраты времени на обработку 1 детали вида (мин)			Суточный ресурс рабочего времени (мин)
	I	II	III
1 станок	1	2	1	890
2 станок	3	-	2	920
3 станок	1	4	-	840
Стоимость одной детали (д. ед.)	3	1	2

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

29. На швейной фабрике для изготовления четырех видов изделий A, B, C и D может быть использована ткань трех артикулов. Нормы расхода тканей всех артикулов на пошив одного изделия приведены в таблице. В ней же указаны имеющееся в распоряжении фабрики общее количество тканей каждого артикула и цена одного изделия данного вида.

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

Артикул ткани	Нормы расхода ткани (м) на одно изделие вида				Общее количество ткани (м)
	A	B	C	D
I	1	-	2	1	354
II	-	1	3	2	178
III	4	2	-	4	286
Цена одного изделия (у. е.)	9	6	4	7

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

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

Ресурсы	Нормы затрат ресурсов на одно изделие				Общее количество ресурсов
	стол	стул	тумба	шкаф
Древесина (м^3) I вида	0,2	0,2	0,1	0,1	40
Древесина (м^3) II вида	0,1	0,2	0,2	0,3	60
Трудоемкость (человеко – ч.)	1,2	1,0	0,9	1,5	371,4
Прибыль от реализации одного изделия, д. ед.	6	3	4	8