Лабораторная №1 «Линейное программирование» (стр. 1 )

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

«Линейное программирование»

(двумерный случай)

Задача №1 . Фирма производит изделия двух видов 1 и 2. На производство изделия 1 требуется а11 (чел.-час.), изделия 2 - а21 (чел.-час.). Издержки производства составляют а12 (тыс. руб.) и а22 (тыс. руб.), прибыль – с1 (тыс. руб.) и с2 (тыс. руб.) соответственно. Имеются ограничения:

1. На изготовление может быть потрачено не более d1 (чел.-час.);

2. Еженедельные издержки производства не должны превышать d2 (тыс. руб.) ;

3. По контракту в неделю необходимо поставлять не менее d3 изделий вида 1 и d4 –вида 2.

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

Указание к решению. Сформулируйте задачу в терминах задач линейного программирования на максимизацию и минимизацию (двойственные задачи). Сведите задачу к двумерному виду и решите ее графическим методом.

Задача №2 . (транспортная задача). На три стройки (W1, W2, W3) необходимо поставить кирпич, причем имеется возможность поставок с двух заводов (F1, F2). Потребности строек в кирпиче wj, возможности поставок с каждого завода fi и издержки перевозок кирпича автомашинами с i-го завода на j-ю стройку сij указаны в таблице.

Кирпичные заводы	Издержки перевозок с i-го завода на j-ю стройку, тыс. руб. на машину	Возможности поставок заводов, автомашин в неделю
Стройки
W1	W2	W3
F1	С11	С12	С13	f1
F2	C21	C22	C23	f2
Потребность строек, автомашин в неделю	w1	w2	w3	,

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

Указание к решению. Сформулируйте задачу к двумерному виду и решите ее графическим методом.

Задание к лабораторной работе

1. Сформулируйте задачу №1 (максимизация прибыли) в терминах стандартных задач линейного программирования на максимизацию и минимизацию (двойственные задачи).

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

3. Дайте экономическую интерпретацию оптимального решения.

4. Оцените (качественно) чувствительность оптимального плана производства к изменению исходных условий задачи.

5. Сформулируйте задачу №2 (оптимальный план перевозок) в терминах стандартных задач линейного программирования (транспортная задача).

6. Постройте граф с вершинами поставщиками, вершинами потребителями и дугами с интенсивностью перевозок.

7. Представьте графически множество допустимых решений. Решите задачу поиска оптимального плана графическим методом, с учетом целочисленного характера переменных. Дайте экономическую интерпретацию оптимального плана перевозок.

Вариант№1

Задача №1
Трудоемкость производства, чел.-час.	Стоимость производства, тыс. руб.
а11	а21	d1	а12	а22	d2
7,5	5,5	260	5,5	3,5	180
Прибыль, тыс. руб.	Минимальное число изделий
c1	c2	d1	d2
1,8	1,5	10	15

Задача №2
Потребности строек, машин	Возможности поставок, машин
w1	w2	w3	f1	f2
7	10	8	12	13
Издержки перевозок, тыс. руб.
c11	c12	c13	c21	c22	c23
4	3	3	2	5	4

Вариант№2

Задача №1
Трудоемкость производства, чел.-час.	Стоимость производства, тыс. руб.
а11	а21	d1	а12	а22	d2
7	5	280	5	3	180
Прибыль, тыс. руб.	Минимальное число изделий
c1	c2	d1	d2
1,85	1,55	11	14

Задача №2
Потребности строек, машин	Возможности поставок, машин
w1	w2	w3	f1	f2
6	10	8	11	13
Издержки перевозок, тыс. руб.
c11	c12	c13	c21	c22	c23
5	4	3	3	2	4

Вариант№3