Задачи линейного программирования. 3

Вариант № 9

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

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

2x1 + x2 + x3 + 3x4≤300

x1 + 2x3 + x4≤100

x1 + 2x2 + x3≤400

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

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

2x1 + 1x2 + 1x3 + 3x4 + 1x5 + 0x6 + 0x7 = 300

1x1 + 0x2 + 2x3 + 1x4 + 0x5 + 1x6 + 0x7 = 100

1x1 + 2x2 + 1x3 + 0x4 + 0x5 + 0x6 + 1x7 = 400

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

2

1

1

3

1

0

0

1

0

2

1

0

1

0

1

2

1

0

0

0

1


 

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

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

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

x5, x6, x7,

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

X1 = (0,0,0,0,300,100,400)

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

Базис

B

x1

x2

x3

x4

x5

x6

x7

x5

300

2

1

1

3

1

0

0

x6

100

1

0

2

1

0

1

0

x7

400

1

2

1

0

0

0

1

F(X0)

0

-5

-3

-2

-1

0

0

0


 

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

Итерация №0.

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

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

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

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

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

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

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

min (300 : 2 , 100 : 1 , 400 : 1 ) = 100

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

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

Базис

B

x1

x2

x3

x4

x5

x6

x7

min

x5

300

2

1

1

3

1

0

0

150

x6

100

1

0

2

1

0

1

0

100

x7

400

1

2

1

0

0

0

1

400

F(X1)

0

-5

-3

-2

-1

0

0

0

0


 

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

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

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

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

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

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

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

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

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

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

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

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

B

x 1

x 2

x 3

x 4

x 5

x 6

x 7

300-(100 • 2):1

2-(1 • 2):1

1-(0 • 2):1

1-(2 • 2):1

3-(1 • 2):1

1-(0 • 2):1

0-(1 • 2):1

0-(0 • 2):1

100 : 1

1 : 1

0 : 1

2 : 1

1 : 1

0 : 1

1 : 1

0 : 1

400-(100 • 1):1

1-(1 • 1):1

2-(0 • 1):1

1-(2 • 1):1

0-(1 • 1):1

0-(0 • 1):1

0-(1 • 1):1

1-(0 • 1):1

0-(100 • -5):1

-5-(1 • -5):1

-3-(0 • -5):1

-2-(2 • -5):1

-1-(1 • -5):1

0-(0 • -5):1

0-(1 • -5):1

0-(0 • -5):1


 

 

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

Базис

B

x1

x2

x3

x4

x5

x6

x7

x5

100

0

1

-3

1

1

-2

0

x1

100

1

0

2

1

0

1

0

x7

300

0

2

-1

-1

0

-1

1

F(X1)

500

0

-3

8

4

0

5

0


 

Итерация №1.

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

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

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

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

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

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

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

min (100 : 1 , - , 300 : 2 ) = 100

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

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

Базис

B

x1

x2

x3

x4

x5

x6

x7

min

x5

100

0

1

-3

1

1

-2

0

100

x1

100

1

0

2

1

0

1

0

-

x7

300

0

2

-1

-1

0

-1

1

150

F(X2)

500

0

-3

8

4

0

5

0

0


 

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

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

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

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

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

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

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

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

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

B

x 1

x 2

x 3

x 4

x 5

x 6

x 7

100 : 1

0 : 1

1 : 1

-3 : 1

1 : 1

1 : 1

-2 : 1

0 : 1

100-(100 • 0):1

1-(0 • 0):1

0-(1 • 0):1

2-(-3 • 0):1

1-(1 • 0):1

0-(1 • 0):1

1-(-2 • 0):1

0-(0 • 0):1

300-(100 • 2):1

0-(0 • 2):1

2-(1 • 2):1

-1-(-3 • 2):1

-1-(1 • 2):1

0-(1 • 2):1

-1-(-2 • 2):1

1-(0 • 2):1

500-(100 • -3):1

0-(0 • -3):1

-3-(1 • -3):1

8-(-3 • -3):1

4-(1 • -3):1

0-(1 • -3):1

5-(-2 • -3):1

0-(0 • -3):1


 

 

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

Базис

B

x1

x2

x3

x4

x5

x6

x7

x2

100

0

1

-3

1

1

-2

0

x1

100

1

0

2

1

0

1

0

x7

100

0

0

5

-3

-2

3

1

F(X2)

800

0

0

-1

7

3

-1

0


 

Итерация №2.

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

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

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

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

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

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

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

min (- , 100 : 1 , 100 : 3 ) = 331/3

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

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

Базис

B

x1

x2

x3

x4

x5

x6

x7

min

x2

100

0

1

-3

1

1

-2

0

-

x1

100

1

0

2

1

0

1

0

100

x7

100

0

0

5

-3

-2

3

1

331/3

F(X3)

800

0

0

-1

7

3

-1

0

0


 

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

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

Вместо переменной x7 в план 3 войдет переменная x6.

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

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

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

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

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

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

B

x 1

x 2

x 3

x 4

x 5

x 6

x 7

100-(100 • -2):3

0-(0 • -2):3

1-(0 • -2):3

-3-(5 • -2):3

1-(-3 • -2):3

1-(-2 • -2):3

-2-(3 • -2):3

0-(1 • -2):3

100-(100 • 1):3

1-(0 • 1):3

0-(0 • 1):3

2-(5 • 1):3

1-(-3 • 1):3

0-(-2 • 1):3

1-(3 • 1):3

0-(1 • 1):3

100 : 3

0 : 3

0 : 3

5 : 3

-3 : 3

-2 : 3

3 : 3

1 : 3

800-(100 • -1):3

0-(0 • -1):3

0-(0 • -1):3

-1-(5 • -1):3

7-(-3 • -1):3

3-(-2 • -1):3

-1-(3 • -1):3

0-(1 • -1):3


 

 

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

Базис

B

x1

x2

x3

x4

x5

x6

x7

x2

1662/3

0

1

1/3

-1

-1/3

0

2/3

x1

662/3

1

0

1/3

2

2/3

0

-1/3

x6

331/3

0

0

12/3

-1

-2/3

1

1/3

F(X3)

8331/3

0

0

2/3

6

21/3

0

1/3


 

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

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

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

Базис

B

x1

x2

x3

x4

x5

x6

x7

x2

1662/3

0

1

1/3

-1

-1/3

0

2/3

x1

662/3

1

0

1/3

2

2/3

0

-1/3

x6

331/3

0

0

12/3

-1

-2/3

1

1/3

F(X4)

8331/3

0

0

2/3

6

21/3

0

1/3


 

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

x2 = 1662/3

x1 = 662/3

F(X) = 3•1662/3 + 5•662/3 = 8331/3

Анализ оптимального плана.

В оптимальный план вошла дополнительная переменная x6. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 331/3

Значение 0 в столбце x1 означает, что использование x1 - выгодно.

Значение 0 в столбце x2 означает, что использование x2 - выгодно.

Значение 2/3> 0 в столбце x3 означает, что использование x3 - не выгодно.

Значение 6> 0 в столбце x4 означает, что использование x4 - не выгодно.

Значение 21/3 в столбце x5 означает, что теневая цена (двойственная оценка) равна 21/3.

Значение 1/3 в столбце x7 означает, что теневая цена (двойственная оценка) равна 1/3.


Задачи линейного программирования. 3 📙 Контрольная → 🆔 31146

Задачи линейного программирования. 3 📙 Контрольная → 🆔 31146

Задачи линейного программирования. 3