Реферат: Задание: Найти, при заданных ограничениях

ПРИМЕР РЕШЕНИЯ ЗАДАЧИ ПО ИССЛЕДОВАНИЮ ОПЕРАЦИЙ (СИМПЛЕКС-МЕТОД) (ВАРИАНТ №4)


Задание: Найти , при заданных ограничениях:



Т.к. в третьем уравнении имеется знак , то введем искусственную переменную х6 и перейдём к задаче максимизации (поменяем знак целевой функции), при этом в целевую ф-цию войдёт искусственная переменная х6 с отрицательным знаком и коэффициентом М (М >>1).

.

Приведём ограничения к расширенной форме:



Из системы ограничений выберем базис, который составят переменные х3, х4, х6, т.к. они образуют единичную матрицу:



Базис:

Составим симплекс-таблицу:

С







с1 = -2

с2 = -1

с3 = 0

с4 = 0

с5 = 0

с6 = -М




ХР

В

А1

А2

А3

А4

А5

А6

с3 = 0

х3

12

3

-2

1

0

0

0

с4 = 0

х4

8

-1

2

0

1

0

0

с6 = -М

х6

6

2

3

0

0

-1

1

S











0

0

-М

0


Определим симплекс-разности:













Т.к. М довольно большое число, то максимальной положительной симплекс-разностью будет являться S2 = -1 + 3М. Столбец, в котором эта разность находится назовем направляющим. Для того чтобы определить направляющую строку найдём:

(т.к. 6/3=2 - минимальное положительное число)

Следовательно, 3-я строка будет направляющей. Направляющий элемент будет направляющим, так как он находится на пересечении направляющей строки и направляющего столбца.

Теперь удаляем из базиса переменную х6 (соответственно направляющей строке) и вводим переменную х2 (соответственно направляющему столбцу).

Заполним новую таблицу, соответствующую новому базисному решению. Для этого в начале все элементы направляющей строки делим на направляющий элемент:





Элементы направляющего столбца (кроме направляющего элемента) будут равны нулю:

.

Остальные элементы рассчитываются согласно мнемоническому правилу:

Пусть направляющий элемент , тогда:

;

.

Т.е. из произведения элементов, стоящих по одной диагонали прямоугольника (), вычесть произведение элементов, стоящих по другую диагональ (), и полученную разность разделить на направляющий элемент.


Согласно вышеуказанной формуле получим:

;

;

;

;

;

;

;

;

;

;

;

.

Получим новую таблицу:

С







с1 = -2

с2 = -1

с3 = 0

с4 = 0

с5 = 0

с6 = -М




ХР

В

А1

А2

А3

А4

А5

А6

с3 = 0

х3

16

13/3

0

1

0

-2/3

2/3

с4 = 0

х4

4

-7/3

0

0

1

2/3

-2/3

с2 = -1

х2

2

2/3

1

0

0

-1/3

1/3

S









0

0

0

-1/3




Определим симплекс-разности:













Все симплекс-разности отрицательны, следовательно, найденное решение является оптимальным.


Оптимальное решение: .

.