Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

MATMEDECONOM (1)

.rtf
Скачиваний:
6
Добавлен:
14.06.2017
Размер:
69.18 Кб
Скачать

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

Определим максимальное значение целевой функции F(X) = 4x1 + 5x2 при следующих условиях-ограничений.

- x1 + 2x2≤10

3x1 + 5x2≤47

4x1 - 3x2≤24

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.

-1x1 + 2x2 + 1x3 + 0x4 + 0x5 = 10

3x1 + 5x2 + 0x3 + 1x4 + 0x5 = 47

4x1-3x2 + 0x3 + 0x4 + 1x5 = 24

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Решим систему уравнений относительно базисных переменных:

x3, x4, x5,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,10,47,24)

Базис

B

x1

x2

x3

x4

x5

x3

10

-1

2

1

0

0

x4

47

3

5

0

1

0

x5

24

4

-3

0

0

1

F(X0)

0

-4

-5

0

0

0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai2

и из них выберем наименьшее:

min (10 : 2 , 47 : 5 , - ) = 5

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.

Базис

B

x1

x2

x3

x4

x5

min

x3

10

-1

2

1

0

0

5

x4

47

3

5

0

1

0

92/5

x5

24

4

-3

0

0

1

-

F(X1)

0

-4

-5

0

0

0

0

Получаем новую симплекс-таблицу:

Базис

B

x1

x2

x3

x4

x5

x2

5

-1/2

1

1/2

0

0

x4

22

51/2

0

-21/2

1

0

x5

39

21/2

0

11/2

0

1

F(X1)

25

-61/2

0

21/2

0

0

Итерация №1.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai1

и из них выберем наименьшее:

min (- , 22 : 51/2 , 39 : 21/2 ) = 4

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (51/2) и находится на пересечении ведущего столбца и ведущей строки.

Базис

B

x1

x2

x3

x4

x5

min

x2

5

-1/2

1

1/2

0

0

-

x4

22

51/2

0

-21/2

1

0

4

x5

39

21/2

0

11/2

0

1

153/5

F(X2)

25

-61/2

0

21/2

0

0

0

Получаем новую симплекс-таблицу:

Базис

B

x1

x2

x3

x4

x5

x2

7

0

1

3/11

1/11

0

x1

4

1

0

-5/11

2/11

0

x5

29

0

0

27/11

-5/11

1

F(X2)

51

0

0

-5/11

12/11

0

Итерация №2.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai3

и из них выберем наименьшее:

min (7 : 3/11 , - , 29 : 27/11 ) = 11

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (27/11) и находится на пересечении ведущего столбца и ведущей строки.

Базис

B

x1

x2

x3

x4

x5

min

x2

7

0

1

3/11

1/11

0

252/3

x1

4

1

0

-5/11

2/11

0

-

x5

29

0

0

27/11

-5/11

1

11

F(X3)

51

0

0

-5/11

12/11

0

0

Получаем новую симплекс-таблицу:

Базис

B

x1

x2

x3

x4

x5

x2

4

0

1

0

4/29

-3/29

x1

9

1

0

0

3/29

5/29

x3

11

0

0

1

-5/29

11/29

F(X3)

56

0

0

0

13/29

5/29

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

Окончательный вариант симплекс-таблицы:

Базис

B

x1

x2

x3

x4

x5

x2

4

0

1

0

4/29

-3/29

x1

9

1

0

0

3/29

5/29

x3

11

0

0

1

-5/29

11/29

F(X4)

56

0

0

0

13/29

5/29

Оптимальный план можно записать так:

x2 = 4

x1 = 9

x3 = 11

F(X) = 5•4 + 4•9 + 0•11 = 56

Решение было получено и оформлено с помощью сервиса:

Симплекс-метод

Вместе с этой задачей решают также:

Графический метод решения задач линейного программирования

Двойственный симплекс-метод

Двойственная задача линейного программирования

Метод Гомори

Транспортная задача

Соседние файлы в предмете Математические методы в экономике