Задача линейного программирования. Симплекс – метод

Задачей линейного программирования называется задача оптимизации (максимизации или минимизации) линейной функции на полиэдре.

Общая задача линейного программирования имеет вид:

→ max (min)

(3.1)

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

1. Преобразование общей задачи к стандартному (каноническому) виду.

2. Нахождение опорного решения.

3. Оптимизация найденного решения.

На первом этапе общая задача преобразуется к виду:

→ min (3.2)

 

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

Для перехода от неравенств к равенствам, перепишем, каждое из неравенств в виде

; s=1, …, k

и введем дополнительные переменные

; s=1, …, k

При этом, очевидно, что .

Если какая – либо переменная х_i может по условию задачи принимать не только положительные, но и отрицательные значения, то ее можно представить в виде разности дополнительных неотрицательных переменных , ; .

На втором этапе исследуется стандартная (каноническая) задача (3.2). В рассматриваемой задаче область допустимых значений будет существовать только в случае m< n (если m=n, то система линейно независимых уравнений имеет единственное решение, а при m> n система вообще не имеет решений). Следовательно, m переменных можно выразить через остальные.

(3.3)

Неизвестные х₁, …, х_m называются базисными, а неизвестные х_m+1, …, x_n – свободными. Очевидно, что система (3.3) имеет бесконечное число решений. Если положить все свободные неизвестные равными нулю, то базисные неизвестные будут равны свободным коэффициентам в равенствах (3.3),

х₁ =b^/₁, …, х_т= b^/_m, x_m+1 = …= x_n = 0.

Полученное решение называется базисным. При этом может оказаться, что некоторые b_i будут отрицательными, и полученное базисное решение не будет удовлетворять системе (3.2). Система (3.3) имеет базисных решений.

Базисное решение, у которого все значения х_i ≥ 0, называется опорным. Для нахождения опорного решения можно воспользоваться методом исключений Жордана- Гаусса.

Пусть система ограничений (3.2) записана в виде:

 

(3.4)

Такая система называется приведенной к единичному базису.

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

 

	х1	х2	…	хт	хт+1	…	хп	b	(3.5)
x1			…		d1m+1	…	d1n	b1
x2			…		d2m+1	…	d2n	b2
…	.	.	…	.	.	…	.	.
xm			…		dmm+1	…	dnn	bm

 

Символы в первом столбце указывают базисные неизвестные. Преобразуем таблицу (3.5) таким образом, чтобы все элементы последнего столбца стали неотрицательными. Для этого выберем среди всех строк с отрицательными b_i такую, у которой b_i наибольший по абсолютной величине. Пусть эта строка имеет номер s. Умножим эту строку на -1 и прибавим ко всем строкам, для которых b_i < 0. Тем самым получим новую таблицу, в которой все элементы последнего столбца будут неотрицательными. При этом в отличие от всех остальных уравнений системы s – e уравнение не будет разрешено относительно базисной неизвестной. Приведем систему к единичному базису, сохранив достигнутую неотрицательность последнего столбца. Для этого используем алгоритм симплексных преобразований таблиц, а именно:

1. Выбираем разрешающий столбец из условия, что элемент d_sp, расположенный на пересечении этого столбца и выбранной ранее s-ой строки был положительным. Если такого элемента не окажется, то система не имеет опорного решения.

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

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

4. Вычисляем элементы всех остальных строк по формуле , то есть вычитая из всех остальных строк l-ю разрешающую строку, умноженную на соответствующее число, добиваемся, чтобы все элементы разрешающего столбца, кроме опорного, стали равны нулю. При этом х_l становится базисной неизвестной и записывается в символьном столбце таблицы вместо х_р.

При выполнении указанного алгоритма симплексных преобразований возможны три случая.

1. Разрешающий элемент d_lp, определенный в пункте 2 симплексного алгоритма, принадлежит выбранной s-ой строке, то есть l=s. Тогда после выполнения итерации симплексных преобразований система будет приведена к единичному базису и последний столбец, полученной таблицы будет описывать опорное решение.

