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

Максимальная прибыль для x₁=46 и x₂=6 находится по формуле:

F _max=11*46+6*6=542 единицы.

 

 

 

 

 

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

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

 

Необходимо найти максимальное значение целевой функции f(x) = x₁+2x₂ → max, при системе ограничений:

-x1+x2≤3	(1)
x1-x2≤0	(2)
x1+2x2≤12	(3)
4x1-x2≥0	(4)

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

1. -x₁+x₂=3

x1	3	1
x2	6	4

2. x₁-x₂=0

x1	1	2
x2	1	2

3. x₁+2x₂=12

x1	0	6
x2	6	3

4. 4x₁-x₂≥0

x1	1	2
x2	4	8

 

или

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

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

 

 

Рассмотрим целевую  функцию задачи F = x₁+2x₂ → max.

Построим прямую, отвечающую значению функции F = 0: F = x₁+2x₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Равный масштаб 

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

Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

x₁-x₂≤0

x₁+2x₂≤12

x1-x2=0	x1=x2	x1=x2	x1=4
x1+2x2=12	x2+2x2=12	3x2=12	x2=4

Решив систему уравнений, получим: x₁ = 4, x₂ = 4.

Откуда найдем максимальное значение целевой функции: 
F(X) = 1*4 + 2*4 = 12

Поскольку функция цели F(x) параллельна прямой (3), то на отрезке DC функция F(x) будет принимает одно и тоже максимальное значение. 
Для определения координат точки C решим систему двух линейных уравнений: 

-x₁+x₂≤3 
x₁+2x₂≤12

-x1+x2=3	-x1=3-x2	x1=3+x2	x1=3+x2	x1=6
x1+2x2=12	x1+2x2=12	3+x2+2x2=12	3x2=9	x2=3

 

Решив систему уравнений, получим: x₁ = 6, x₂ = 3.

Откуда найдем максимальное значение целевой функции: 
F(X) = 1*2 + 2*5 = 12

 

 

 

 

 

 

 

 

 

 

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

 

Определим максимальное значение целевой функции F(X) = - x₁ - x₂ - 2x₃ при следующих условиях-ограничений.

 
x₁ - x₂ - x₃≥1 
- 2x₁ + 3x₂≥1 
- 3x₁ + x₂ - 2x₃<=1

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

 
1x₁-1x₂-1x₃-1x₄ + 0x₅ + 0x₆ = 1 
-2x₁ + 3x₂ + 0x₃ + 0x₄-1x₅ + 0x₆ = 1 
-3x₁ + 1x₂-2x₃ + 0x₄ + 0x₅ + 1x₆ = 1

 
Введем искусственные переменные x: в 1-м равенстве вводим переменную x₇; в 2-м равенстве вводим переменную x₈;

 
1x₁-1x₂-1x₃-1x₄ + 0x₅ + 0x₆ + 1x₇ + 0x₈ = 1 
-2x₁ + 3x₂ + 0x₃ + 0x₄-1x₅ + 0x₆ + 0x₇ + 1x₈ = 1 
-3x₁ + 1x₂-2x₃ + 0x₄ + 0x₅ + 1x₆ + 0x₇ + 0x₈ = 1

 
Для постановки задачи на максимум целевую функцию запишем так:

 
F(X) = -1x₁-1x₂-2x₃ - Mx₇ - Mx₈ → max

Из уравнений выражаем искусственные переменные:

 
x₇ = 1-x₁+x₂+x₃+x₄ 
x₈ = 1+2x₁-3x₂+x₅

 
которые подставим в целевую функцию: 
F(X) = (-1-M)x₁+(-1+2M)x₂+(-2-M)x₃+(-M)x₄+(-M)x₅+(-2M) → max

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

1	-1	-1	-1	0	0	1	0
-2	3	0	0	-1	0	0	1
-3	1	-2	0	0	1	0	0

 

Решим систему уравнений  относительно базисных переменных: 
x₇, x₈, x₆,

Полагая, что свободные переменные равны 0, получим первый опорный план: 
X1 = (0,0,0,0,0,1,1,1)

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x7	1	1	-1	-1	-1	0	0	1	0
x8	1	-2	3	0	0	-1	0	0	1
x6	1	-3	1	-2	0	0	1	0	0
F(X0)	-2M	1+M	1-2M	2+M	M	M	0	0	0

 
Переходим к основному алгоритму  симплекс-метода.

Итерация №0.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем  столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2 
и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент  равен (3) и находится на пересечении  ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x7	1	1	-1	-1	-1	0	0	1	0	-
x8	1	-2	3	0	0	-1	0	0	1
x6	1	-3	1	-2	0	0	1	0	0	1
F(X1)	-2M	1+M	1-2M	2+M	M	M	0	0	0	0

 
Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x7	11/3	1/3	0	-1	-1	-1/3	0	1	1/3
x2	1/3	-2/3	1	0	0	-1/3	0	0	1/3
x6	2/3	-21/3	0	-2	0	1/3	1	0	-1/3
F(X1)	-1/3-11/3M	12/3-M	0	2+M	M	1/3+M	0	0	-1/3+2/3M

 

Итерация №1.

Текущий опорный план неоптимален, так как в индексной  строке находятся отрицательные коэффициенты.

В качестве ведущего выберем  столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 
и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент  равен (¹/₃) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x7	11/3	0	-1	-1	-1/3	0	1	1/3	4
x2	1/3	-2/3	1	0	0	-1/3	0	0	1/3	-
x6	2/3	-21/3	0	-2	0	1/3	1	0	-1/3	-
F(X2)	-1/3-11/3M	12/3-M	0	2+M	M	1/3+M	0	0	-1/3+2/3M	0

 
Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x1	4	1	0	-3	-3	-1	0	3	1
x2	3	0	1	-2	-2	-1	0	2	1
x6	10	0	0	-9	-7	-2	1	7	2
F(X2)	-7	0	0	7	5	2	0	-5+M	-2+M