Симплексный метод решения задач ЛП - Решение оптимизационных экономических задач методами линейного программирования

Вид сырья

Запас сырья

Количество единиц сырья, идущих на изготовление единицы продукции

P1

P2

P3

P4

S1

4

1

1

1

3

S2

18

2

4

6

1

Прибыль от единицы продукции

9

14

15

5

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

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

X1 + x2 + x3 + x4?4

2x1 + 4x2 + 6x3 + x4?18

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

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

    1x1 + 1x2 + 1x3 + 1x4 + 1x5 + 0x6 = 4 2x1 + 4x2 + 6x3 + 1x4 + 0x5 + 1x6 = 18

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

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

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

X5, x6,

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

X1 = (0,0,0,0,4,18)

Базисное решение называется допустимым, если оно неотрицательно.

Базис

B

X1

X2

X3

X4

X5

X6

X5

4

1

1

1

1

1

0

X6

18

2

4

6

1

0

1

F(X0)

0

-9

-14

-15

-5

0

0

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

Итерация №0.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения DI по строкам как частное от деления: bI / aI3

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

Min (4 : 1 , 18 : 6 ) = 3

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

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

Базис

B

X1

X2

X3

X4

X5

X6

Min

X5

4

1

1

1

1

1

0

4

X6

18

2

4

6

1

0

1

3

F(X1)

0

-9

-14

-15

-5

0

0

0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x в план 1 войдет переменная x3 .

Строка, соответствующая переменной x3 В плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=6

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x3 Плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x3 И столбец x3 .

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (6), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B

X 1

X 2

X 3

X 4

X 5

X 6

4-(18 * 1):6

1-(2 * 1):6

1-(4 * 1):6

1-(6 * 1):6

1-(1 * 1):6

1-(0 * 1):6

0-(1 * 1):6

18 : 6

2 : 6

4 : 6

6 : 6

1 : 6

0 : 6

1 : 6

0-(18 * -15):6

-9-(2 * -15):6

-14-(4 * -15):6

-15-(6 * -15):6

-5-(1 * -15):6

0-(0 * -15):6

0-(1 * -15):6

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

Базис

B

X1

X2

X3

X4

X5

X6

X5

1

2/3

1/3

0

5/6

1

-1/6

X3

3

1/3

2/3

1

1/6

0

1/6

F(X1)

45

-4

-4

0

-21/2

0

21/2

Итерация №1.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения DI по строкам как частное от деления: bI / aI2

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

Min (1 : 1/3 , 3 : 2/3 ) = 3

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

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

Базис

B

X1

X2

X3

X4

X5

X6

Min

X5

1

2/3

1/3

0

5/6

1

-1/6

3

X3

3

1/3

2/3

1

1/6

0

1/6

41/2

F(X2)

45

-4

-4

0

-21/2

0

21/2

0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x в план 2 войдет переменная x2 .

Строка, соответствующая переменной x2 В плане 2, получена в результате деления всех элементов строки x5 плана 1 на разрешающий элемент РЭ=1/3

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x2 Плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x2 И столбец x2 .

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B

X 1

X 2

X 3

X 4

X 5

X 6

1 : 1/3

2/3 : 1/3

1/3 : 1/3

0 : 1/3

5/6 : 1/3

1 : 1/3

-1/6 : 1/3

3-(1 * 2/3):1/3

1/3-(2/3 * 2/3):1/3

2/3-(1/3 * 2/3):1/3

1-(0 * 2/3):1/3

1/6-(5/6 * 2/3):1/3

0-(1 * 2/3):1/3

1/6-(-1/6 * 2/3):1/3

45-(1 * -4):1/3

-4-(2/3 * -4):1/3

-4-(1/3 * -4):1/3

0-(0 * -4):1/3

-21/2-(5/6 * -4):1/3

0-(1 * -4):1/3

21/2-(-1/6 * -4):1/3

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

Базис

B

X1

X2

X3

X4

X5

X6

X2

3

2

1

0

21/2

3

-1/2

X3

1

-1

0

1

-11/2

-2

1/2

F(X2)

57

4

0

0

71/2

12

1/2

1. Проверка критерия оптимальности.

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

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

Базис

B

X1

X2

X3

X4

X5

X6

X2

3

2

1

0

21/2

3

-1/2

X3

1

-1

0

1

-11/2

-2

1/2

F(X3)

57

4

0

0

71/2

12

1/2

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

X2 = 3

X3 = 1

F(X) = 14*3 + 15*1 = 57

Похожие статьи




Симплексный метод решения задач ЛП - Решение оптимизационных экономических задач методами линейного программирования

Предыдущая | Следующая