Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Решим прямую задачу линейного программирования симплексным методом, с использованием - страница №1/1

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

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

4x1 + 3x2≤24

- x1 + x2≤3

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

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

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

-1x1 + 1x2 + 0x3 + 1x4 = 3

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим систему уравнений относительно базисных переменных:

x3, x4,

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

X1 = (0,0,24,3)



Базис

B

x1

x2

x3

x4

x3

24

4

3

1

0

x4

3

-1

1

0

1

F(X0)

0

-1

-2

0

0

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



Итерация №0.

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

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

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

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

min (24 : 3 , 3 : 1 ) = 3

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

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



Базис

B

x1

x2

x3

x4

min

x3

24

4

3

1

0

8

x4

3

-1

1

0

1

3

F(X1)

0

-1

-2

0

0

0

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



Базис

B

x1

x2

x3

x4

x3

15

7

0

1

-3

x2

3

-1

1

0

1

F(X1)

6

-3

0

0

2


Итерация №1.

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

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

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

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

min (15 : 7 , - ) = 21/7

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

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



Базис

B

x1

x2

x3

x4

min

x3

15

7

0

1

-3

21/7

x2

3

-1

1

0

1

-

F(X2)

6

-3

0

0

2

0

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



Базис

B

x1

x2

x3

x4

x1

21/7

1

0

1/7

-3/7

x2

51/7

0

1

1/7

4/7

F(X2)

123/7

0

0

3/7

5/7

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

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


Базис

B

x1

x2

x3

x4

x1

21/7

1

0

1/7

-3/7

x2

51/7

0

1

1/7

4/7

F(X3)

123/7

0

0

3/7

5/7

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

x1 = 21/7

x2 = 51/7

F(X) = 1•21/7 + 2•51/7 = 123/7

В полученном оптимальном плане присутствуют дробные числа.

По 3-у уравнению с переменной x, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 3/7, составляем дополнительное ограничение:

q3 - q31•x1 - q32•x2 - q33•x3 - q34•x4≤0

q3 = b3 - [b3] = 123/7 - 12 = 3/7

q31 = a31 - [a31] = 0 - 0 = 0

q32 = a32 - [a32] = 0 - 0 = 0

q33 = a33 - [a33] = 3/7 - 0 = 3/7

q34 = a34 - [a34] = 5/7 - 0 = 5/7

Дополнительное ограничение имеет вид:



3/7-3/7x3-5/7x4≤0

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



3/7-3/7x3-5/7x4 + x5 = 0

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



Базис

B

x1

x2

x3

x4

x5

x1

21/7

1

0

1/7

-3/7

0

x2

51/7

0

1

1/7

4/7

0

x5

-3/7

0

0

-3/7

-5/7

1

F(X0)

-123/7

0

0

-3/7

-5/7

0

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-3/7).


Базис

B

x1

x2

x3

x4

x5

x1

21/7

1

0

1/7

-3/7

0

x2

51/7

0

1

1/7

4/7

0

x5

-3/7

0

0

-3/7

-5/7

1

F(X)

-123/7

0

0

-3/7

-5/7

0

θ

0

-

-

-3/7 : (-3/7) = 1

-5/7 : (-5/7) = 1

-

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.



Базис

B

x1

x2

x3

x4

x5

x1

2

1

0

0

-2/3

1/3

x2

5

0

1

0

1/3

1/3

x3

1

0

0

1

12/3

-21/3

F(X0)

-12

0

0

0

0

-1

Решение получилось целочисленным. Нет необходимости применять метод Гомори.

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

x1 = 2

x2 = 5

x3 = 1

F(X) = 12
Решение было получено и оформлено с помощью сервиса:

Метод Гомори

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



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

Метод ветвей и границ

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

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

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

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