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

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

Название метода произошло от названия геометрической фигуры, уравнение которой было использовано создателем метода Дж. Данцигом в одном из доказательств. Симплексом тела в k-мерном пространстве называют совокупность k+1 его вершин. Так, для плоскости при k=2 симплексом будет треугольник с его тремя вершинами, при k=3 - четырехгранник и т.д.

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

Допустимый план – такой возможный вариант решения, который удовлетворяет всем заданным ограничениям задачи, но не обязательно является оптимальным (иные его названия опорный или базисный план). Исходя из понятий, сформированных при рассмотрении геометрической интерпретации задач линейного программирования, целесообразно чтобы исходный план находился в одной из вершин области допустимых решений. Если окажется, что он оптимален, расчет на этом заканчивается, если нет – по определенным формальным правилам переходят к некоторому очередному плану, который в свою очередь может оказаться или оптимальным или, по крайней мере, будет более близким к нему, чем предыдущий. В конце концов за конечное число шагов, при правильно сформулированной постановке задачи и построенной математической модели, будет получен оптимальный вариант решения. Вновь обращаясь к геометрической интерпретации, можно заметить, что нахождение решения связано с перебором вершин многоугольника ОДР. Вычислительный алгоритм организован таким образом, что в процессе решения, осуществляется не полный, а направленный перебор вершин, в процессе которого на каждом шаге обязательно осуществляется переход от вершины с меньшим значением целевой функции к вершине с большим ее значением (при решении задачи на максимум). Можно сказать, что на каждом шаге производится “улучшение плана”, т.е. последовательное приближение решения к оптимальному его варианту. В последующем, для упрощения, все рассмотрение процесса решения будем вести применительно к максимизации значения целевой функции. Очевидно, что решение задач на минимум осуществляется по той же схеме.

Различные методы последовательного улучшения плана различаются своими алгоритмами. В частности, создано несколько модификаций симплексных алгоритмов. Мы остановимся на изучении одного из них. Для большей наглядности представим процесс решения в виде блок-схемы (рис.2.7):

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

Получить исходный план

нет

да

План оптимален?

да

нет

нет

да

Принятие решения

Рис. 2.7

Сущность симплексного метода применительно к излагаемому алгоритму рассмотрим на приведенном ниже примере.

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

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

С целью лучшей организации производства, исходя из разной производительности станков типа С¹ и С², создаются комплекты оборудования двух видов. Первый из них, включающий 2 станка типа А, 1 – типа В и 4 – типа С¹, имеет производительность 20 изделий в час. Второй – состоящий из 2 станков типа А, 2 – типа В и 4 – типа С², имеет производительность 30 изделий в час. Парк станков состоит из 12 станков типа А, 8 – типа В, 16 – типа С¹ и 12 – типа С². Требуется распределить имеющиеся станки по комплектам так, чтобы обеспечить максимальную их производительность при производстве планируемого изделия.

Составление математической модели.

С целью большей наглядности сведем исходные данные в таблицу (табл.2.3).

Таблица 2.3

Типы станков	Количество станков в 1 комплекте	Парк станков
I вида	II вида
А
В
С1
С2
Производ. комплекта

Для составления математической модели обозначим через х₁ количество комплектов первого вида, х₂ – второго.

Составление модели начнем с введения ограничения на использование станков типа А. Как следует из табл. 2.3 в один комплект первого вида входит 2 станка рассматриваемого типа, а для х₁ комплектов первого вида потребуется 2х₁ станков. Аналогично – в х₂ комплектов второго вида будет включено 2х₂ станков типа А. Очевидно, что общее количество этих станков в комплекте обоих видов не может превышать 12 единиц. Математически рассмотренное ограничение запишется:

2х₁ + 2х₂ ≤ 12

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

Аналогично можно составить ограничения для каждого из остальных типов станков и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид:

2х₁+2х₂ ≤ 12

х₁+2х₂ ≤ 8

4х₁ ≤ 16 (2.17)

4х₂ ≤ 12

Z = 20х₁ + 30х₂

х₁≥0; х₂≥0

Получение исходного плана.

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

2х₁+2х₂+1у₁=12

1х₁+2х₂+1у₂=8 (2.18)

4х₁+0х₂+1у₃=16

0х₁+4х₂+1у₄=12

Записанная в таком виде система включает четыре уравнения (m=4) и шесть переменных (n=6), т.е. поставленная задача может рассматриваться как задача линейного программирования. Из разности n-m=6-4=2 следует, что две любые переменные могут быть выбраны в качестве свободных. Им могут быть присвоены любые числовые значения. Остальные четыре переменные являются базисными, т.е. они могут быть выражены через свободные, и их значения вычисляются в зависимости от выбранных значений последних.

Примем в рассматриваемой задаче, в качестве свободных переменные х₁ и х₂ и приравняем их нулю. Выразим базисные переменные через свободные. В результате система ограничений (2.18) примет вид:

у₁=12-(2х₁+2х₂+0у₂+0у₃+0у₄)