2. Разрешающий элемент d_lp не принадлежит выбранной s- ой строке (l ≠ s). В этом случае проводится следующая итерация по описанному симплексному алгоритму.

3. При выполнении преобразований все элементы, какой- либо строки, за исключением последнего, окажутся не положительными, то есть d_ik ≤ 0, b_i > 0. Тогда система уравнений не имеет опорного решения.

Пусть опорное решение системы (3.2) найдено и х₁, …, х_т – базисные неизвестные, то есть х₁ = β ₁, х₂ = β ₂, …, х_т = β _т, х_т+1 = х_т+2 =…=х_п = 0.

В этом случае система (3.2) преобразуется в систему равенств

где β _i ≥ 0, i =1, …, m

Выразим целевую функцию z через свободные неизвестные. Тогда задача (3.1) запишется в виде:

 

z+ γ _m+1 x_m+1 + γ _m+2 x_m+2 + …+ γ _n x_n = γ ₀ → max (3.6)

 

(3.7)

Для поиска оптимального решения задачи (3.6) с ограничениями (3.7) будем использовать симплекс-метод.

В основе симплекс–метода лежит описанная выше процедура симплексных преобразований, заключающаяся в последовательном переходе от имеющегося опорного решения к другому опорному решению, так чтобы значение функции z увеличивалось, либо, по крайней мере, не уменьшалось.

Составим симплекс – таблицу из коэффициентов системы (3.6) и (3.7) следующим образом: в первую строку запишем неизвестные, следующие т строк составляют коэффициенты системы (3.7), в последнюю строку записываем коэффициенты из равенства (3.6), называемые оценками. В первом столбце таблицы выписываем базисные неизвестные.

 

	х1	х2	…	хт	хт+1	…	хп		(3.8)
х1			…		α 1т+1	…	α 1п	β 1
х2			…		α 2т+1	…	α 2п	β 2
…	.	.	…	.	.	…	.
хт			…		α тт+1	…	amп	β т
z			…		γ m+1	…	γ n	γ 0

Заметим, что последний столбец таблицы описывает опорное решение.

Для преобразования таблицы (3.8) используем алгоритм симплекс – метода.

1. Выбираем l-й разрешающий столбец из условия γ _l < 0 и хотя бы один элемент α _rl > 0.

2. Выбираем s- ю разрешающую строку из условия для всех α _rl > 0.

3. Производим пересечет элементов s-й строки по формуле , то есть все элементы разрешающей строки делим на разрешающий элемент, расположенный на пересечении s-й строки и l-го столбца.

4. Вычисляем элементы всех остальных строк по формуле α ^/_rk = α _rk – α ^/_sk α _rl. Полученные строки пишутся на месте прежних. При этом вместо х_s в символьной столбец таблицы пишется х_l.

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

Если после выполнения очередного шага:

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

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

в) все оценки в последней строке окажутся неотрицательными, то получено оптимальное решение.

Если в некоторых уравнениях системы (3.7) свободные члены β _i = 0, соответствующие базисные неизвестные также равны нулю. В этом случае базисное решение называется вырожденным. При решении такой задачи симплексным методом на каком–либо шаге может получиться симплекс-таблица, идентичная одной из предыдущих, то есть может произойти зацикливание в схеме расчета. Для устранения зацикливания разрешающую строку выбирают в соответствии со следующим правилом.

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

Используем симплекс – метод для решения задачи.

Предприятию нужно перевезти по железной дороге изделия трех видов: изделий первого вида не более 273, изделий второго вида не более 300, изделий третьего вида не более 380. Подразделение железной дороги может выделить для этого вагоны двух видов А и В. Для полной загрузки вагона следует помещать в него изделия всех трех видов.

При этом в вагон типа А входят 3 изделия первого вида, 3 изделия второго вида и 2 изделия третьего вида. В вагон типа В входят 2 изделия первого вида, 3 изделия второго вида и 5 изделий третьего вида. Экономия от перевозки в вагоне типа А составляет 40 тысяч рублей, а в вагоне типа В – 50 тысяч рублей. Сколько вагонов каждого типа следует выделить для перевозки, чтобы суммарная экономия от перевозки груза была наибольшей?

