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

В основе симплекс-метода лежит идея поиска базисного решения с последующим переходом от одного базиса к другому таким образом, чтобы целевая функция при этом все время увеличивалась, если речь идет о задаче максимизации. Для начала работы требуется, чтобы заданная система ограничений выражалась равенствами, причем в этой системе ограничений должны быть выделены базисные неизвестные. Решение задачи при помощи симплекс-метода распадается на ряд шагов. На каждом шаге от данного базиса Б переходят к другому, новому базису Б ¹ с таким расчетом, чтобы значение функции f(x) уменьшалось, т. е. f_Б’≥f_Б. Для перехода к новому базису из старого базиса удаляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый базис Б ^(k), для которого f_Б^(k) есть искомый максимум для линейной функции f, а соответствующее базисное решение является оптимальным либо выясняется, что задача не имеет решения.

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

Целевая функция вида:

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

,

Переобозначим свободные коэффициенты ограничений a_j0=b_j. Приведем матрицу ограничений к каноническому виду:

(10.1)

Используя метод Жордана-Гаусса, приведем записанную систему к виду, где выделены базисные переменные. Введем условные обозначения:

x ₁, x ₂,..., x_r - базисные переменные;

x_{r +1}, x_{r +2},..., x_n - свободные переменные.

Будем применять метод полного исключения к расширенной матрице ограничений. Выбираем направляющий элемент a_ij на данной итерации. В результате преобразования Гаусса получим новые значения коэффициентов:

(10.2)

Если l≠I, l =1,2,…, m.

Выясним условия, при которых новое базисное решение будет допустимым, т.е. для всех l. По предположению, a_l0≥0, тогда

Если то очевидно, , так как ,

Если то будет больше нуля при всех значениях l =1,2,…, m тогда и только тогда, когда при условии

Преобразование Гаусса называется симплексным преобразованием, когда направляющий элемент определяют по следующим правилам:

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

· направляющую строку выбирают так, чтобы отношения были минимальными при условии, что a_ij> 0.

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

По последней системе ограничений и целевой функции в каноническом виде построим симплекс-таблицу.

Таблица 10.1

Симплекс-таблица

С

С1

С2

С3

…

Сj

…

Cn

…

Bx

A0

A1

A2

A3

…

Aj

…

An

An+1

…

An+m

cn+1

xn+1

a10

a11

a12

a13

…

a1j

…

a1n

…

cn+2

xn+1

a20

a21

a22

a23

…

a2j

…

a2n

…

…

…

…

…

…

…

…

…

…

…

…

…

cn+i

xn+i

ai0

ai1

ai2

ai3

…

aij

…

ain

…

…

…

…

…

…

…

…

…

…

…

…

…

cn+m

xn+m

am0

am1

am2

am3

…

amj

…

amn

…

a00

a01

a02

a03

…

a0j

…

a0n

a0m+1

…

a0m+n

Все дальнейшие преобразования связаны с изменением содержания этой таблицы.

Нижняя строка элементов а_ок, к = 0,…, т+п называется индексной. Элементы индексной строки вычисляются следующим образом:

означает номер соответствующей строки.

Поскольку на первом шаге заполнения таблицы все элементы с_n+i равны нулю, то элементам индексной строки присваиваются значения соответствующих элементов целевой функции данного столбца, взятые с обратным знаком, т.е. а_ok= -С_к. Последняя строка таблицы служит для определения направляющего столбца.

Элемент а₀₀ равен значению целевой функции, которое вычисляется по формуле - номер базисной переменной (индексация идет по строкам таблицы).

В столбце В_х записываются базисные переменные, на первом шаге в качестве базисных выбирают фиктивные переменные {х_п+к }, к =1,…,т. В дальнейшем фиктивные переменные необходимо вывести из базиса.

В столбец С записываются коэффициенты при х_п+к, на первом шаге значения этих коэффициентов равны нулю.

Для перехода от базиса фиктивных переменных к базису реальных переменных применяют следующие правила:

• в качестве направляющего столбца выбирают столбец А_j для которого выполняется условие

a_0J = min{a_oi), l = l,…, п+т при а_0l < 0, т.е. выбирается минимальный элемент, при условии, что этот элемент отрицательный;

