Лабораторная работа №4
Симплексные методы решения
задач линейного программирования

Цель работы

Использование методов линейного программирования для решения конкретных экономических задач.

Порядок выполнения работы

1. Сформулировать заданную задачу как задачу линейного программирования.

2. Решить задачу методом последовательного улучшения плана или методом последовательного уточнения оценок. Дать смысловую интерпретацию полученного решения.

3. Составить двойственную задачу для любой поставленной задачи линейного программирования и решить её. Дать интерпретацию переменным двойственной задачи.

Варианты заданий

1. Плановое задание по изготовлению 4 видов костюмов необходимо распределить между 3 швейными фабриками. Производственные мощности i-й фабрики (i = 1, 2, 3) позволяют за рассматриваемый период времени выпустить r_ij костюмов j-й модели ( j = 1, 2, 3, 4). При этом, если все производственные мощности фабрики идут на производство костюмов одного типа, то костюмы других видов производиться не могут. Заданы цены c_j на костюм j-й модели и себестоимости s_ij изготовления j-й модели на i-й фабрике.

   R	S	C	X (плановое задание)
   20 240 300 150 240 300 200 300 150 240 300 300	400 400 500 200 250 300 250 400 400 500 400 300	500 650 800 500	180 150 100 100

   
   Опираясь на эти данные ответить на вопросы:
   • Может ли быть выполнено плановое задание?
   • Составить оптимальный план загрузки фабрик из условия минимизации себестоимости плановой продукции.
   • Составить оптимальный план загрузки из условия максимизации прибыли при точном выполнении планового задания.
   • То же, при допустимости перевыполнения планового задания.
   • Составить оптимальный план загрузки фабрик, обеспечивающий максимальное количество комплектов костюмов, если числа планового задания рассматривать как ассортиментные отношения.

   ---

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

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

   
   По этим исходным данным ответить на вопросы:
   • Какой ассортимент товара надо выпускать, чтобы прибыль была максимальной?
   • Определить, как повлияет на максимальную прибыль увеличение каждого ресурса на единицу.
   • Определить оптимальный ассортимент при дополнительном условии: 1-го товара выпустить не более 5 ед., 2-го - не менее 8 ед., а 3-го и 4-го в соотношении 1:2.
   • Дополнительно к пункту 1 заданы производственные издержки в рублях на 1 ед. каждого изделия: 60, 90, 120, 30. Найти оптимальный ассортимент, максимизирующий прибыль, при условии, что суммарные производственные издержки не должны превышать 960 руб.
   • Определить изменение в оптимальном ассортименте, найденном в пункте 1, если ресурсы сырья увеличены на 50%, а ресурсы рабочей силы и оборудования на 30%.

   ---

3. Нефтеперерабатывающий завод получает 4 различных полуфабриката: 400 тыс. л алкилата, 250 тыс. л крекинг-бензина, 350 тыс. л бензина прямой перегонки и 100 тыс. л изопентона. В результате смешивания этих четырех компонентов в разных пропорциях образуются три сорта авиационного бензина: бензин А 2:3:5:2, бензин Б - 3:1:2:1 и бензин С - 2:2:1:3. Стоимость 1 тыс. л указанных сортов бензина характеризуется числами 12000 руб., 10000 руб., 15000 руб.
   По этим исходным данным решить следующие задачи:
   • Определить план смешения компонентов, при котором будет достигнута максимальная стоимость всей продукции.
   • Определить оптимальный план смешения из условия максимального использования компонентов.

   ---

4. Полуфабрикаты поступают на предприятие в виде листов фанеры. Всего имеется две партии материала, причем первая партия содержит 400 листов, а вторая 250 листов фанеры. Из поступающих листов фанеры необходимо изготовить комплекты, включающие 4 детали 1-го типа, 3 детали 2-го типа и 2 детали 3-го типа. Лист фанеры каждой партии может раскраиваться различными способами.
   Количество деталей каждого типа, которое получается при раскрое одного листа соответствующей партии по тому или иному способу раскроя, представлено в таблице:

   Детали	Сп. раскроя 1 (партия 1)	Сп. раскроя 2 (партия 1)	Сп. раскроя 3 (партия 1)	Детали	Сп. раскроя 1 (партия 2)	Сп. раскроя 2 (партия 2)
   1	0	6	9	1	6	5
   2	4	3	4	2	5	4
   3	10	16	0	3	8	0

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

   ---

