Симплексный метод на основе укороченных таблиц

Рассмотрим систему уравнений (1.3) и запишем ее в виде таблицы 1.4

 

СП БП	1	X1	X2
Y1	350	14	5
Y2	392	14	8
Y3	408	6	12
Z	0	-10	-5

 

 

Таблица 1.4

    В первый столбец записываем базисные переменные (БП), а в первую строку – свободные переменные (СП). Далее переход к новой таблице 1.5 совершаем по правилу:

 

1) меняем местами СП и БП

2) на месте разрешающего элемента стоит величина ему обратная

3) элементы разрешающей стоки делим на разрешающее число

4) элементы разрешающего столбца делим на разрешающее чисто и меняем знак

5) остальные элементы находятся как в главе “Отыскание максимума линейнойфункции” правило 4 (правило прямоугольников для ОЖИ). Получаем таблицу 1.5.
 

СП БП	1	Y1	X2
X1	25	1/14	5/14
Y2	42	-1	3
Y3	258	-6/14	138/14
Z	250	10/14	-20/14

 

 

Таблица 1.5

Улучшаем этот опорный план, производя симплексное преобразование с разрешающим элементом “3” (табл. 1.6).

СП БП	1	Y1	Y2
X1	20	4/21	-5/42
X2	14	-1/3	1/3
Y3	120	20/7	-23/7
Z	270	5/21	10/21

 

 

Таблица 1.6

Получили оптимальный план Z_max = 270 при X₁ =20, X₂ = 14, а ресурсы оборудования оказались в избытке в количестве 120 станко–часов.

Решение задачи линейного программирования

Найти максимум целевой функции

 

F = 10x + 5y

 

при ограничениях

 

14x + 5y ≤ 350       

7x + 4y ≤ 196

x + 2y ≤ 68

 

Решение задачи с использованием программы Microsoft Excel.

Отведем А3 и B3 под значения переменных x и y.

 

В ячейку C4 введем функцию цели

 

                 = 10*A3 + 5*B3

 

В ячейки A7:A9 введем левые части ограничений

 

                 = 14*A3 + 5*B3

                 = 7*A3 + 4*B3

                 = A3 + 2*B3

 

а в ячейки B7:B9 – правые части ограничений.

 

После этого выберем команду Сервис, Поиск решения (Tools, Solver) и заполним открывшееся диалоговое окно Поиск решения (Solver) как показано на рис. 2. После нажатия кнопки Выполнить (Solve) открывается окно Результаты поиска решения (Solver Results), которое сообщает, что решение найдено (рис. 3).

 

 

Рис. 2. Поиск решения

 

  

Рис. 3. Результаты поиска решения

 

Геометрическое решение задачи с применением программы MATHCAD 2000.

1. Установите режим автоматических вычислений.

2. Запишите в виде y = kx + b уравнения прямых, ограничивающих область допустимых значений переменных. Для того чтобы ввести и разрешить относительно y ограничение 14x + 5y ≤ 350, введите левую часть неравенства, нажмите кнопку Ctrl и нажмите одновременно кнопку =, удерживая предыдущую до тех пор пока выскочит жирный знак =, пометьте выделяющей рамкой переменную y, щелкните в меню Symbolic (Символы) по строке Solve (Вычислить) – результат вычислений будет выведен в рабочем документе справа от уравнения; введите имя функции (в рассматриваемом примере y1(x)) и присвойте ей полученное выражение. Таким образом, определено уравнение одной из прямых, ограничивающих область допустимых значений. Аналогично введите остальные ограничения. Введите уравнение 10x + 5y = C линии уровня (опорная прямая) целевой функции. Действуйте так же, как и при вводе ограничений, но перед тем как разрешить уравнение относительно y, присвойте какое-нибудь значение константе C.

3. Изобразите на графике соответствующие прямые и определите область допустимых решений системы.

