Тема 2: симплексный метод. Общее понятие о симплексном методе. Симплексные преобразования

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

Давайте сперва приведем основные правила симплекс-метода, а затем решим этим методом какой-нибудь пример.

Итак. АЛГОРИТМ решения задач линейного программирования симплексным методом (при решении задачи на минимум):

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

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

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

4. Осуществляем переход к новому базису, исключая из старого базиса переменную, соответствующую разрешающей строке, и вводя вместо нее переменную, которая соответствует разрешающему столбцу. Составляется новая симплекс-таблица, соответствующая новому базису.

5. Возвращаемся к второму шагу алгоритма.

При решении задачи на максимум – наоборот.

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

Рассмотрим условный пример.

На предприятие по производству запасных частей для автомобилей поступило три сорта материалов: первого - 1200, второго - 300, третьего - 800 кг. Эти материалы могут быть использованы для выпуска запасных частей трех видов.

На производство запасной части первого вида требуется 5 кг материала первого сорта и 4 кг второго сорта. Материал третьего сорта при производстве запасных частей первого вида не используется. На производство одной запасной части второго вида необходимо израсходовать материала первого сорта - 5 кг, второй сорт не используют и третьего сорта - 2 кг. На единицу запасных частей третьего вида расходуют материала первого сорта 2, второго - 3, третьего - 4,8 кг.

От реализации одной запасной части первого вида предприятие получит 5 р. прибыли, второго вида - 8 и третьего вида - 6 р.

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

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

Обозначим объем производства запасных частей первого вида через x1, второго – x2, третьего – x3. Переменные x1, x2, x3 не могут быть отрицательными, так как это противоречило бы их экономическому смыслу, поскольку объем производства не бывает отрицательным.

Потребность в материале первого сорта составит

5 x1 + 5 x2 + 2 x3.

Этот расход материалов не должен превышать их наличия, т.е. 1200 кг. Рассуждая аналогично, можно записать ограничение по расходу материалов второго и третьего сортов соответственно:

4 x1 + 3 x3 ≤ 300;

2 x2 + 4,8 x3 ≤ 800.

Прибыль, полученная от реализации запасных частей, L(x) = 5 x1+ 8 x2+ 6 x3.

Таким образом, задача сводится к определению значений x1, x2, x3 при условии, что

5 x1 + 5 x2 +2 x3 ≤ 1200;

4 x1 + 3 x3 ≤ 300;

2 x2 + 4,8 x3 ≤800;

x1 ≥0, x2 ≥0, x3≥0,

которые максимизируют линейную функцию

L(x) = 5 x1+ 8 x2+ 6 x3.

Чтобы приступить к решению данной задачи симплексным методом, необходимо определить первое допустимое базисное решение. Для этого неравенства преобразуют в равенства путем прибавления в левую часть неравенств дополнительных переменных x4, x5, x6 c коэффициентом, равным единице, и нулевыми коэффициентами в целевой функции:

5 x1 + 5 x2 + 2 x3 + x4 = 1200;

4 x1 + 3 x3 + x5 = 300;

2 x2 + 4,8 x3 + x6 = 800;

x1 ≥0, x2 ≥0, x3 ≥0, x4 ≥0, x5 ≥0, x6 ≥0,

L(x) = 5 x1 + 8 x2 + 6 x3 + 0 x4 + 0 x5 + 0 x6 → max.

Дополнительные переменные рассматриваются как показатели недоиспользования имеющихся материалов: первого сорта - x4, второго - x5, третьего - x6.

Дополнительные переменные x4, x5, x6 не способствуют увеличению прибыли, так как недоиспользованное сырье не участвует в производстве. Поэтому в линейной форме L(x) эти переменные записывают с коэффициентом прибыли, равным нулю.

При решении задачи относительно дополнительных переменных возможны три случая.

Случай 1 - дополнительная переменная равна нулю (xn+i; i = 1, m). Это значит, что при производстве используются все материалы (остатков нет).

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

x4 = 1200 - (5 x1 + 5 x2 + 2 x3).

Случай 3 - дополнительная переменная равна запасам материалов, сырье используется неполностью, а основные переменные задачи (x1, x2, x3) принимают нулевые значения. Например, по материалам первого сорта это значит, что

x4 = 1200; x1 = 0, x2 = 0, x3 = 0.

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

Решение задачи начинают с определения первого базисного допустимого плана. За базисные переменные принимаются дополнительные переменные x4, x5, x6, так как каждая из них входит лишь в одно уравнение с коэффициентами, равными единице, которые образуют единичную матрицу.

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

x4 = 1200 - (5 x1 + 5 x2 + 2 x3);

x5 = 300 - (4 x1 + 3 x3);

x6 = 800 - (2 x2 + 4,8 x3).

Затем подставляют их значения в линейную форму L(x). Но в связи с тем, что дополнительные переменные входят в линейную форму с нулевыми коэффициентами, для базиса из дополнительных переменных она всегда равна нулю.