• • выбирают направляющую строку, для чего каждый элемент столбца свободных членов делится на соответствующий элемент направляющего столбца, элемент столбца свободных членов находится в одной строке с элементом направляющего столбца . Из всех возможных соотношений выбирается минимальное при условии, что a_rj > 0, 1 < г < т.

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

Переменная, которая соответствует направляющему столбцу, вводится в базис, а переменная, соответствующая направляющей строке, выводится из базиса. При этом для переменной, вводимой в базис, изменяется соответствующее значение коэффициента целевой функции. Вместо коэффициента с _n+i соответствующего старой базисной переменной, в таблице записывается значение коэффициента целевой функции при переменной, вводимой в базис.

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

1. Для всех элементов направляющей строки

где к - номер шага (к = 1, 2,...); i - номер направляющей строки; j - номер направляющего столбца; £ = 0, т.е. все элементы направляющей строки делим на направляющий элемент, в итоге направляющий элемент стал равным единице; .

2. В направляющем столбце необходимо получить , для всех , r≠i, при , т.е. в направляющем столбце должны быть все нули кроме направляющего элемента, который равен, единице.

Для всех остальных элементов, включая индексную строку, производим вычисления

(10.3)

Симплексные преобразования повторяют до тех пор, пока не реализуется один из двух возможных исходов:

а) все a_0i ≥ 0 - это условие оптимальности базиса последней табицы;

б) найдется такой элемент a_0j< 0, при котором все элементы столбца а_rj < 0, - это признак неограниченности целевой функции на множестве допустимых решений.

Пример решения задачи линейного программирования. Рассмотрим задачу линейного программирования в следующем виде: найти максимум линейной формы 4х₁ + 3х₂ при ограничениях

x₁ ≤;4000, х₂ ≤;6000, х₁ + х₂≤6000, х₁,х2 > 0.

Каноническая форма задачи линейного программирования будет иметь вид

4x₁ + 3x₂ + 0x₃ + 0x₄ + 0x₅ → max;

1х₁ + 0 х ₂ + 1х₃ + 0x₄ + 0x₅, = 4000;

0х₁ + 1 х ₂ + 0х₃ + 1x₄ + 0x₅, = 6000;

1х₁ + х ₂ + 0х₃ + 0x₄ + 1x₅ = 6000;

1х₁+ х ₂+ 0х₃ + 0x₄ + 1x₅ =6000.

Составим исходную симплекс-таблицу (табл. 10.2).

Таблица 10.2

С
	Bx	A0	A1	A2	A3	A4	A5
	хз
	x4
	x5
			-4	-3

Поскольку -4 < -3 < 0, то в качестве направляющего выбираем первый столбец. Составив отношение вида , определяем направляющую строку. Для этого находим минимальное отношение

min Следовательно, направляющая строка - первая, направляющий элемент — а₁₁=1- Применив первый шаг симплексного преобразования, получим новую таблицу (табл. 10.3).

Таблица 10.3

С
	Bx	A0	A1	A2	A3	A4	A5
	x1
	x4
	x5				-1
				-3

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

Табл. 10.4.

С
	Bx	A0	A1	A2	A3	A4	A5
	x1
	x4						-
	X2				-
					-

Так как а₀₃ = - < 0, то направляющий столбец А₃ направляющая строка- вторая, направляющий элемент а₂₃ = • Выполним очередной шаг преобразования, получим еще одну таблицу (табл. 10.5).

Таблица 10.5

С
	Bx	A0	A1	A2	A3	A4	A5
	x1
	x4						-1
	X2

Поскольку в индексной строке все элементы положительны, это означает, что найдено оптимальное решение х₁₀= 2000, х₂₀ = 6000, х₃₀ = 2000. Искомое значение целевой функции равно 4 х₁ + Зх₂= 26000.

Алгоритм симплекс-метода сводится к следующему.

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

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

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

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

5. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Симплекс-таблица преобразована следующим образом (табл. 10.4):

17. Элемент табл. 10.4, соответствующий разрешающему элементу табл. 10.3, равен обратной величине разрешающего элемента.

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

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

