1.2. Решение злп графическим методом:

F(A) = 2 F(D) = -6

F(B) = 5  max F(E) = -1

F(C) = -8

Находим оптимальное решение графически: двигаемся по направлению градиента, пока не выйдем из области, ограниченной неравенствами (симплекса). Оптимальное решение: (5;2), F (5,2) = -2 * 5 + 2 = - 8

Значение целевой функции: - 8.

1.3. Решение злп алгебраическим методом:

Ограничения – неравенства Ограничения – равенства

-3x1 - 5x2 + 25 0 - 3x1 – 5x2 + 25 = x3

-2x1 + 2x2 + 6 0 - 2x1 + 2x2 + 6 = x4

x1 + 2x2 – 3 0 x1 + 2x2 – 3 = x5 x1 + x2 – 2 0 x1 + x2 – 2 = x6

xi 0

F = - 2x1 + x2  min Свободные х₁, х₂

< 0, 0, 25, 6,- 3, - 2 >

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

F = - 2x1 + x2  min

Для приведения данного решения к допустимому выведем переменную x5 из базиса и заменим её на x1.

Заменим x1 на x3

x1 = x5 -2x2 +3

С вободные х₂ ,х₅

x3 = -3x5 + 6x2 – 5x2 - 9 + 25

x4= -2(x5 – 2x2 + 3) + x2 + 6

x1 = x5 – 2x2 + 3

x6 = x5 – 2x2 + 3 + x2 – 2

x3 = -3x5 + x2 +16  16/3

x4= - 2x5 + 6x2  0

x1 = x5 – 2x2 + 3  ∞ (1)

x6 = x5 – x2 + 1  ∞

F = -2(x5 – 2x2 + 3) + x2 = - 2x5 + 4x2 – 6 + x2 = - 2x5 + 5x2 – 6

< 3, 0, 16, 0, 0, 1 >

Допустимое (1) , может быть опорным

F = - 2x5 + 5x2 – 6  min

Решение не является оптимальным, так как коэффициент при х₅ отрицателен. Переведём переменную х₅ в свободные. Заменим х₅ на х₄

x5 =1/2 x4 + 3x2

С вободные х₄ ,х₂

x3 = -3(-1/2 x4 + 3x2) + x2 + 16

x5= - 1/2 x4 + 3x2

x1 = - 1/2 x4 + 3x2 – 2x2 + 3

x6 = - 1/2 x4 + 3x2 – x2 + 1

x3 = 3/2 x4 – 8x2 + 16 2

x5= - 1/2 x4 + 3x2  ∞

x1 = - 1/2 x4 + x2 + 3  ∞

x6 = - 1/2 x4 + 2x2 + 1  ∞

F = -2(- 1/2 x4 + 3x2) + 5x2 - 6= x4 – x2 – 6

< 3, 0, 16, 0, 0, 1 >

Решение не является оптимальным, так как коэффициент при х₂ отрицателен. Переведём переменную х₂ в свободные. Заменим х₂ на х₃

x2 = 3/16 x4 – 1/8 x3 + 2

С вободные х₄ ,х₂

x2 = 3/16 x4 – 1/8 x3 + 2

x5= - 1/2 x4 + 3(3/16 x4 – 1/8 x3 + 2)

x1 = - 1/2 x4 + 3/16 x4 – 1/8 x3 + 2 + 3

x6 = - 1/2 x4 + 2(3/16 x4 – 1/8 x3 + 2) + 1

x2 = 3/16 x4 – 1/8 x3 + 2

x5= - 1/16 x4 – 1/8 x3 + 6

x1 = - 5/16 x4 – 1/8 x3 + 5

x6 = - 1/2 x4 – 1/4 x2 + 5

F = x4 – 3/16 x4 + 1/8 x3 – 2 – 6 = 13/16 x4 + 1/8 x3 – 8

< 5, 2, 0, 0, 6, 5 >

F =13/16 x4 + 1/8 x3 – 8 – все коэффициенты положительны, решение оптимальное в точке (5;2), значение исходной целевой функции - 8.

1.4. Решение злп симплекс – методом:

Д ля решения симплекс методом воспользуемся опорным решением (1), полученным ранее.

x3 = -3x5 + x2 +16

x4= - 2x5 + 6x2

x1 = x5 – 2x2 + 3 (1)

x6 = x5 – x2 + 1

F = - 2x5 + 5x2 – 6  min

Преобразуем систему для решения симплекс – методом

x 3 = 16 - (3x5 - x2)

x4= 0 - (2x5 - 6x2)

x1 = 3 - (-x5 + 2x2) (1)

x6 = 1 - (-x5 + x2)

F = - 6 – ( 2x5 – 5x2)  min

Таблица 1. Симплекс – таблица

Б\Св	β		x5		x2
x3	16	0	3	-3/2	-1	9
x4	0	0	2	1/2	-6	-3
x1	3	0	-1	1/2	2	-3
x6	1	0	-1	1/2	1	-3
F	-6	0	2	-1	-5	6

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

16/3 –допустимое значение, но не минимальное

0 – допустимое, минимальное

-3 – недопустимое значение (отрицательное)

- 1 – недопустимое значение (отрицательное)

Минимальным из допустимых значений является значение, соответствующее 0 поэтому генеральным элементом является элемент а₂₂ (соответствует сроке х₄), тогда соответственно λ = 1/ а₂₂ = 1/2. На основании этого производим вычисления.

После вычисление получаем:

Таблица2.

Б\Св	β		x4		x2
x3	16	2	-3/2	-3/16	8	1/8
x5	0	6	1/2	-9/16	-3	3/8
x1	3	2	1/2	-3/16	-1	1/8
x6	1	4	1/2	-3/8	-2	1/4
F	-6	-2	-1	3/16	1	-1/8

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

2– допустимое, минимальное

0 – допустимое, но коэффициент x5 - отрицательный

-3 – недопустимое значение (отрицательное)

-1 – недопустимое значение (отрицательное)

Минимальным из допустимых значений является значение, соответствующее 2 поэтому генеральным элементом является элемент а₂₃ (соответствует сроке х₅), тогда соответственно λ = 1/ а₁₃ = 1/8. На основании этого производим вычисления.

После вычисление получаем:

Таблица3.

Б\Св	β	x4	x3
x2	2	-3/16	1/8
x5	6	1/16	3/8
x1	5	5/16	1/8
x6	5	1/2	1/4
F	-8	-13/16	-1/8

Так как все коэффициенты целевой функции отрицательны, то решение оптимальное и в точке (5;2). Значение целевой функции – 8 .

< 5, 2, 0, 0, 6, 5>

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