4. Изменяя значения константы C, например C = 100,150,200,250,..., наблюдайте за движением опорной прямой и сформулируйте вывод о разрешимости задачи.

5. Если задача имеет единственное решение, найдите вершину, в которой Z = Z_max. В нашем примере максимум целевой функции достигается в точке пересечения прямых 14x + 5y = 350 и 7x + 14y = 196. Найдите координаты точки, используя функцию Find.

6. Вычислите значение целевой функции в найденной точке.

 

 

14x + 5y = 350 (-14/5)x + 70  y1(x):= (-14/5)x + 70

 

7x + 4y = 196 (-7/4)x + 49    y2(x):= (-7/4)x + 49    

 

x + 2y = 68     (-1/2)x + 34    y3(x):= (-1/2)x + 34

 

10x + 5y = C  -2x + (1/5)C   y4(x):= -2x + (1/5)C         

 

C:= 100;

 

Рис. 4.

 

Данным

 

14x + 5x = 360

7x + 4y = 196

 

Найти (x, y) → (20, 14)

f(x, y): = 10x + 5y

fmin: = f(20, 14)

fmin: = 270

 

 

Аналитическое решение задачи с применением программы MATHCAD 2000.

Аналитическое решение задачи в MathCAD значительно проще.

 

1. Установите режим автоматических вычислений.

2. Запишите задачу произвольным x и y присвойте произвольные (допустимые) значения, чтобы программа могла начать счет.

 

Z(x, y): = 10x + 5y

X: = 1y: = 1

 

Данным

 

14x + 5x ≤ 360

7x + 4y ≤ 196

x + 2y ≤ 68

 

M: = Максимизировать (z, x, y)     M = (20, 14)     Z (M₀, M₁) = 270

 

 

Задача максимизации линейной функции при наличии отрицательных свободных коэффициентов

Найти максимум линейной функции

 

Z = X₁ + X₂

 

при ограничениях

 

X₁ – X₂ ≤ 3,

X₁ + X₂ ≥ 5,

2X₁ – 3X₂ ≤ 6,

X₂ ≤ 6,

X₁ ≥ 0, X₂ ≥ 0.

 

Запишем систему в виде

 

Y₁ = -X₁ + X₂ + 3 ≥ 0

Y₂ = X₁ + X₂ - 5 ≥ 0

Y₃ = -2X₁ + 3X₂ + 6 ≥ 0

Y₄ = -X₂ + 6 ≥ 0

 

Составим таблицу.

 

	-X1	-X2	1
Y1	1	-1	3
Y2	-1	-1	-5
Y3	2	-3	6
Y4	0	1	6
Z	-1	-1	0

 

В столбце имеется отрицательный элемент “-5”, его надо убрать, чтобы на этом месте был положительный элемент. Совершаем ШМЖИ с разрешающим элементом 1. Получаем таблицу.

 

	-Y1	-X2	1
X1	1	-1	3
Y2	1	-2	-2
Y3	-2	-1	0
Y4	0	1	6
Z	1	-2	3

 

Продолжаем работать со 2-й строкой, так как отрицательный элемент не пропал. Совершаем ШМЖИ с разрешающим элементом -2. Получаем таблицу.

 

	-Y1	-Y2	1
X1	1/2	-1/2	4
X2	-1/2	-1/2	1
Y3	-5/2	-1/2	1
Y4	1/2	1/2	5
Z	0	-1	5

 

Все свободные переменные положительные, находим опорное решение, полагая

Y₁ = Y₂ = 0, X₁ = 4, X₂ = 1, Y₃ = 1, Y₄ = 5. Так как план не оптимальный, то совершаем ШМЖИ с разрешающим элементом 1/2. Получаем таблицу, из которой имеем оптимальное решение X₁ = 9, X₂ = 6 и Z_max  = 15.

 

	-Y1	-Y4	1
X1	1	1	9
X2	0	1	6
Y3	-2	1	6
Y2	1	2	10
Z	1	2	15