у₂=8-(1х₁+2х₂+0у₁+0у₃+0у₄) (2.19)

у₃=16-(4х₁+0х₂+0у₁+0у₂+0у₄)

у₄=12-(0х₁+4х₂+0у₁+0у₂+0у₃).

Очевидно, что, при условии равенства нулю переменных х_j, переменные y_i (i=1,2,…m) будут равны свободным членам уравнений. Обратим внимание на то, что дополнительные переменные у_i представляют собой остаток неиспользованных ресурсов. А так как в рассматриваемом случае сформированных комплектов нет (х_j=0), то значения у_i соответствуют количеству имеющихся станков.

Целевая функция, исходя из записи системы ограничений (2.18), может быть записана:

Z = 20х₁ + 30х₂ + 0у ₁+ 0у₂ + 0у₃ + 0у₄ (2.20)

Запишем данное уравнение в виде:

Z = 0 - (-20х₁ - 30х₂ - 0у ₁- 0у₂ - 0у₃ - 0у₄) (2.21)

Исходя из записи системы ограничений (2.19) и уравнения целевой функции (2.21) строим симплексную таблицу, которая представляет собой исходный вариант решения (табл. 2.4)

Таблица 2.4

№ строк	План	Коэффициенты при переменных
х1	х2	у1	у2	у3	у4
	у1
	у2
	у3
	у3
	Z		-20	-30

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

В двух нижних клетках раздела Плануказывается обозначение целевой функции – Z и ее значение, соответствующее рассматриваемому варианту решения. Эта величина вычисляется при подстановке значений переменных, включенных в план, в уравнение целевой функции (2.20). Поскольку все переменные у_i включены сюда с нулевыми значениями коэффициентов, а переменные х_j приравнены нулю, то очевидно, что и Z=0. Правая часть таблицы заполняется коэффициенты при переменных, взятыми из системы ограничений (2.19), а строка целевой функции – коэффициентами из уравнений (2.21). Смысл записи такого вида в строке целевой функции будет рассмотрена позднее.

Обращаясь к геометрической интерпретации, можно видеть, что вариант решения, соответствующий исходному плану, находится в вершине ОДР расположенной в начале координат (х₁=х₂=0, Z=0).

Исследование плана.

Правила и последовательность исследования едины для любого варианта решения (плана), начиная с исходного.

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

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

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

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

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

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

Получение “улучшенного” варианта плана.

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

а) определение свободной переменной, подлежащей включению в план;

б) определение базисной переменной, подлежащей исключению из плана, производство замены этих переменных;

в) расчет новых значений всех числовых показателей симплексной таблицы.

Рассмотрим более подробно последовательность выполнения каждого шага алгоритма.

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

б) Нахождение переменной, подлежащей исключению из плана, связано с отысканием ответа на вопрос: сколько комплектов второго типа можно ввести в план? Этот шаг в алгоритме симплекс-метода называется отысканием “узкого места”, которое ограничивает количество комплектов второго типа.

Очевидно, количество комплектов того или другого вида зависит от наличия станков рассматриваемого типа, входящих в комплект.

Для определения узкого места необходимо числа столбца плана разделить на коэффициенты столбца х₂ и из полученных частных выбрать наименьшее

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

Таким образом, узкое место определяет четвертая строка. Назовем ее ключевой строкой, а число 4 – генеральным элементом. Переменной, исключаемой из плана, является переменная у₄ и в столбце План вместо у₄ следует записать х₂,

Генеральный элемент в анализируемой таблице выделяется.

Теперь можно приступить к формированию следующей симплексной таблицы – нового варианта плана (табл. 2.5). В столбце базисных переменных раздела План в три верхние клетки записываются переменные из предыдущего плана, в нижнюю – переменная х₂. Во всех клетках матрицы, содержащих числовые величины (включая и строку целевой функции), производится расчет их новых значений. Новое значение целевой функции определяется по ее уравнению (2.20). Получение новых значений остальных характеристик выполняется в соответствии с приводимыми ниже правилами.

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

Таблица 2.5

№ строк	План	Коэффициенты при переменных
х1	х2	у1	у2	у3	у4
	у1							-0,5
	у2							-0,5
	у3
	х2							0,25
	Z		-20					7,5

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

Например, в строке №1 элементу со значением 12 (табл. 2.4) будет соответствовать новый элемент:

элементу 2 будет соответствовать новый элемент

и т.д.

В результате расчета новых значений всех элементов матрицы будет получен “улучшенный” вариант плана (рис 2.5), производительность по которому (вычисленное значение Z) составит 90 производимых значений.

Из второго плана следует, что при создании трех комплектов станков второго вида (х₁=0, х₂=3) останутся неиспользованными 6 станков типа А, 2 – типа В, 16 – типа С¹.

Оценим полученный план на оптимальность. На то, что он не оптимален и имеется возможность его дальнейшего “улучшения” указывает присутствие отрицательного элемента в сроке целевой функции.

Соответственно алгоритм улучшения повторяется для варианта плана, представленного в табл. 2.5. Находим ключевой столбец – х₁. Определяем узкое место: находим

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

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