Составим математическую модель задачи.

Обозначим за х₁ используемое число вагонов типа А, за х₂ - число вагонов типа В.

Целевая функция – суммарная экономия – имеет вид

z = 40х₁ + 50х₂ → mах

Ограничения записываются в виде неравенств

 

3х₁ + 2х₂ ≤ 273

3х₁ + 3х₂ ≤ 300 (3.9)

2х₁ + 5х₂ ≤ 380

х₁ ≥ 0; х₂ ≥ 0.

Преобразуем задачу к каноническому виду. Для этого введем новые неизвестные

х₃ = 273 – 3х₁ – 2х₂

х₄ = 300 – 3х₁ – 3х₂

х₅ = 380 – 2х₁ – 5х₂

Очевидно, что в силу (3.9) х₃ ≥ 0, х₄ ≥ 0; х₅ ≥ 0.

Соответствующая каноническая задача имеет вид

z- 40х₁ – 50х₂ = 0 → mах

3х₁+ 2х₂+ х₃ = 273

3х₁+ 3х₂+ х₄ = 300 (3.10)

2х₁+ 5х₂+ х₅ = 380

х_i ≥ 0, i= 1, …, 5

В системе (3.10) неизвестные х₃, х₄, х₅ выражаются через неизвестные х₁ и х₂, то есть получившаяся система уже приведена к единичному базису и х₃, х₄, х₅ – базисные неизвестные. Такой системе соответствует базисное решение х₁ = 0, х₂ = 0, х₃ = 273,

х₄ = 300, х₅ = 380. Все неизвестные неотрицательны, то есть базисное решение является опорным. Целевая функция z выражена через свободные неизвестные х₁ и х₂.

Составим симплекс- таблицу:

	х1	х2	х3	х4	х5
х1
х2
х3
z	-40	-50

В последней строке имеем две отрицательные оценки, следовательно, найденное опорное решение не оптимально. Применим симплексный алгоритм.

За разрешающий столбец выбираем первый. В этом столбце три положительных элемента 3, 3 и 2. Разделим на эти числа соответствующие свободные коэффициенты системы (3.10), записанные в последнем столбце таблицы. Имеем ; ;

. Наименьшее из полученных частных 91 соответствует первой строке, которую выбираем за разрешающую. Таким образом, разрешающий элемент расположен на пересечении первой строки и первого столбца и равен 3. Для составления следующей таблицы разделим элементы разрешающей строки на разрешающий элемент и полученную строку пишем на месте прежней. К каждой из остальных строк прибавляем (вычитаем) вновь полученную, умноженную на такое число, чтобы в клетках разрешающего столбца появились нули и пишем преобразованные строки на месте прежних. Новый базис составляют неизвестные х₁, х₄ и х₅.

	х1	х2	х3	х4	х5
х1		2/3	1/3
х4			-1
х5		11/3	-2/3
z		-70/3	40/3

Полученной таблице соответствует опорное решение х₁ = 91, х₂ = 0, х₃ = 0,

х₄ = 27, х₅ = 198 и значение экономии z=3640 тысяч рублей. Последняя строка содержит отрицательную оценку во втором столбце, поэтому полученное решение не оптимально.

Выберем второй столбец за разрешающий. В этом столбце три положительных элемента. Разделим на них соответствующие элементы последнего столбца. Получаем 91: (2/3)=273/2, 27: 1=27, 198: (11/3)=54. Следовательно, за разрешающую строку выбираем вторую. Повторяя описанную выше процедуру пересчета, получим новую симплекс – таблицу.

	х1	х2	х3	х4	х5
х1				-2/3
х2			-1
х5				-11/3
z			-10	70/3

Получено новое опорное решение х₁ = 73, х₂ = 27, х₃ = 0, х₄ = 0, х₅ = 99 и z=4270 тысяч рублей.

Это решение не оптимальное, поскольку в последней строке имеется отрицательная оценка.

На следующем этапе за разрешающий столбец выбираем третий. Так как 73: 1=73 и 99: 3=33, за разрешающую строку выбираем третью. Применяя рассмотренный выше вычислительный алгоритм, получим

	х1	х2	х3	х4	х5
