Симплекс метод - пример решения.

Ниже приведено условие  и решение задачи. Закачка решения в формате doc  начнется автоматически через 10 секунд.

Z = -X1 + 8X2     max(min)

X1 – 2X2 -2,

-2X1 + 3X26

2X1 + 4X2 0,

X2≥0

Решение

Вместо переменной Х1 произвольного знака вводим переменные Х1 и X1’’.

X1 = Х1 - X1’’.

Запишем систему неравенств в виде:

    (Х1 - X1’’)2Х2  ≤ -2

-2(Х1 - X1’’) + 3Х2  ≤ 6                                        

                                                     2(Х1 - X1’’) + 4Х2   0

Получим:

  Х1 -    X1’’-    2  ≤ -2

                                                -2Х1 + 2X1’’+ 3Х2  ≤ 6                                         (1)

                                                      2Х1 -   2X1’’ +4Х2  ≤ 0

Условие положительности:

Х10, X1’’0, X2≥0.                                                          (2)

Целевая функция:

F = -(Х1 - X1’’) + 8X2 = -Х1 + X1’’ + 8X2    (max)                                                     (3)

Задача записана в симметричной фоме записи. Приведем задачу к канонической форме записи, для этого введем дополнительные переменные Х3, Х4, Х5. Расширенная система задачи имеет вид:

    Х1 -    X1’’-    2Х2  3  = -2

-2Х1 + 2X1’’+ 3Х2  4 = 6

1 -   2X1’’ + 4Х2 +Х5 = 0

Условия неотрицательности примут вид:

Xj≥0 (j=1,..,5).

Заполним первую симплексную таблицу (Табл. 1), в которой переменные X3, X4, X5 являются базисными, переменные Х1, X1’’, X2 свободными. Последняя строка заполняется коэффициентами целевой функции с противоположным знаком.

Таблица 1. Первая (начальная) симплексная таблица

 

Базис

C

Свободный член

Переменные

Оценочное отношение

X1'

X1''

X2

X3

X4

X5

-1

1

8

0

0

0

X3=

0

-2

1

-1

-2

1

0

0

1

X4=

0

6

-2

2

3

0

1

0

2

X5=

0

0

2

-2

4

0

0

1

0

F

0

1

-1

-8

0

0

0

 

 

В результате симплексного преобразования, получим вторую симплексную таблицу (Табл.2).

 

 

 

 

 

 

Таблица 2. Вторая симплексная таблица

Базис

C

Свободный член

Переменные

Оценочное отношение

X1'

X1''

X5

X3

X4

X5

-1

1

8

0

0

0

X3=

0

-2

2

-2

0

1

0

0,5

1

X4=

0

6

-3,5

3,5

0

0

1

-0,75

1,7142857

X2=

8

0

0,5

-0,5

1

0

0

0,25

0

F

0

5

-5

0

0

0

2

 

Таблица 3. Третья симплексная таблица

Базис

C

Свободный член

Переменные

Оценочное отношение

X1'

X1''

X5

X3

X4

X5

-1

1

8

0

0

0

X1''=

1

1

-1

1

0

-0,5

0

-0,25

-2

X4=

0

2,5

0

0

0

1,75

1

0,125

1,4285714

X2=

8

0,5

0

0

1

-0,25

0

0,125

-2

F

5

0

0

0

-2,5

0

0,75

 

Таблица 4. Четвертая симплексная таблица

Базис

C

Свободный член

Переменные

Оценочное отношение

X1'

X1''

X5

X3

X4

X5

-1

1

8

0

0

0

X1''=

1

1,714286

-1

1

0

0

0,28571

-0,2143

 

X3=

0

1,428571

0

0

0

1

0,57143

0,07143

 

X2=

8

0,857143

0

0

1

0

0,14286

0,14286

 

F

8,571429

0

0

0

0

1,42857

0,92857

 

 

В последней строке все элементы неотрицательные, критерий оптимальности выполнен, значит опорный план (0; 1,714; 0,857; 1,423; 0; 0) является опти­мальным, а соответствующее ему значение 8,571 целевой функции будет макси­мальным. Х1 = - 1,714.

Мы получили такое же решение, что и графическим методом.

Найдем минимальное значение целевой функции. Для этого целевую функцию запишем в виде:

-F = Х1 - X1’’ - 8X2    (max)

Первая симплексная таблица запишется в виде табл. 5. В таблице 5 в столбце свободных членов есть отрицательный элемент, следовательно, план не является опорным.

Таблица 5.

Базис

C

Свободный член

Переменные

Оценочное отношение

X1'

X1''

X2

X3

X4

X5

1

-1

-8

0

0

0

X3=

0

-2

1

-1

-2

1

0

0

-2

X4=

0

6

-2

2

3

0

1

0

-3

X5=

0

0

2

-2

4

0

0

1

0

-F

0

-1

1

8

0

0

0

 

 

 

 

Переходим ко второй симплексной таблице.

Таблица 6.

Базис

C

Свободный член

Переменные

Оценочное отношение

X1'

X1''

X2

X3

X4

X5

1

-1

-8

0

0

0

X3=

0

-2

0

0

-4

1

0

-0,5

 

X4=

0

6

0

0

7

0

1

1

 

X1'=

1

0

1

-1

2

0

0

0,5

 

-F

0

0

0

10

0

0

0,5

 

Таблица 7.

Базис

C

Свободный член

Переменные

Оценочное отношение

X1'

X1''

X2

X3

X4

X5

1

-1

-8

0

0

0

X2=

-8

0,5

0

0

1

-0,25

0

0,125

 

X4=

0

2,5

0

0

0

1,75

1

0,125

 

X1'=

1

-1

1

-1

0

0,5

0

0,25

 

-F

-5

0

0

0

2,5

0

-0,75

 

Таблица 8.

Базис

C

Свободный член

Переменные

Оценочное отношение

X1'

 

Имя файла: mathprog13.doc

Размер файла: 163.5 Kb

Если закачивание файла не начнется через 10 сек, кликните по этой ссылке