5. На фабрике производится продукты двух типов. Для производства используются станки трех типов, два типа сырья, квалифицированная и неквалифицированная рабочая сила.
   Сырье. Для производства одной единицы первого продукта требуется одна единица сырья первого типа и семь единиц сырья второго типа. Для производства одной единицы второго продукта требуется три единицы сырья первого типа и пять единиц сырья второго типа.
   Станки. Станок первого типа имеет ресурс мощности 3^.10⁶, второго типа - 1^.10⁶, третьего типа - 3^.10⁵. При производстве первого продукта используется 0.5 единиц ресурса мощности станка первого типа, 0.2 единицы ресурса мощности станка второго типа и 0.025 единиц ресурса мощности станка третьего типа. При производстве второго продукта используется 2 единицы ресурса мощности станка первого типа, 0.5 единиц ресурса мощности станка второго типа и 0.1 единица ресурса мощности станка третьего типа.
   Персонал. Бригада из одного квалифицированного рабочего и восьми неквалифированных рабочих может выпустить 1.5^.10⁵ единиц первого продукта. Бригада из двух квалифицированных рабочих и 11-ти неквалифированных рабочих может выпустить 4^.10⁴ единиц второго продукта.
   Стоимость одной единицы сырья первого типа 1 руб., второго типа - 0.15 руб. Стоимость одного станка первого типа 8^.10⁶ руб., станка второго типа - 7^.10⁶ руб., станка третьего типа - 9^.10⁶ руб. Амортизационные отчисления составляют 5 % от стоимости станка. Заработная плата квалифицированных рабочих 6.25^.10³ руб., неквалифицированных - 4^.10³ руб. Цена первого продукта составляет 3.5 руб., второго - 12.5 руб.
   Считается, что имеется неограниченное количество сырья. В наличии имеется 5 станков первого типа, 5 - второго типа, 3 - третьего типа. Максимальное число квалифицированных рабочих - 360, неквалифицированных - 2500. Платежеспособный спрос на первый продукт составляет 2.2^.10⁷ руб., на второй продукт - 2.7^.10⁷ руб.
   Плановое задание: 1.25^.10⁷ единиц первого продукта и 4^.10⁶ единиц второго продукта.
   По этим исходным данным решить следующие задачи:
   • Выполнимо ли плановое задание? Если да, то вычислить себестоимость плановой продукции и объем необходимых ресурсов.
   • Определить оптимальный план выпуска продукции из условия максимальной стоимости продукции.
   • Определить оптимальный план выпуска продукции из условия максимальной прибыли.

   ---

6. Фирма выпускает три продукта: A, B, C. На производство единицы продукта A требуется затратить 1 ч. труда ИТР, 10 ч. физического труда и 3 кг сырья. Для единицы продукта B соответствующие показатели равны 2 ч., 4 ч и 2 кг, для продукта C - 1 ч, 5 ч. и 1 кг. Ресурсы составляют 100 ч. труда ИТР, 700 ч. физического труда и 400 кг сырья. При оптовых закупках покупателю предоставляются скидки, так что прибыли от продажи продукции изменяются как показано в таблице. Например, если продается 120 ед. продукта A, то первые 40 ед. приносят по 10 долл. прибыли; следующие 60 - по 9 долл., а остальные 20 - по 8 долл. Сформулируйте задачу линейного программирования, решение которой определяет наиболее доходный производственный план.

   Продукт А		Продукт B		Продукт C
   Продажа, ед.	Удельная прибыль, руб.	Продажа, ед.	Удельная прибыль, руб.	Продажа, ед.	Удельная прибыль, руб.
   0 - 40	60000	0 - 50	36000	0 - 100	30000
   40 - 100	54000	50 - 100	24000	Более 100	24000
   100 - 150	48000	Более 100	18000	-	-
   Более 150	42000	-	-	-	-

   ---