х1				5/9	-1/3
х2				-2/9	1/3
х3				-11/9	1/3
z				100/9	10/3

В последней строке таблицы отрицательных оценок нет. Следовательно, эта таблица соответствует оптимальному решению х₁ = 40, х₂ = 60, х₃ = 33, х₄ = 0, х₅ = 0.

Таким образом, для оптимальной перевозки следует выделить 40 вагонов типа А и 60 вагонов типа В. При этом останутся на складе 33 изделия первого вида (х₃=33), а изделия второго и третьего видов будут перевезены полностью (х₄=0, х₅=0). Сумма экономии составит 4600 тысяч рублей.

 

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

Каждой задаче линейного программирования можно поставить в соответствие задачу, называемую двойственной.

Запишем общую задачу линейного программирования

→ max

(4.1)

Двойственной задачей к задаче (4.1) называется задача

(4.2)

В таком случае задача (4.1) называется прямой. Исходная и двойственная задачи образуют пару взаимно двойственных задач, при этом любую из них можно рассматривать как прямую задачу.

Переход от прямой задачи к двойственной можно осуществить с помощью следующих правил.

1. Каждому ограничению – неравенству со знаком ≤ соответствует неотрицательная неизвестная y_i двойственной задачи, а каждому ограничению – равенству неизвестная произвольного знака.

2. Каждой неотрицательной неизвестной х_j прямой задачи соответствует ограничение – неравенство со знаком ≥ двойственной задачи, а каждой произвольной по знаку переменной – ограничение в виде равенства.

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

4. Свободные коэффициенты системы ограничений равны соответствующим коэффициентам при неизвестных х_j целевой функции прямой задачи.

5. Коэффициенты при неизвестных y_i целевой функции L двойственной задачи равны свободным коэффициентам системы ограничений прямой задачи.

6. Если целевая функция z прямой задачи максимизируется, то целевая функция L двойственной задачи минимизируется, и наоборот, если целевая функция z прямой задачи минимизируется, то целевая функция L двойственной задачи максимизируется.

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

Справедливы следующие утверждения.

1. Двойственная задача (4.2) имеет решение в том и только в том случае, если имеет решение прямая задача (4.1).

2. Если есть оптимальное решение прямой задачи (4.1), а есть оптимальное решение двойственной задачи (4.2), то выполняется соотношение двойственности

(4.3)

3. Если получено решение одной из пары двойственных задач, например, прямой, то оптимальное решение другой задачи определяется равенством

(4.4)

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

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

.

(4.5)

В качестве примера найдем неотрицательные значения х₁ и х₂, максимизирующие функцию

(4.6)

при наличии ограничений

 

(4.7)

с помощью перехода к двойственной задаче.

Используя сформулированные выше правила, перейдем к двойственной задаче

 

(4.8)

 

(4.9)

Перейдем к канонической задаче. Для этого перенесем свободные коэффициенты в левые части неравенств (4.9) и обозначим получившиеся выражения за новые неизвестные

,

.

Кроме того, перейдем к задаче на максимум. Для этого поменяем знаки в правой части целевой функции (4.8). Каноническая задача имеет вид:

 

; (4.10)

 

(4.11)

Для решения задачи симплекс – методом необходимо привести систему (4.11) к единичному базису и найти опорное решение. Умножим равенства (4.11) на (-1). Тогда получим

(4.12)

В полученной системе неизвестные y₃ и y₄ выражаются через y₁ и y₂.

Тем самым, система приведена к единичному базису. Приравнивая, свободные неизвестные y₁ и y₂ к нулю, получим базисное решение.

y₁=0; y₂=0; y₃=-5; y₄=-4.

Так как базисные неизвестные отрицательны, полученное решение не является опорным. Для нахождения опорного решения воспользуемся методом исключений Жордана – Гаусса. Выпишем коэффициенты системы (4.12) в таблицу

	y1	y2	y3	y4
y3	-4	-3			-5
y4	-3	-4			-4

Умножим первую строку на (-1) и прибавим ко второй строке. При этом y₃ перестает быть базисной неизвестной.

	y1	y2	y3	y4
			-1
