Решение задач линейного программирования графическим методом

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Нижегородский государственный педагогический университет

имени Козьмы Минина»

(Мининский университет)

 

 

Факультет естественных, математических и компьютерных наук

 

 

 

 

Контрольная работа

по

математическому и имитационному моделированию

 

 

 

Выполнил студент:

Группа: ПМЗ-13

Проверил: преподаватель Круподерова К.Р

 

Нижний Новгород

2014

Решение задач линейного программирования графическим методом

Задача 7 (об использовании сырья). Для изготовления двух видов продукции П1 и П2 используется три вида сырья: С1, С2 и С3. Запасы сырья на складе и количество единиц сырья, затрачиваемых на изготовление единицы продукции, приведены в табл. 6.

Таблица 6

Вид сырья	Запас сырья	Количество единиц сырья на изготовление единицы продукции
		П1	П2
С1	20	2	5
С2	40	8	5
С3	30	5	6

 

 

Прибыль от реализации единицы продукции П1 составляет 50 руб., продукции П2 - 40 руб. Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.

Решение

 

Необходимо найти максимальное значение целевой функции F = 50x1+40x2 → max, при системе ограничений:

2x1+5x2≤20	(1)
8x1+5x2≤40	(2)
5x1+6x2≤30	(3)
x1≥0	(4)
x2≥0	(5)

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

или

Границы области допустимых решений

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

Рассмотрим целевую функцию задачи F = 50x1+40x2 → max.  
Построим прямую, отвечающую значению функции F = 0: F = 50x1+40x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (50; 40). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

 

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

Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых: 
8x1+5x2=40 
5x1+6x2=30 
 
Решив систему уравнений, получим: x1 = 3.913, x2 = 1.7391 
Откуда найдем максимальное значение целевой функции: 
F(X) = 50*3.913 + 40*1.7391 = 265.2174

Задача 2. Для изготовления изделий А, В и С в качестве сырья используется сталь, алюминий и цветные металлы, объемы которых ограничены. Изделия производятся на токарных, фрезерных и шлифовальных станках. Требуется составить план выпуска продукции, при котором будет достигнута максимальная прибыль от реализации всей продукции. Составить математическую модель задачи при данных, приведенных в таблице.

Вид ресурса	Объем ресурса	Норма расхода на единицу ресурса
		А	В	С
Сталь (кг)	800	15	20	40
Алюминий (кг)	600	8	15	10
Цветные металлы (кг)	300	3	6	4
Станко-токарные (ч)	4800	60	80	120
Станко-фрезерные (ч)	5600	80	70	28
Станко-шлифовальные (ч)	600	6	10	12
Прибыль (ден. ед.)		30	40	60