Решение задачи симплекс-методом

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

Постановка задачи

На предприятии выпускают n видов продукции . При ее изготовлении используются ресурсы P₁, P₂ и P₃. Размеры допустимых затрат ресурсов ограничены соответственно величинами b ₁ , b ₂ и b ₃ . Расход ресурса i-го (i = 1, 2, 3) вида на единицу продукции j-го вида составляет a_ij ден. ед. Цена единицы продукции j-го вида равна c_j ден. ед.

Требуется:

составить экономико-математическую модель задачи, позволяющую найти сбалансированный план выпуска продукции, обеспечивающий предприятию максимальный доход;

найти оптимальный план выпуска продукции по видам (дать содержательный ответ, раскрыв экономический смысл всех переменных, приведенных в решении задачи);

n = 3; b = ; A = ; c = (9 10 16).

Обозначим через x₁, x₂, x₃ количество единиц продукции соответственно П₁, П₂, П₃, планируемой к выпуску, а через f - величину дохода от реализации этой продукции. Тогда, учитывая цену единицы продукции П₁, равную 9 ден. ед., единицы П₂ - 10 ден. ед., единицы П₃ - 16 ден. ед., запишем суммарную величину дохода - целевую функцию - в следующем виде:

 

f = 9x₁ + 10x₂ + 16x₃.                                                                        (1)

 

Переменные х₁, х₂, х₃ должны удовлетворять ограничениям, накладываемым на расход имеющихся в распоряжении предприятия ресурсов. Так, затраты ресурса Р₁ на выполнение плана (х₁, х₂, х₃) составят

18x₁ + 15x₂ + 13x₃ единиц,

где 18х₁ - затраты ресурса Р₁ на выпуск x₁ единицы продукции П₁; 15х₂ - на выпуск единицы продукции П₂; 12х₃ - на выпуск единицы продукции П₃. Указанная сумма не может превышать имеющийся запас Р₁ в 360 единиц, т.е.

 

x₁ + 15x₂ + 13x₃ £ 360.                                                                     (2)

 

Аналогично получаем ограничения по расходу ресурсов Р₂, Р₃:

 

x₁ + 4x₂ + 8x₃ £ 192.                                                                         (3)

x₁ + 3x₂ + 3x₃ £ 180.                                                                         (4)

 

По смыслу задачи переменные х₁, х₂, х₃ не могут выражаться отрицательными числами, т.е.

 

x_j  0 (j = )  (5)

 

Соотношения (1) - (5) образуют экономико-математическую модель данной задачи. Итак, математически задача сводится к нахождению числовых значений х₁*, х₂*, х₃* переменных х₁, х₂, х₃, удовлетворяющих линейным неравенствам (2) - (5) и доставляющих максимум линейной функции (1).

Приведем модель задачи к канонической форме, преобразовать неравенства в эквивалентные уравнения. Для этого введем в левые части неравенств дополнительные (балансовые) неотрицательные переменные x₅, x₆, х₇. В результате получим:

 

f = 9x₁ + 10x₂ + 16x₃ → max                                                            (6)

x₁ + 15x₂ + 13x₃ + x₄ = 360.

6x₁ + 4x₂ + 8x₃ + x₅ = 192.                                                                (7)

x₁ + 3x₂ + 3x₃ + x₆ = 180.

x_j ³ 0 (j = )   (8)

 

Экономический смысл переменных х₄, х₅, х₆ - возможные остатки ресурсов Р₁, Р₂, Р₃ соответственно (резервы).

Решение задачи симплекс-методом

В канонической модели (6) - (8) каждая из переменных х₄, х₅, х₆ является базисной, а остальные переменные - свободными. В связи с этим, в первую симплексную таблицу системы ограничительных уравнений (1.7) можно записать в виде, разрешенном относительно базиса х₄, х₅, х₆ (табл. 1).

 

Таблица 1

		x1	x2	x3	x4	x5	x6
x4	360	18	15	13	1	0	0	27,7
x5	192	6	4	8	0	1	0	24
x6	180	5	3	3	0	0	1	60
f	0	-9	-10	-16	0	0	0

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

Все элементы столбца свободных членов положительны, поэтому содержащийся в табл. 1 план (0; 0; 0; 360; 192; 180) является опорным. Однако этот план не является оптимальным: в f-строке имеются отрицательные элементы.

Чтобы получить новый опорный план более близкий к оптимальному, выполним симплексное преобразование (табл. 1). С этой целью выберем переменные, участвующие в преобразовании базиса х₄, х₅, х₆ в новый базис. Наибольший по модулю отрицательный элемент (-16) f-строки указывает, что в новый базис следует ввести переменную х₃, т.е. в качестве разрешающего в предстоящем симплексном преобразовании надо взять третий столбец. Чтобы определить переменную, выводимую из базиса, составляем симплексные отношения и выбираем наименьшее из них:

min (360/13; 192/8; 180/3) = min (27,7; 24; 60) = 24.

Итак, из базиса надо исключить переменную, стоящую во второй (разрешающей) строке, т.е. х₅.На пересечении разрешающих столбца и строки находится разрешающий элемент 8, с которым и выполняем симплекс-преобразование. Получаем табл. 2.

 

Таблица 2

		x1	x2	x3	x4	x5	x6