y4		-1	-1

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

	y1	y2	y3	y4
	4/3		-1/3		5/3
y4		-1	-1

Получим нуль в разрешающем столбце. Для этого ко второй строке прибавим разрешающую. При этом неизвестная y₂, соответствующая разрешающему столбцу, становится базисной и пишется в символьном столбце

	y1	y2	y3	y4
y2	4/3		-1/3		5/3
y4	7/3		-4/3		8/3

 

Полученной таблице соответствует система равенств

или

(4.13)

Эта система приведена к единичному базису и базисное решение, соответствующее этой системе является опорным

 

y₁=0; ; y₃=0; (4.14)

Выразим целевую функцию L₁ через свободные неизвестные y₁ и y₃. Для этого подставим равенства (4.13) в (4.10). Тогда задача (4.10); (4.11) с учетом (4.13) примет вид

;

Составим симплекс – таблицу

	y1	y2	y3	y4
y2	4/3		-1/3		5/3
y4	7/3		-4/3		8/3
L1	-8				-40

В последней строке в первом столбце имеется отрицательная оценка. Следовательно, опорное решение (4.14), соответствующее записанной таблице, не оптимально. Выберем первый столбец за разрешающий. Разделим элементы последнего столбца на соответствующие положительные элементы разрешающего столбца

; .

Наименьший результат соответствует второй строке, поэтому выберем эту строку за разрешающую. Разрешающий элемент равен 7/3. Разделим разрешающую строку на разрешающий элемент.

	y1	y2	y3	y4
y2	4/3		-1/3		5/3
y4			-4/7	3/7	8/7
L1	-8				-4

Получим нули в разрешающем столбце. Для этого из первой строки вычтем разрешающую, умноженную на 4/3, а к последней прибавим разрешающую, умноженную на 8.

После пересчета имеем

	y1	y2	y3	y4
y2			3/7	-4/7	1/7
y1			-4/7	3/7	8/7
L1			24/7	24/7	-216/7

В последней строке отрицательных оценок (коэффициентов при неизвестных y_i) нет. Следовательно, опорное решение, соответствующее полученной таблице оптимально.

; ; y₃=0; y₄=0; . (4.15)

Определим решение прямой задачи (4.6); (4.7), используя формулу (4.4)

.

Здесь - матрица - строка.

Учтем, что базисными неизвестными в оптимальном решении являются y₁ и y₂, и элементами матриц С_о и W являются коэффициенты при базисных неизвестных оптимального решения в равенствах (4.8) и (4.11). То есть

С_о=(24 24);

В этом случае обратная матрица W^-1 имет вид

Отсюда

.

Таким образом, оптимальное решение (4.6), (4.7) следующее

(4.16)

; ; .

Заметим, что прямая исходная задача (4.6), (4.7) не содержит ограничений в виде равенств, поэтому оптимальное решение (4.16) может быть записано сразу без использования формулы (4.4). Для этого можно воспользоваться равенствами (4.5)

,

,

где b₃ и b₄ – элементы последней строки симплекс–таблицы, соответствующей оптимальному решению.

 

⇐ Предыдущая123456Следующая ⇒

Поделиться:

Популярное:

1. Алгоритм решения задач динамического программирования.
2. Есть, конечно, и другие важные составляющие Delphi, вроде линейки инструментов, системного меню и многих других, нужных вам для точной настройки программы и среды программирования.
3. Каковы особенности заполнения первой симплексной таблицы в задачах решаемых М-методом?
4. Коэффициент линейного теплового расширения
5. Магнитное поле прямолинейного проводника
6. Область допустимых решений задачи линейного программирования имеет вид
7. Основы нейролингвистического программирования. Применение техник НЛП в создании рекламного обращения.
8. Подходы к решению задач линейного программирования
9. Соотносительность ряда позитивных моментов содержательного цифрового распределения от минимального значения к максимуму есть цепеобразное построение линейного функционирования.
10. Тема2:. Графический метод решения задач линейного программирования
11. Тема: Использование программных комплексов при решении задач линейного программирования