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

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

Вариант 13.

 

Наиболее простым  и  наглядным методом линейного  программирования (ЛП) является графический  метод. Он применяется для решения  задач ЛП с двумя переменными.

Задачи 1 – 15. Цех выпускает два вида продукции П₁ и П₂, используя два вида полуфабрикатов – Р₁ и Р₂. Продукция используется при комплектации изделий, при этом на каждую единицу продукции первого вида требуется не более k единиц продукции второго вида. Известны нормы расхода a_ij полуфабрикатов каждого вида на единицу выпускаемой продукции, общие объемы b_i полуфабрикатов и прибыль p_j от продажи единицы продукции (i = 1,2; j = 1,2). По данным табл. 7.1 определите план производства продукции П₁ и П₂, доставляющий максимум прибыли.

Таблица 1

Пара- метр	Числовые данные для номеров задач
	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
a11	1	2	1	2	10	11	10	1	2	2	2	3	1	2	4
a12	2	5	3	3	3	6	3	3	3	5	7	7	7	13	11
a21	6	5	4	2	2	3	2	2	3	7	10	9	8	11	9
a22	2	1	1	1	7	13	7	1	1	3	3	3	1	3	5
b1	800	1385	900	300	132	120	352	420	451	510	516	477	266	1250	925
b2	2400	645	1180	350	138	160	370	390	400	464	532	459	313	529	630
p1	10	12	10	8	3	12	3	1	5	6	7	15	2	3	2
p2	35	30	20	24	15	15	10	4	4	18	18	6	8	18	10
k	2	3	1	2	3	5	2	1	2	3	2	2	2	4	3

 

Решение: Пусть x = ( ) – план задачи. Тогда модель задачи примет вид

 

max Z =2 +8

 

Ограничения на полуфабрикаты:

 

+8 ≤266,

7 + ≤313

 

Условие комплектности  и неотрицательности переменных:

 

2 ≥

≥0, ≥0.

 

 

 

 

 

Таблица 2

Полуфабрикаты	Нормы затрат на единицу продукции		Объём полуфабриката
PI PII	1 7	8 1	266 313
Прибыль	2	8

 

В первую очередь найдем область  допустимых значений, то есть точки  x1 и x2, которые удовлетворяют системе ограничений. По условию задачи x1≥0  и  x2 ≥0. Мы рассматриваем только те точки, которые принадлежат первой четверти.

Шаг первый:

Рассмотрим неравенство  первой системы ограничений:

X1+8X2≤266

Построим прямую.

Заменим знак неравенства  на знак равенства.

X1+8X2=266

Преобразуем уравнение следующим  образом:

+=266

Каждый член уравнения разделим на 266

+=1

Данное представление прямой называется уравнением прямой в отрезках и позволяет очень легко нарисовать данную прямую. На оси X1 рисуем точку с координатой 266, на оси X2 рисуем точку с координатой 133/4. Соединяем эти точки и получаем необходимую прямую.

Какие точки нас интересуют?

X1+8X2≤266

8X2≤-X1+266

X2≤-1/8X1+133/4

Знак неравенства меньше или равно нуля, следовательно, нас  интересуют точки, лежащие ниже построенной  прямой.

 

Рис. 1

 

 

Область допустимых значений выделена штриховкой. Точки, принадлежащие  области допустимых значений: А(0;0), В(0;266), С(133/4;0)

Шаг 2:

Рассмотрим неравенство  второй системы ограничений:

7X1+X2≤313

Построим прямую.

Заменим знак неравенства  на знак равенства

7X1+X2=313

Преобразуем уравнение следующим  образом:

+=313

Каждый член уравнения  разделим на 313

+=1

Аналогичным образом рисуем на оси X1 точку с  координатой 313/7, а на оси X2 точкус координатой 313.

Соединяем точки и получаем необходимую прямую.

Какие точки нас интересуют?

7X1+X2≤313

X2≤ -7X1+313

Знак неравенства меньше или равно нуля, следовательно, нас  интересуют точки, расположенные ниже построенной прямой.

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

Рис 2.

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

Точки, принадлежащие области  допустимых значений: А(0;0), D(313/7;0), С(0;133/4), Е (2238/55;1549/55)

Шаг 3:

Рассмотрим неравенство  третьей системы ограничений:

2X1-X2≥0

Построим прямую.

Заменим знак неравенства  на знак равенства.

2X1-X2=0

-X2=-2X1

X2=2X1

Прямая проходит через начало координат

Какие точки нас интересуют?

 

 

2X1-X2≥0

-2X1+X2≤0

X2≤2X1

Знак неравенства меньше или равно нуля, следовательно, нас  интересуют точки, расположенные ниже построенной прямой.

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

 

Рис. 3

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

Точки, принадлежащие области  допустимых значений: А(0;0), D(313/7;0), Е(2238/55;1549/55), F(266/17;532/17)

Шаг 4:

Вернемся к нашей исходной функции Z=2x1+8x2. Допустим, значение функции Z=1, тогда 1=2x1+8x2. Данное уравнение является уравнением прямой на плоскости. Из курса геометрии известно, что данная прямая перпендикулярна вектору, координатами которого являются коэффициенты функции, а именно вектору =(2;8). Следовательно, с геометрической точки зрения, исходная функция Z изображается как множество прямых, перпендикулярных вектору =(2;8).

На рисунке вектор изображен  красным цветом.( Вектор нарисован для наглядности)

Будем перемещать прямую перпендикулярно  вектору до тех пор, пока она полностью не пройдет область допустимых значений. Касание прямой, перед выходом  из области допустимых значений произойдет в т. Е(2238/55;1549/55). В данной точке значение функции будет наибольшим.

Рис. 4

 

 

 

 

Ответ:

Наибольшее значение функция  достигает при

X1=2238/55

X2=1549/55

Значение функции Z= 16868/55

Таким образом необходимо выпустить 41 единицу первого продукта и 29 единиц второго продукта, чтобы получить max Z=41*2+29*8=307ден.ед.