«Методы оптимальных решений»

3.3.

Задача 4.

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

4.3.

ЗАДАЧА 5

Решить симплекс-методом следующие задачи.

ЗАДАЧА 6

В каждой из указанных задач требуется:

а) составить двойственную задачу;

б) проверить взаимность двойственной пары;

в) решив исходную задачу симплексным методом, найти из таблицы решение двойственной задачи;

Z= -X1 +X2 -X3 +X4max

X1+2X2 -X3+3X4 =6

X2+2X3 -X4 =4

2X1 +X3 +X4 =6

Xj0, (j=1,2,3,4)

Δ = 322231113

∆ = 3*(3*3 - 1*1) - 2*(2*3 - 1*2) + 1*(2*1 - 3*2) = 12

Определитель матрицы равен ∆ =12

Разложим а4 = α1а1 + α2а2 + α3а3

Запишем данное равенство в координатной форме:

(5;1;11) = α(3;2;2) + α(2;3;1) + α(1;1;3)

Используя свойства векторов, получим следующее равенство:

(5;1;11) = (3α1;2α1;2α1;) + (2α2;3α2;1α2;) + (1α3;1α3;3α3;)

(5;1;11) = (3α1 + 2α2 + 1α3;2α1 + 3α2 + 1α3;2α1 + 1α2 + 3α3)

По свойству равенства векторов имеем:

3α1 + 2α2 + 1α3 = 5

2α1 + 3α2 + 1α3 = 1

2α1 + 1α2 + 3α3 = 11

Решаем полученную систему уравнений методом Крамера

5 2 1

Δ1= 1 3 1

11 1 3

3 5 1

Δ2 = 2 1 1

2 11 3

3 2 5

Δ3 = 2 3 1

2 1 11

решим методом Крамера

=> вычислим сначала определители

Δ1=24, Δ2= -24, Δ3=36

α1 = Δ1/ Δ=24/12=2

α2 = Δ2/ Δ=-24/12=-2

α3= Δ3/ Δ=36/12=3

а4 = 2-23

а4 = 2а1 -2а2 + 3а3 .

Следующий базис выберем

Векторы линейно независимы и образуют базис, т.к. определитель, составленный из координат этих векторов, отличен от нуля:

Второе ограничение имеет вид 1х1 + 4х2 ≤ 10. Находим пересечение с осями координат. Прямая 1х1 + 4х2 = 10 проходит через точки (10;0) и (0; 5/2).

Решением этих неравенств системы является полуплоскость ABCD

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

Построим вектор-градиент

Начало вектора совпадает с началом координат. Построим линию уравнения, перпендикулярную вектору – градиента: 3x1 + 4x2 = 0. При максимизации функции движемся в направлении вектора-градиента.