Пример решения двойственной задачи симплексным методом.

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

Z = 2X1 + 6X2 + X3 (min)

 

5X1 + X2 + 4X3 ≥5,

X1 + 3X2 + 7X3 ≥3.

 

X1≥0, X2≥0, X3≥0.

Решение.

Запишем матрицу исходной задачи в виде.

5

1

4

5

1

3

7

3

2

6

1

φ min

Транспонируем составленную матрицу. В результате получим матрицу двойственной задачи:

5

1

2

1

3

6

4

7

1

5

3

f max

По полученной матрице запишем двойственную задачу.

F = 5Y1 + 3Y2  (max)

5Y1 + Y2 ≤ 2,

Y1 + 3Y2 ≤ 6,

4Y1 + 7Y2 ≤1.

 

Y1≥0, Y2≥0.

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

5Y1 + Y2   + Y3  = 2

Y1 + 3Y2  + Y4 = 6

 4Y1 + 7Y2   + Y5 = 1

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

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

Заполним первую симплексную таблицу (Табл. 1), в которой переменные Y3, Y4, Y5 являются базисными, переменные Y1, Y2 свободными. Последняя строка заполняется коэффициентами целевой функции с противоположным знаком.

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

Базис

C

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

Переменные

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

Y1

Y2

Y3

Y4

Y5

5

3

0

0

0

 

Y3=

0

2

5

1

1

0

0

0,4

Y4=

0

6

1

2

0

1

0

6

Y5=

0

1

4

7

0

0

1

0,25

F

0

-5

-3

0

0

0

 

В полученной таблице в F-строке есть отрицательные элементы, следовательно план не является оптимальным. Производим симплексное преобразование с разрешающим элементом 4 и переходим к таблице 2.

 

 

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

Базис

C

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

Переменные

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

Y1

Y2

Y3

Y4

Y5

5

3

0

0

0

 

Y3=

0

0,75

0

-7,75

1

0

-1,25

 

Y4=

0

5,75

0

0,25

0

1

-0,25

 

Y1=

5

0,25

1

1,75

0

0

0,25

 

F

1,25

0

5,75

0

0

1,25

 

Получаем табл. 2. в F-строке которой нет отрицательных элементов.

Следовательно, опорный план (0,25; 0; 0,75; 5,75; 0) является опти­мальным, а соответствующее ему значение 1,25 целевой функции будет макси­мальным.

Запишем соответствия между переменными двойственных задач:

   Y3 X1, Y4 X2, Y5 X3, Y1 X4, Y2 X5.

Используя соответствие между переменными двойственных задач и полученные значения в таблице 2, находим решение двойственной задачи.

X1 = 0; X2 = 0; X3 = 1,25; X4 = 0; X5 = 5,75. Экстремальные значения целевых функций двойственных задач совпадают Fmax = Zmin = 1,25.

 

 

 

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

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

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