Главная » 2013 » Февраль » 18 » Симплекс метод линейного программирования
19:58
Симплекс метод линейного программирования

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

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

x1+2x2≤80

1.5x1+x2≤40

1x1 + 2x2 + 1x3 + 0x4 = 80

1.5x1 + 1x2 + 0x3 + 1x4 = 40

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

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

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

x3, x4,

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

X1 = (0,0,80,40)

 

Базис

В

x1

x2

x3

x4

x3

80

1

2

1

0

x4

40

1.5

1

0

1

F(X0)

0

-7

-3

0

0

 

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

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

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

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

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

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

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

 

Базис

В

x1

x2

x3

x4

min

x3

80

1

2

1

0

80

x4

40

1.5

1

0

1

26.67

F(X1)

0

-7

-3

0

0

0

 

 

После преобразований получаем новую таблицу:

 

Базис

В

x1

x2

x3

x4

x3

53.33

0

1.33

1

-0.67

x1

26.67

1

0.67

0

0.67

F(X1)

186.67

0

1.67

0

4.67

 

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

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

 

Базис

В

x1

x2

x3

x4

x3

53.33

0

1.33

1

-0.67

x1

26.67

1

0.67

0

0.67

F(X2)

186.67

0

1.67

0

4.67

 

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

x3 = 53.33

x1 = 26.67

F(X) = 7*26.67 = 186.67

Поможем с решением ваших задач и контрольных!


Категория: Линейное программирование | Просмотров: 35 | Добавил: Admin | Теги: Линейное программирование | Рейтинг: 0.0
Всего комментариев: 0
Имя *:
Email:
Код *: