logo

Решение контрольных по математике!!!

15. Решение задач

Вернемся к решению задачи из примера в начале темы. Для задачи (3.51)–(3.53) запишем ВЗ:

-(U1+U2+U3) Max (3.84)

2X1 + 2X3 + 4X4 + X5 + U1 = 150

X1 + X2 + 2X5 + U2 = 200 (3.85)

X1 + X3 + 2X6 + U3 = 300

Xj ≥ 0; Ui ≥ 0; j = ; I = . (3.86)

Результаты первого этапа представлены в табл. 3.5.

Таблица 3.5

0

0

0

0

0

0

-1

-1

-1

S

I

1

7

-1

150

0

2

2

4

1

0

1

0

0

37,5

0

2

8

-1

200

1

1

0

0

2

0

0

1

0

-

3

9

-1

300

1

0

1

0

0

2

0

0

1

-

4

-650

-2

-3

-3

-4

-3

-2

0

0

0

1

4

0

37,5

0

0,5

0,5

1

0,25

0

0,25

0

0

-

150

-

1

2

8

-1

200

1

1

0

0

2

0

0

1

0

200

100

-

3

9

-1

300

1

0

1

0

0

2

0

0

1

300

-

150

4

-500

-2

-1

-1

0

-2

-2

1

0

0

1

4

0

37,5

0

0,5

0,5

1

0,25

0

0,25

0

0

-

2

2

1

0

200

1

1

0

0

2

0

0

1

0

-

3

9

-1

100

0

-1

1

0

-2

2

0

-1

1

50

4

-100

0

1

-1

0

2

-2

1

2

0

1

4

0

37,5

0

0,5

0,5

1

0,25

0

0,25

0

0

3

2

1

0

200

1

1

0

0

2

0

0

1

0

3

6

0

50

0

-0,5

0,5

0

-1

1

0

-0,5

0,5

4

0

0

0

0

0

0

0

1

1

1

На третьей итерации симплексного метода получен оптимальный план вспомогательной задачи: = (200; 0; 0; 37.5; 0; 50; 0; 0; 0), в котором ни одна из искусственных переменных не является базисной, следовательно, вектор = (200; 0; 0; 37.5; 0; 50) является невырожденным опорным планом исходной задачи, определяемым К-матрицей.

На втором этапе решаем задачу

max (–0,4X1–0,3X2–0,1X3–0,1X5–0,2X6)

.

Решение приведено в табл. 3.6.

Таблица 3.6

-0.4

-0.3

-0.1

0

-0.1

-0.2

S

I

1

4

0

37,5

0

0,5

0,5

1

0,25

0

150

0

2

1

-0,4

200

1

1

0

0

2

0

100

3

6

-0,2

50

0

-0,5

0,5

0

-1

1

-

4

-90

0

0

0

0

-0,5

0

1

4

0

12,5

-0,125

0,375

0,5

1

0

0

25

1

2

5

-0,1

100

0,5

0,5

0

0

1

0

-

3

6

-0,2

150

1

0

1

0

0

1

300

4

-40

0,25

0,25

0

0

0

0

1

3

-0,1

25

-0,25

0,75

1

2

0

0

2

2

5

-0,1

100

0,5

1

0

0

1

0

3

6

-0,2

137,5

0,625

-0,375

0

-1

0

1

4

-100

0,25

0,25

0

0

0

0

На первой итерации (табл. 3.6) второго этапа получен оптимальный план исходной задачи 1 = (0; 0; 12.5; 100; 150) и = 40.

Так как = 0, а вектор не является базисным, то его можно ввести в базис, и при этом в соответствии с формулой (3.28) значение целевой функции не изменится, т. е. на второй итерации можно получить еще один оптимальный план исходной задачи

2 = (0; 0,25; 0; 100; 137,5) и = 40.

Исходная задача имеет бесчисленное множество решений, задаваемое формулой

(3.87)

Пример 3.15. Решить ЗЛП:

max (2X1 – X2 – X4)

X1 – 2X2 + X3 = 10

–2X1 – X2 – 2X4 18 (3.88)

3X1 + 2X2 + X4 36

Приведем ЗЛП (3.88) к каноническому виду

max (2X1 – X2 – X4)

X1 – 2X2 + X3 = 10

-2X1 – X2 – 2X4 – S1 =18 (3.89)

3X1 + 2X2 + X4-S2 = 36

Расширенная матрица системы линейных уравнений (3.89)

Не является К-матрицей ЗЛП (3.89) , т. к. не содержит единичной подматрицы.

Запишем вспомогательную задачу для ЗЛП (3.89). Т. к. матрица Содержит один единичный вектор = (1; 0; 0), то при формулировке ВЗ достаточно ввести лишь две искусственные переменные U1; U2 во второе и третье уравнения системы (3.89).

Итак, ВЗ имеет вид

-(U1+U2) Max

X1 – 2X2 + X3 = 10

-2X1 – X2 – 2X4 – X5 + U1 = 18 (3.90)

3X1 + 2X2 + X4 – X6 + U2 = 36

; U1 ,U2 0

Решение ВЗ приведено в табл. 3.7.

Таблица 3.7

0

0

0

0

0

0

-1

-1

S

I

1

3

0

10

-1

-2

1

0

0

0

0

0

-

0

2

7

-1

18

-2

-1

0

-2

-1

0

1

0

-

3

8

-1

36

3

2

0

1

0

-1

0

1

18

4

-54

-1

-1

0

1

1

1

0

0

1

3

0

46

2

0

1

1

0

-1

0

1

1

2

7

-1

36

-0,5

0

0

-1,5

-1

-0,5

1

0,5

3

2

0

18

1,5

1

0

0,5

0

-0,5

0

0,5

4

-36

0,5

0

0

1,5

1

0,5

0

0,5

На первой итерации получен оптимальный план.

= (0; 18; 46; 0; 0; 36; 0).

Т. к. вектор имеет отличную от нуля искусственную переменную U1 = 36, то множество планов ЗЛП (3.88) пусто в силу несовместности системы уравнений (3.89).

 
Яндекс.Метрика
Наверх