9. Остальные элементы вычисляются по правилу прямоугольника: мысленно вычерчиваем прямоугольник в табл. 10.3, одна вершина которого совпадает с разрешающим элементом, а другая - с элементом, образ которого мы ищем; остальные две вершины определяются однозначно. Тогда искомый элемент из табл. 10.4 будет равен соответствующему элементу табл. 10.3 минус дробь, в знаменателе которой стоит разрешающий элемент, а в числителе - произведение элементов из двух неиспользованных вершин прямоугольника.

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

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

Лекция 11. Двойственная задача линейного программирования

Двойственная задача в линейном программировании строится по формальным правилам на базе другой задачи линейного программирования, называемой основной.

Например, если основная задача имеет вид

Ах ≤b, х≥0, f (с,х) → max, (11.1)

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

А^Ту≥ с, у≤0, f(b, у) → min. (11.2)

Здесь х = (x₁,х₂,...,х_n); b = (b₁, b₂,…,b_т); с = (с₁, с₂,..., с_n); у = (y₁,y₂,... ,у_m);

f (c,x)= (11.3)

(b,y)= транспонированная матрица A.

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

Отношение между прямой и двойственной задачами находи выражение в виде следующих правил:

1) если прямая задача является задачей максимизации, то двойственная задача будет задачей минимизации и наоборот;

2) коэффициенты целевой функции прямой задачи с = (с₁, с₂,..., с_n) становятся свободными членами ограничений двойственной задачи;

3) свободные члены ограничения прямой задачи b = (b₁, b₂,…,b_т) становятся свободными членами целевой функции двойственной задачи;

4) матрицу ограничений двойственной задачи получают транспонированием матрицы ограничения прямой задачи;

5) знаки неравенств в ограничениях изменяются на обратные;

6) число ограничений прямой задачи равно числу переменных двойственной задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи.

Основная теорема двойственности:

Либо обе задачи двойственной пары разрешимы, и тогда (с, х*) = (b, у*), либо обе задачи не имеют решения. Здесь х*,у* - оптимальные планы пары двойственных задач.

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

Содержательный анализ двойственной задачи, в том числе и неизвестных у₁ у₂,..., у_m, полностью определяется содержательным смыслом прямой задачи.

Так, например, если основная задача (11.1) является задачей производственного планирования, где А - технологическая матрица, b _i - количество i-го ресурса, x _j - объем выпуска j- го продукта, i = 1, 2,... m, j = 1, 2,... n, то целью решения двойственной задачи (11.2) оказывается нахождение так называемых двойственных оценок ресурсов y_i, которые также называют маргинальными (предельными) данными ресурсов.

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

Если маргинальные цены не превосходят рыночных (у_i *≤ q _i, i =1,2,..., m), то производство, для которого они были рассчитаны, не сможет получить прибыль р от своей производственной деятельности: для любого плана выпуска x.

р(х) = (с, х) - (b, q) ≤, (с, х*) - (b, q) ≤ (с, х*) - (b. у *) = 0.

И, наоборот, если у_i * > q _i, i = 1, 2,..., т, то реализация оптимального производственного плана х* принесет положительную прибыль.

р(х*) = (с, х*) - (b, q) = (А, у*) - (b, q) = (b, y*-q)> 0,

размер которой ограничивается: а) средствами, выделяемым на закупку ресурсов; b) объемом рынка ресурсов; с) технологическими условиями производства.

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

В частности, следующее важное утверждение:

Если задача линейного программирования не вырождена и С(х*) представляет собой максимум ее линейной формы при заданных ограничениях, то дс(х*)/дb_i = у_i*, i = 1,2,..., т.

Таким образом, с математической точки зрения оптимальные оценки определяют влияние свободных членов b, условий-ограничений на оптимальную величину целевой функции. Иными словами, вычисление наряду с оптимальным планом х* = (х₁*, х₂*,..., х_n*) связанных с ним оптимальных оценок у* = {у₁*, у₂*,..., y_т*) позволяет ввести относительную важность отдельных ресурсов (b₁*,b₂*..... b_m*) для достижения поставленной цели (максимизации ).

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

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

Дата добавления: 2017-02-01