В нашем примере первым базисным решением является план: x1 = 0, x2 = 0, x3 = 0; x4 = 1200; x5 = 300; x6 = 800, который является допустимым, поскольку значения переменных удовлетворяют системе уравнений, отражающей условия задачи, и они неотрицательны.

С экономической точки зрения полученное первое базисное решение означает, что производство еще не начато и запасы материалов находятся на складе. Предприятие никакой продукции не выпускает (x1 = 0, x2 = 0, x3 = 0) и, естественно, прибыли не имеет. Действительно, если подставить значения переменных в линейную форму, она окажется равной нулю.

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

В первую таблицу заносится первоначальное допустимое базисное решение.

Рассмотрим как составляется симплексная таблица.

Таблица 1

ci	Базисные переменные	cj
План	x1	x2	x3	x4	x5	x6
	x4
	x5
	x6				4,8
Индексная строка zj- cj	L(x) = 0	-5	-8	-6

ci - коэффициенты линейной формы при переменных, вошедших в базис;

cj - коэффициенты линейной формы, включая и базисные переменные;

∆ j - оценка индексной строки, которая характеризует эффективность включения в план (базис) j- й переменной и показывает, насколько изменится целевая функция на каждую единицу переменной.

В последней строке таблицы оценка ∆ j - определяется по правилу: элементы столбца c_i -умножаются на соответствующие коэффициенты столбца, для которого определяется оценка, полученные произведения суммируются и из этой суммы вычитается значение коэффициента c_j - при данной переменной в линейной форме.

Для столбца, соответствующего переменной x₁, оценка составит

∆₁ = 0*5 +0*4 +0*0 -5 = -5;

для переменной x2

∆₂ = 0*5 +0*0 +0*2 -8 = -8;

для переменной x3

∆₃ = 0*2 +0*3 +0*4,8 -6 = -6.

Для базисных переменных (в табл. это x4, x5, x6) оценки всегда равны нулю, так как эти переменные уже вошли в план и определять их эффективность по отношению к плану не требуется.

Первым шагом в анализе первоначального допустимого базисного решения является проверка его на оптимальность. Поскольку оценки ∆ j характеризуют эффективность технологических способов по отношению к сложившейся структуре производства, они же и являются показателями оптимальности плана. Так, из первой симплексной таблицы следует, что если включить в план производство продукции первого вида (x₁), то на каждую единицу предприятие получит 5 р. прибыли; второго вида (x₂) - 8 р.; третьего вида (x₃) - 6 р. Наибольшую прибыль в расчете на единицу продукции предприятие получит при производстве продукции второго вида, которому в индексной строке таблицы соответствует наибольшая по абсолютной величине отрицательная оценка. Эту продукцию следует производить в первую очередь.

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

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

Базисных переменных должно быть столько, сколько уравнений в системе ограничений. Поэтому, чтобы ввести новую переменную, надо заменить ею какую-то из базисных.

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

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

1200 / 5 = 240

300 / 0 =?

800 / 2 = 400

В нашем примере (см. табл. 1) выводим из базиса переменную x₄, ав базис вводим переменную x₂, разрешающий элемент → 5.

Переход к новому базису осуществляется преобразованием симплексной таблицы и составлением новой (табл. 2).

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

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

Преобразованные элементы записываются в соответствующие клетки второй симплексной таблицы.

Для сокращения расчетов следует иметь в виду следующее:

в новой таблице на месте разрешающего элемента всегда будет единица, а остальные элементы разрешающего столбца - нули;

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

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

В нашем примере во вторую симплексную таблицу перейдут без изменений вторая строка, пятый (x₅) и шестой (x₆) столбцы.

Таблица 2

ci	Базисные переменные	cj
План	x1	x2	x3	x4	x5	x6
	x2				0,4	0,2
	x5
	x6					-0,4
Индексная строка zj - cj	L(x) = 1920			-2,8	1,6

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

x₁ = 0, x₂ = 240, x₃ = 0, x₄ = 0, x₅ = 300, x₆ = 320.

Экономический смысл его в том, что рекомендуется производить запасных частей второго вида 240 ед. и предприятие получит от этого прибыль 1920 р. При этом материалы первого сорта будут использованы полностью, остатки материалов второго и третьего сортов составят соответственно 300 и 320 ед., т.е. материалы второго сорта не используются совсем, а материалов третьего сорта будет израсходовано 480 ед. (800 - 320).

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

Наименьшее отношение свободных членов к положительным элементам разрешающего столбца (320:4 = 80) соответствует базисной переменной x₆ (разрешающая строка). Разрешающий элемент 4. Следовательно, для дальнейшего улучшения плана, представленного во второй симплексной таблице, необходимо ввести в базис переменную x₃, а вывести x₆.