7. Леспромхоз, имеющий лесопильный и фанерный цеха, столкнулся с проблемой наиболее рационального использования выделенной лесосеки. Чтобы получить 2.5 м³ коммерчески реализуемых комплектов пиломатериалов, необходимо израсходовать 2.5 м³ еловых и 7.5 м³ пихтовой древесины. Для изготовления 100 м² фанеры требуется 5 м³ еловых и 10 м³ пихтовой древесины. Выделенная лесосека содержит 80 м³ еловых и 180 м³ пихтовой древесины. Согласно условиям поставок, в течении планируемого периода необходимо произвести по крайней мере 10 м³ пиломатериалов и 1200 м² фанеры. Доход с 1 м³ пиломатериалов составляет 80 000 руб., а со 100 м² фанеры - 300 000 руб. Оптимизировать использование лесосеки.

   ---

8. Мебельное предприятие выпускает три вида наборов мебели, книжные полки и тумбу под телевизоры. Характеристики каждого вида продукции приведены в таблице. При условии получения максимальной прибыли объем товарной пилопродукции должен составить не менее 459 310 тыс. руб. Ситуация со сбытом продукции сложилась следующая. Книжными полками рынок насыщен поэтому торговые организации уменьшили объем договоров до 10 тыс. шт. Тумбы для телевизоров могут быть реализованы в объемах от 4 до 7 тыс. шт., наборы мебели 2 - от 7 до 10 тыс. шт. Спрос на наборы мебели 1 и 3 неограничен и требуется не менее 10 тыс. шт. Предприятие имеет технологическое оборудование, число единиц которого и нормы затрат времени оборудования каждой группы на изготовление единицы каждого вида продукции приведены в таблице. Предприятие работает в две смены с эффективным временем работы каждой машины в 3945 ч. (коэффициент сменности 1.9). Оптимизировать производственную программу предприятия.

   Показатель	Виды продукции
   	Набор мебели 1	Набор мебели 2	Набор мебели 3	Книжные полки	Тумба под телевизор
   Оптовая цена единицы изделия, руб.	7200	14000	32000	180	1500
   Прибыль от реализации, руб.	2400	4500	60000	60	450

   Наименование оборудования	Число, шт.	Виды продукции
   		Набор мебели 1	Набор мебели 2	Набор мебели 3	Книжные полки	Тумба под телевизор
   Линия раскроя древесно-стружечных плит	2	0.068	0.096	0.207	0.018	0.042
   Гильотинные ножницы	1	0.045	0.080	0.158	0.011	0.035
   Линия облицовывания	2	0.132	0.184	0.428	0.020	0.060
   Линия обрезания кромок	2	0.057	0.082	0.230	0.010	0.028
   Лаконаливная машина	2	0.063	0.090	0.217	0.010	0.032
   Полировальные станки	4	0.170	0.280	0.620	0.020	0.096

   ---

9. В леспромхозе производится раскряжевка хлыстов на сортименты. Требуется получить сортименты трех видов - длиной 6, 2.2 и 1.5 м. Длина среднего хлыста 31 м, средний диаметр 0.3 м. План поставки сортиментов, соответственно, 30000 м³, 86000 м³ и 40000 м³. Используя карту раскроя хлыстов без учета толщины пропила определить оптимальный план раскроя.

   Сортимент, м	Варианты раскроя хлыстов
   	1	2	3	4	5	6	7	8	9	10	11
   6 2.2 1.5	5 0 0	4 2 1	4 1 3	3 5 1	3 0 8	2 4 6	2 1 11	1 9 3	1 2 13	0 10 6	0 1 19
   Отходы	1	1.1	0.3	0.5	1.0	1.2	0.3	0.7	1.1	0	0.3

   ---

