Лабораторная работа №1.

Решение задач линейного программирования.

 

Задача. Найти экстремум (максимум или минимум) линейной целевой функции:

при ограничениях (условиях):

где заданные постоянные величины.

 

Решение.

1) Специальной переменной ORIGIN присваивают значение 1. Значением ORIGIN является номер первого элемента строки или столбца в матрице. По умолчанию ORIGIN=0.

В меню Math выбрать строку Options или

 

 

2) Вводят исходные данные задачи в матричной форме.

 

3) Вводят линейную целевую функцию.

4) Задают начальные значения переменным задачи.

 

 

5) Вводят ограничения задачи в матричной форме (в случае небольшого числа переменных можно ввести ограничения в естественной форме)

 

или

 

6) Определяют оптимальное решение задачи с помощью встроенной функции Maximize (в случае поиска максимума функции) или Minimize (в случае поиска минимума функции).

 

 

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

Пример.

 

Найти максимальное значение функции

при заданных ограничениях

 

Решение.

1) Специальной переменной ORIGIN присваивают значение 1. Значением ORIGIN является номер первого элемента строки или столбца в матрице. По умолчанию ORIGIN=0.

В меню Math выбрать строку Options или

 

 

2) Вводят исходные данные задачи в матричной форме.

 

 

3)                  Вводят линейную целевую функцию.

 

 

4) Задают начальные значения переменным задачи.

 

 

5) Вводят ограничения задачи в матричной форме.

 

 

6) Определяют оптимальное решение задачи с помощью встроенной функции Maximize (в случае поиска максимума функции) или Minimize (в случае поиска минимума функции).

 

 

7) В случае задачи с двумя переменными строят график.

 

 

 

 

Задания для лабораторной работы №1.

Задачи линейного программирования.

 

1.      Задача об использовании ресурсов (задача планирования производства).

1.1  Для изготовления двух видов продукции P₁ и P₂ используют четыре вида ресурсов S₁, S₂, S₃ и S₄. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, прибыль, получаемая от единицы продукции, приведены в таблице:

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

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

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

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

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

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

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

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

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

Вид сырья	Нормы расхода сырья (т) на 1 т карамели			Общее количество сырья (т)
	А	В	С
Сахарный песок	0.8	0.5	0.6	800
Патока	0.4	0.4	0.3	600
Фруктовое пюре	-	0.1	0.1	120
Прибыль от реализации 1 т продукции (ден. ед.)	108	112	126

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

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

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

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

1.6  Для изготовления двух видов продукции P₁ и P₂ используют четыре вида ресурсов S₁, S₂, S₃. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, прибыль, получаемая от единицы продукции, приведены в таблице:

Вид ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции		Запас ресурса
	P1	P2
S1	2	3	180
S2	4	1	240
S3	6	7	426
Прибыль, получаемая от единицы продукции	16	12

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

1.7  Для изготовления двух видов продукции P₁ и P₂ используют четыре вида ресурсов S₁, S₂, S₃. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, прибыль, получаемая от единицы продукции, приведены в таблице:

Вид ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции		Запас ресурса
	P1	P2
S1	10	8	168
S2	5	10	180
S3	6	12	144
Прибыль, получаемая от единицы продукции	14	18

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

1.8  Для изготовления двух видов продукции P₁ и P₂ используют четыре вида ресурсов S₁, S₂, S₃. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, прибыль, получаемая от единицы продукции, приведены в таблице:

Вид ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции		Запас ресурса
	P1	P2
S1	0.2	0.1	40
S2	0.1	0.3	60
S3	1.2	1.5	371.4
Прибыль, получаемая от единицы продукции	6	8

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

1.9  Для изготовления двух видов продукции P₁, P₂, P₃ и P₄ используют четыре вида ресурсов S₁, S₂, S₃. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, прибыль, получаемая от единицы продукции, приведены в таблице:

Вид ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции				Запас ресурса
	P1	P2	P3	P4
