Основные виды записи задач линейного программирования

Общей задачей линейного программирования называют задачу:  

найти max (min)

при ограничениях  в_i (i = ),

x_j ³ 0 (j = ),

 где , а_ij, в_i – заданные числа, Z – целевая функция, ={х₁... х_n} – план. Ограничения могут быть записаны и в виде: в_i, в_i, где (i = ).

Симметричной формой записи задачи линейного программирования называют задачу вида:

найти max

при ограничениях в_i (i = ),

x_j ³ 0

  Или задачу вида:

найти min    

при ограничениях в_i (i = ),

x_j ³ 0

 

Канонической формой записи задачи линейного программирования называют задачу вида:

найти max(min)

                  при ограничениях  в_i, (i = ),

x_j ³ 0 (j = ).

От симметричной формы записи всегда можно перейти к канониче­ской форме записи согласно рассмотренной выше теореме.

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

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

1. Некоторая фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений, а в улучшенный – 2 кг азотных, 6 кг фосфорных и 3 кг калий­ных удобрений. Известно, что для некоторого газона требуется, по меньшей мере, 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Обычный набор стоит 3 у. е., а улучшенный – 4 у. е. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

2. Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем производства первой линии – 60 изделий, второй линии – 75 изделий. На радиоприемник первой модели расходуется 10 однотипных элементов электронных схем, на радиоприемник второй модели – 8 таких же элементов. Максимальный суточный запас используемых элементов равен 800 единицам. Прибыль от реализации одного радиоприемника первой и второй модели равна 30 и 20 у. е., соответственно. Определить оптимальный суточный объем производства первой и второй моделей.

3. Процесс изготовления двух видов промышленных изделий состоит в последовательной обработке каждого из них на трех станках. Время использования каждого из этих станков для производства данных изделий ограничено 10-ю часами в сутки. Время обработки и прибыль от продажи одного изделия каждого вида приведены в табл. 4. Найти оптимальный объем производства изделий каждого вида.

Таблица 4

Изделие	Время обработки одного изделия, мин.			Удельная прибыль, у. е.
	Станок 1	Станок 2	Станок 3
1	10	6	8	2
2	5	20	15	3

 

4. Фирма производит два вида продукции – А и В. объем сбыта продукции А составляет не менее 60 % общего объема реализации продукции обоих видов. Для изготовления продукции А и В используется одно и тоже сырье, суточный запас которого ограничен величиной 100 кг. Расход сырья на единицу продукции А составляет 2 кг., а на единицу продукции В – 4 кг. Цены продукции А и В равны 20 и 40 у. е., соответственно. Определить оптимальное распределение сырья для изготовления продукции А и В.

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

 

Таблица 5

Виды кормов	Содержание в 1 кг кормов			Себестоимость 1 кг кормов,руб.
	Кормовых единиц, г.	Белка, г.	Кальция, г
Сено	0,5	50	10	15
Концентраты	1,0	200	2	225
Минимальная суточная потребность	20	2000	100

 

6. В суточный рацион включают два продукта питания П₁ и П₂, причем продукта П₁ должно войти в двойной рацион не более 200 ед.  Стоимость 1 ед. продукта П₁ составляет 2 р., продукта П₂ – 4р. Содержание питательных веществ в 1 ед. продукта, минимальные нормы потребления указаны в табл. 6.

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

Таблица 6

Питательные Вещества	Минимальная норма потребления	Содержание питательных веществ в 1 ед. продукта
		П1	П2
А	120	0,2	0,2
В	160	0,4	0,2

 

Провести анализ задач с использованием графического метода.

7. Фирма выпускает изделия двух типов: А и В. При этом используется сырье четырех видов. Расход сырья каждого вида на изготовление единицы продукции и запасы сырья заданы в табл. 7.

Таблица 7

Изделия	Сырье, ед.
	1	2	3	4
А	2	3	0	2
В	3	0	1	1
Запасы сырья	21	4	6	10

 

Выпуск одно изделия типа А приносит доход 300 р., одного изделия типа В – 200 р.

Составить план производства, обеспечивающий фирме наибольший доход.

8. Обработка деталей А и В может производиться на трех станках, причем каждая деталь должна последовательно обрабатываться на каждом из станков. Прибыль от реализации детали А – 100р., детали В – 160 р. Исходные данные приведены в табл. 8.

Таблица 8

Станки	Норма времени на обработку одной детали, ч		Время работы станка, ч
	А	В
1	0,2	0,1	100
2	0,2	0,5	180
3	0,1	0,2	100

 

Определить производственную программу, максимизирую-щую прибыль при условии: спрос на деталь А – не менее 300 шт., на деталь В – не более 200 шт.

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

Таблица 9

Виды сырья	Норма расхода сырья на выпуск изделий, кг		Запасы сырья, кг
	П1	П2
C1	3	5	453
C2	4	8	616
C3	3	11	627
Прибыль от реализации единицы продукции, руб.	200	500

 

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

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

Таблица 10

Виды сырья	Норма расхода сырья на выпуск изделий, кг		Запасы сырья, кг
	П1	П2
C1	15	4	1095
C2	11	5	865
C3	9	10	1080
Прибыль от реализации ед. продукции, руб.	300	200

 

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

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

Таблица 11

Группа оборудования	Необходимое количество единиц оборудования на выпуск 1 комплекта продукции		Количество оборудования в группе
	1	2
А	2	2	12
B	1	2	8
C	4	0	16
Д	0	4	12
Чистый доход на 1 штуку, тыс. руб	2	3

 

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

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

Таблица 12

Виды сырья	Норма расхода сырья на выпуск изделий, кг		Объем ресурсов, кг
	A	B
1	8	6	1620
2	5	7	1400
3	7	3	1540
Стоимость единицы продукции, руб.	10	12

 

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

13. При подкормке посевов нужно на 1 га почвы химических веществ A, B, C, Д  в количествах, не менее указанных в таблице. Совхоз закупает комбинированные удобрения двух видов. В табл. 13 указаны содержание химических веществ и цена единицы каждого вида удобрения.

Таблица 13

Химические вещества	Содержание химического вещества в удобрении		Норма расхода химических веществ на 1 га
	1	2
А	2	1	60
В	2	4	120
С	–	4	40
Д	6	–	90
Стоимость единицы продукции, руб.	50	60

 

Составить план наиболее экономичной закупки удобрений.

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

Таблица 14

Ресурсы	Технологический процесс		Объем ресурсов
	1	2
Сырье	15	12	1200
Электроэнергия	0,2	0,4	30
Накладные расходы	6	5	600
Зарплата	3	4	300

 

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

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

 Таблица 15

Виды продукции	Нормы затрат			Прибыль на единицу продукции, руб.
	Рабочее время, чел.-ч.	древесина, м^3	стекло
Стол	9,2	0,3	-	300
Шкаф	4,0	0,6	2,0	300
Ресурсы	520	24	80

  

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

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

Таблица 16

Виды ресурсы	Вид товара		Объем ресурса
	1	2
Сырье, кг	6	5	150
Рабочая сила, ч	2	4	60
Оборудование, станко-ч.	4	16	200
Прибыль на единицу товара, руб.	100	300

 

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