10. Нижний склад производит два вида продукции: обрезную доску и брус. Для изготовления 1 м³ бруса требуется 2,5 м³ сосны или 3 м³ ели. Для изготовления 1 м³ доски требуется 3 м³ сосны или 3.5 м³ ели. Максимальные суточные запасы сосны - 200 м³, ели - 300 м³. Суточный спрос на брус - 100 м³, на доску - 150 м³ при оптовых ценах за 1 м³ бруса - 200 000 руб., за 1 м³ доски - 300 000 руб. Определить оптимальные объемы выпуска бруса и доски.

    ---

11. Лесхоз для кормления животных использует два вида корма. В дневном рационе животного должно содержаться не менее 6 единиц вещества A и 12 единиц B. Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальны (по данным в таблице).

    Питательные вещества	Количество питательных веществ в 1 кг корма
    	вида 1	вида 2
    A B	2 2	1 4
    Цена 1 кг корма, руб	2	3

    ---

12. В деревообрабатывающий цех завода поступил заказ вырезать из фанеры заготовки двух видов для 1000 изделий. Известно, что на одно изделие идет две заготовки первого вида и 3 - второго. На складе имеется 800 листов. Существуют три способа раскроя: при первом способе из листа фанеры получается 3 заготовок 1 вида и 2 заготовки 2 вида, при втором: 1 заготовка первого вида и 2 заготовки второго и при третьем - соответственно 2 и 2. Сколько листов фанеры надо выкроить по каждому способу, чтобы выполнить заказ и расход фанеры был минимальным?

    ---

13. Леспромхоз имеет древесину трех видов в количествах 1000 м³, 500 м³, и 700 м³ для изготовления изделий A, B, C и D. Нормы расхода древесины в м³ на изготовление единицы каждого изделия и прибыль от реализации единицы изделия даны в таблице. Определить, сколько изделий каждого вида должно произвести предприятие, чтобы общая прибыль от реализации всех изделий была максимальной?

    Сырье	Нормы расхода сырья на единицу изделия
    	A	B	C	D
    1 2 3	0.1 0.2 0.4	0.15 0.4 0.5	0.2 0.3 0.1	0.25 0.1 0.2
    Прибыль, руб	10	20	30	10

    ---

14. Производство двух видов лесопродукции должно пройти три операции. Затраты времени на каждой операции на одно изделие, прибыль от реализации одного изделия даны в таблице. Сколько изделий каждого вида должно произвести предприятие, чтобы получить максимум прибыли, причем число изделий A должно быть не менее 10, а B - не более 70 единиц.

    Изделия	Затраты на одно изделие			Прибыль, руб.
    	1	2	3
    A B	11 6	7 8	16 9	25 38
    Фонд времени на каждую операцию	600	700	1300

    ---

15. Предприятие должно выпустить по плану продукции A - 500 единиц, B - 300 единиц, C - 450 единиц на двух машинах. Каждая из двух машин может выполнить операции по производству всех трех видов продукции. Затраты времени на производстве единицы изделия каждой из двух машин приведены в таблице. Как распределить работу машин, чтобы затраты времени на выполнение плана были минимальны?

    Машины	Продукция
    	A	B	C
    1 2	4 6	10 8	10 20

     

    ---

    Предприятию задана месячная программа по изготовлению четырех видов изделий в количествах: вида A - 5000, B - 2000, C - 3000, D - 1600. На предприятии имеется три группы станков с различной производительностью. Задается суммарное допустимое время работы за этот период для каждой группы станков: первой - 800 ч., второй - 1000 ч., третьей - 1500 ч. Нормы времени (в часах) на изготовление одного изделия на каждом станке и данные об издержках (в рублях) на изготовление каждого изделия на станках различных групп приводятся в табл. 2.19. Требуется так распределить изготовление изделий по группам станков, чтобы была обеспечена заданная программа по изготовлению изделий и чтобы общие издержки были минимальны?

    Таблица 2.20

    Группы станков	Нормы времени на станках, час				Издержки на изготовление единицы изделия, руб
    	1	2	3	4		A	B	C	D
    1 11 111	0,5 0,4 0,4	0,3 0,2 0,1	0,4 0,2 0,3	0,1 0,5 0,6		0,12 0,15 0,18	0,25 0,15 0,35	0,3 0,4 0,5	0,4 0,2 0,1

     

    ---

Содержание отчета

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