Таблица 2.6

№ строк	План	Коэффициенты при переменных
х1	х2	у1	у2	у3	у4
	у1					-2		0,5
	х1							-0,5
	у3					-4
	х2							0,25
	Z							-2,5

Анализ третьего плана показывает, что производительность значительно выросла (Z=130), но план еще не оптимален: в целевой строке имеется отрицательный элемент - 2,5. Строим новую симплексную таблицу (табл. 2.7), в которой будет представлен оптимальный план.

Таблица 2.7

№ строк	План	Коэффициенты при переменных
х1	х2	у1	у2	у3	у4
	у1					-1	-0,25
	х1						0,25
	у4					-2	0,5
	х2					0,5	-0,125
	Z						1,25

В ходе оптимизации при отыскании узкого места может встретиться случай, когда таких мест окажется два или более. Так, в частности, случилось в таблице 2.6 (2:0,5=4, 8:2=4: строки у₁ и у₃ - ключевые). В простейшем случае выбирают любую из них. При строгом подходе поступают следующим образом. Следует разделить все элементы строки у₁ на 0,5, а строки у₃ на 2. Затем полученные таким путем частные сравнивают по столбцам, двигаясь слева на право, до расхождения чисел. Ключевой строкой будет та строка, в которой будет найдено меньшее число. Для рассматриваемого варианта получаем следующие частные

(первая строка)

(третья строка)

Сравнивая полученные результаты, видим, что расхождение наступает в четвертом столбце. Поскольку то в качестве ключевой следует выбрать третью строку. Легко убедиться, что если в качестве ключевой выбрать первую стоку, то оптимальный вариант остается тем же. В обоих случаях, при создании четырех комплектов первого типа (х₁=4) и второго - (х₂=2), будет достигнута максимально возможная для заданных ограничений производительность равная 140 единицам изделий в час.

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

1. Задание исходного варианта плана.

2. Проверка плана на допустимость.

План является допустимым при:

х_i0 ≥ 0 (i = 1, m).

Здесь через j=0 обозначен столбец раздела План, в котором представлены значения базисных переменных.

3. Проверка плана на оптимальность.

План оптимален при:

С_j≥0 (j=1,…, n+m)

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

При выполнении указанного условия решения задачи заканчивается. В противном случае переход к п. 4.

4. “Улучшение плана”.

а) Выбор свободной переменной, вводимой в план:

min {-C_j} (j=1, n+m)

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

б) Выбор базисной переменной, удаляют из плана:

(j = 1, m)

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

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

в) Определение генерального элемента.

Генеральный элемент находится на пересечении ключевой строки и ключевого столбца. Введем для него обозначение – Э_кк.

г) Вычисление новых значений ключевой строки:

(j = 0,…, n+m)

Здесь индексом с обозначается старое числовое значение, записанное в клетку, н – новое, т.е. вычисляемое, значение.

Задание новых значений ключевого столбца:

(i=1,…, m),

за исключением значения Э_кк, вычисляемого по правилам, установленным в п. 3г.

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

Исключение составляет вычисление значения целевой функции, которое осуществляется подстановкой в уравнение целевой функции значений переменных из раздела План.

Результатом выполнения п.п. 2-4 будет получение “улучшенного” варианта плана.

5.Возврат к п.2 алгоритма.

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

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

При планировании учитываются: трудозатраты на производство единицы продукции каждого вида (человекочасов); потребность в используемых для сборки вспомогательных материалах, изготавливаемых на рассматриваемом предприятии (кг); затраты на приобретение на других предприятиях комплектующих (блоков), необходимых для сборки (руб). Затраты ресурсов каждого вида, отнесенные к единице продукции, предельные размеры выделяемых ресурсов и прибыль от реализации единицы продукции, представлены в таблице 2.8.

Таблица 2.8

Затраты	Прод. 1	Прод. 2	Прод. 3	Прод. 4	Ресурс
Трудозатраты
Вспомогательные
Комплектующие
Прибыль

В соответствии с постановкой математическая модель задачи имеет вид:

10х₁+10х₂+10х₃+10х₄ ≤ 160

60х₁+50х₂+40х₃+30х₄ ≤ 1100

4000х₁+6000х₂+10000х₃+13000х₄ ≤ 100000

Z=60х₁+70х₂+120х₃+130х₄

х₁≥0; х₂≥0; х₃≥0; х₄≥0.

Здесь х_j количество планируемой у выпуску продукции j – того вида (j=1,2,3,4). Заметим, что для упрощения вычислений, выполняемых при решении задачи, можно обе части первого и второго ограничений разделить на 10, а третьего – на 1000:

х₁+х₂+х₃+х₄ ≤ 16

6х₁+5х₂+4х₃+3х₄ ≤ 110

4х₁+6х₂+10х₃+13х₄ ≤ 100 (2.22)

Z=60х₁+70х₂+120х₃+130х₄

х₁≥0; х₂≥0; х₃≥0; х₄≥0.

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

Таблица 2.9