x4	48	8,25	8,5	0	1	-1,625	0	5,6
x3	24	0,75	0,5	1	0	0,125	0	48
x6	108	2,75	1,5	0	0	-0,375	1	72
f	384	3	-2	0	0	2	0

 

Полученному плану X = (0; 0; 24; 48; 0; 108) соответствует значение целевой функции f(X₁) = 384. В f-строке табл. 2 есть отрицательный элемент, равный -2, значит, полученный опорный план оптимальным не является.

Наибольший по модулю отрицательный элемент (-2) f-строки указывает, что в новый базис следует ввести переменную х₂, т.е. в качестве разрешающего в предстоящем симплексном преобразовании надо взять второй столбец. Чтобы определить переменную, выводимую из базиса, составляем симплексные отношения и выбираем наименьшее:

min (48/8,5; 24/0,5; 108/1,5) = min (5,6; 48; 72) = 5,6.

Итак, из базиса надо исключить переменную, стоящую в первой (разрешающей) строке, т.е. х₄.На пересечении разрешающих столбца и строки находится разрешающий элемент 8,5, с которым и выполняем следующее симплекс-преобразование.

В результате приходим к табл. 3.

Таблица 3

		x1	x2	x3	x4	x5	x6
x2	5,647	0,971	1	0	0,118	-0,191	0
x3	21,176	0,265	0	1	-0,059	0,221	0
x6	99,529	1,294	0	0	-0,176	-0,088	1
f	395,3	4,941	0	0	0,235	1,618	0

 

Полученному плану X₂ = (0; 5,647; 21,176; 0; 0; 99,529) соответствует значение целевой функции f(X₂) = 395,3. В результате получаем табл. 3, в f-строке которой отрицательных элементов нет.

Значит, опорный план X* = Х₂ = (0; 5,647; 21,176; 0; 0; 99,529) является оптимальным, а соответствующее ему значение 395,3 целевой функции будет максимальным.

Итак, по оптимальному плану следует изготовить 5,647 ед. продукции вида П₂ и 21,176 ед. продукции П₃, продукцию вида П₁ производить не следует. При этом предприятие получит максимальную прибыль, которая составит 395,3 денежных единиц.

Останутся неиспользованными 99,529 ед. ресурса Р₃, а ресурсы Р₁ и Р₂ будут израсходованы полностью.

Двойственная задача

Чтобы составить модель двойственной задачи, запишем матрицу исходной задачи (1) - (5) в следующем виде:

 

.   (9)

 

Транспонируем матрицу (9) и получим матрицу (10) двойственной задачи.

 

. (10)

По исходной матрице (10) запишем модель задачи, двойственной исходной задаче:

 

φ = 360y₁ + 192y₂ + 180y₃ → min                                                  (11)

18y₁ + 6y₂ + 5y₃  9;

15y₁ + 4y₂ + 3y₃  10;

y₁ + 8y₂ + 3y₃  16;

y_i  0 (i = ). (13)

 

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

В п. 2 найден оптимальный план исходной задачи, его компоненты находятся в табл. 3. В f-строке этой же таблицы содержатся и компоненты у_i*оптимального плана двойственной задачи (11) - (13). Выписать компоненты у_i* поможет соответствие между переменными двойственных задач

Чтобы установить это соответствие, преобразуем ограничения-неравенства (12) в эквивалентные уравнения, вычитая из левых частей дополнительные неотрицательные переменные у₁*, у₂*, у₃*, равные разностям между левыми и правыми частями этих неравенств. Тогда модель (11) - (13) запишется в виде:

 

φ = 360y₁ + 192y₂ + 180y₃ → min;

18y₁ + 6y₂ + 5y₃ - y₄ = 9;

y₁ + 4y₂ + 3y₃ - y₅ = 10;

3y₁ + 8y₂ + 3y₃ - y₆ = 16;

y_i ³ 0 (i = ).

В этой записи переменные у₄, у₅, у₆ являются базисными, а у₁, у₂, у₃ - свободными. В исходной задаче (6) - (8) переменные x₁, x₂, x₃ являются свободными, а x₄, x₅, x₆ - базисными. Сопоставим базисным переменным одной задачи свободные переменные другой и наоборот, т.е.

 

СП        БП

x₁ x₂ x₃ x₄ x₅ x₆

у₄ у₅ у₆ у₁ у₂ у₃                                     (14)

БП        СП

 

Воспользуемся соответствием (14) для нахождения компонентов оптимального плана двойственной задачи. Находим их в табл. 3 в f-строке

 

.		x1	x2	x3	x4	x5	х6
f	395,3	4,941	0	0	0,235	1,618	0
		у4	у5	у6	у1	у2	у3

 

Получим оптимальный план двойственной задачи:

 

Y* = (0,235; 1,618; 0; 4,941; 0; 0).                                                 (15)

 

Как следует из теорем двойственности, экстремальные значения функций разрешимых двойственных задач совпадают:

f_max = φ_min = 395,3.

Величины y₁* = 0,235, y₂* = 1,618 и y₃* = 0 ден. ед. являются теневыми ценами на ресурсы S₁, S₂, S₃ соответственно и в данном случае служат мерой их дефицитности.

Как следует из оптимального плана (15) двойственной задачи, избыточным является ресурс S₃ (y₃* = 0). Ресурс S₂ является наиболее дефицитным (y₂* = 1,618), ресурс S₁ менее дефицитным (y₁* = 0,235).