Заполним третью симплексную таблицу (табл. 3), используя правило деления элементов разрешающей строки на разрешающий элемент, правило прямоугольника и правило расчета оценок индексной строки. Столбцы, соответствующие переменным x₂ и x₅, в новую таблицу перейдут без изменений.

В третьей симплексной таблице в индексной строке нет отрицательных оценок. Следовательно, полученный план улучшен быть не может и является оптимальным, линейная форма L(x) достигает своего максимального значения. Оптимальное решение: x₁ = 0; x₂ = 208; x₃ = 80; x₄ = 0; x₅ = 60; x₆ = 0.

Экономический смысл оптимального решения таков: чтобы получить максимальную прибыль 2144 р., предприятие должно производить запасных частей второго вида 208 ед., запасных частей третьего вида -80 ед. Запасные части первого вида производить нецелесообразно; x₅ = 60 означает, что 60 ед. сырья второго вида осталось неиспользованным. Материалы первого и третьего видов используются полностью, так как x₄ = 0, x₆ = 0, т.е. остатков этих материалов нет.

Таблица 3

ci	Базисные переменные	cj
План	x1	x2	x3	x4	x5	x6
	x2		1,2			0,24		-0,1
	x5		5,5			0,30		-0,75
	x3		-0,5			-0,1		0,25
Индексная строка zj - cj	L(x) = 2144	1,6			1,32		0,7

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

5*0 +5*208 + 2*80 + 0 = 1200;

4*0 + 3*80 +60 = 300;

2*208 +4,8*80 + 0 = 80;

L(x) = 8*280 +6*80 = 2144.

Значения переменных удовлетворяют условиям задачи, следовательно, решение правильно.

Ценную информацию представляют коэффициенты и оценки оптимального плана (см. табл. 3).

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

Например, если по какой-либо причине предприятию потребуется наладить производство запасных частей первого вида, то на каждую единицу их производства необходимо сократить производство запасных частей второго вида на 1,2 ед., расход материалов второго сорта увеличится на 5,5 ед., производство запасных частей третьего вида необходимо увеличить на 0,5 ед. От этого предприятие понесет убыток 1,6 р.

Такое положение обусловлено следующим. Производство запасных частей второго вида сократится на 1,2 ед., а каждая единица приносит предприятию прибыль 8 р., значит, за счет сокращения производства будет потеряно 9,6 р. (1,2*8) прибыли. Производство запасных частей третьего вида увеличится на 0,5 ед., а каждая единица дает предприятию 6 р. прибыли, следовательно, прибыль увеличится на 3 р. При этом будет произведена и одна запасная часть первого вида, от реализации которой предприятие получит 5 р. прибыли. В итоге при производстве каждой запасной части первого вида предприятие потеряет 1,6 р.

(-9,6 + 5 + 3).

Исходя из ограниченности ресурсов второго сорта, предприятие сможет произвести запасных частей первого вида около 11 ед. (60:5,5). Общие потери прибыли при этом составят 176 р. (1,6*11).

Установим, почему на 5,5 ед. увеличится расход материалов второго сорта. Эти материалы расходуются на производство запасных частей первого и третьего видов (см. условие задачи). На одну запасную часть первого вида расходуют 4 ед., а третьего вида - 3 ед. материала второго сорта. Производство запасных частей первого вида увеличится на единицу, третьего вида - на 0,5 ед. Общий расход материала этого вида увеличится на 5,5 ед. (4 + 3*0,5).

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

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

Для дополнительных переменных x4, x5, x6 (количество недоиспользованных материалов соответственно первого, второго и третьего сортов) коэффициенты замещения показывают, как следует изменить интенсивность запланированных технологических способов при дополнительном выделении единицы соответствующего сорта материала, чтобы получить изменение целевой функции на величину оценки, указанной в индексной строке так, чтобы увеличить прибыль предприятия на 1,32 р. При дополнительном выделении единицы материала первого сорта x4 необходимо увеличить производство продукции второго вида на 0,24 ед., сократить производство продукции третьего вида на 0,1 ед., при этом высвободятся материалы второго сорта в количестве 0,3 ед.

При дополнительном выделении, например, единицы материалов третьего сорта необходимо сократить на 0,1 ед. производство продукции второго вида, увеличить расход (уменьшить запас) материалов второго сорта на 0,75 ед. и увеличить производство продукции третьего вида на 0,25 ед. Прибыль предприятия от этого увеличится на 0,7р.

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

Оценки индексной строки для основных переменных, не вошедших в оптимальный план, показывают, сколько прибыли пришлось бы потерять, если была бы произведена единица продукции соответствующего вида. Для дополнительных переменных эти оценки показывают, сколько единиц прибыли приносит единица материалов данного вида при производстве продукции. Так, единица материалов первого вида приносит предприятию 1,32р., третьего вида - 0,75 р. прибыли. Оценка для сырья второго вида равна нулю, это означает, что ресурсы сырья второго вида не лимитируют производство, имеются его излишки.

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