S1	1	-	2	1	180
S2	-	1	3	2	210
S3	4	2	-	4	800
Прибыль, получаемая от единицы продукции	9	6	4	7

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

1.10      Для изготовления двух видов продукции P₁ – P₄ используют четыре вида ресурсов S₁, S₂, S₃. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, прибыль, получаемая от единицы продукции, приведены в таблице:

Вид ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции				Запас ресурса
	P1	P2	P3	P4
S1	2	1	1	3	300
S2	1	-	2	1	70
S3	1	2	1	-	340
Прибыль, получаемая от единицы продукции	8	3	2	1

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

 

2.     Задача составления рациона (задача о диете, задача о смесях).

2.1  Имеется два вида корма I и II, содержащие питательные вещества (витамины) S₁, S₂ и S₃. Содержание числа единиц питательных веществ в 1 кг каждого вида корма, стоимость 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице:

Питательное вещество (витамин)	Число единиц питательных веществ в 1 кг корма		Необходимый минимум питательных веществ
	I	II
S1	3	1	9
S2	1	2	8
S3	1	6	12
Стоимость 1 кг корма	4	6

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

2.2  Рацион для питания животных на ферме состоит из двух видов кормов I и II. 1 кг корма I стоит 80 ден. ед. и содержит: 1 ед. жиров, 3 ед. белков, 1 ед. углеводов, 2 ед. нитратов. 1 кг корма II стоит 10 ден. ед. и содержит 3 ед. жиров, 1 ед. белков, 8 ед. углеводов, 4 ед. нитратов.

Составить наиболее дешевый рацион питания, обеспечивающий жиров не менее 6 ед., белков не менее 9 ед., углеводов не менее 8 ед., нитратов не более 16 ед.

2.3  При откорме животных каждое животное ежедневно должно получить не менее 60 ед. питательного вещества А, не менее 50 ед. вещества В и не менее 12 ед. вещества С. Указанные питательные вещества содержат три вида корма. Содержание единиц питательных веществ в 1 кг каждого из видов корма приведено в следующей таблице:

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

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

3.     Задача об использовании мощностей (задача о загрузке оборудования).

3.1  Предприятию задан план производства продукции по времени и номенклатуре: требуется за время T выпустить n₁, n₂, …, n_k единиц продукции P₁, P₂, …, P_k. Продукция производится на станках S₁, S₂, …, S_m. Для каждого станка известны производительность a_ij (т.е. число единиц продукции, которое можно произвести на станке S_i) и затраты b_ij на изготовление продукции P_j на станке S_i в единицу времени.

Необходимо составить такой план работы станков (т.е. так распределить выпуск продукции между станками), чтобы затраты на производство всей продукции были минимальными.

3.2  На двух автоматических линиях выпускают аппараты трех типов. Другие условия задачи приведены в таблице:

Тип аппарата	Производительность работы линий, шт. в сутки		Затраты на работу линий, ден. ед. в сутки		План, шт.
	1	2	1	2
А	4	3	400	300	50
В	6	5	100	200	40
С	8	2	300	400	50

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

4.     Задача о раскрое материалов.

4.1  На раскрой (распил, обработку) поступает материал одного образца в количестве a единиц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональных числам b₁, b₂, …, b_l (условие комплектности). Каждая единица материала может быть раскроена n различными способами, причем использование i-го способа (i=1,2,…,n) дает a_ik единиц k-го изделия (k=1,2,..,l).

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

4.2  Для изготовления брусьев длиной 1,2м, 3м и 5м в соотношении 2:1:3 на распил поступают 195 бревен длиной 6м. Определить план распила, обеспечивающий максимальное число комплектов.

4.3  Необходимо распилить 20 бревен длиной по 5 м каждое на бруски по 2 м и 3 м; при этом должно получиться равное количество брусков каждого размера. Составить такой план распила, при котором будет получено максимальное число комплектов и все бревна будут распилены (в один комплект входит по одному бруску каждого размера).