Приложение 3В. Линейное программирование

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

Линейное программирование можно формально определить как метод оптимизации (т.е. максимизации или минимизации) линейной функции нескольких переменных, имеющих комплекс линейных ограничений. Задачи линейного программирования решаются с использованием операций матричной алгебры методом, известным как симплексный. Поскольку соотношения будут линейными, задачу с двумя переменными также можно решать графически[14]. Графический метод практически не используется для решения реальных задач линейного программирования, однако он очень полезен для разъяснения базовых концепций, методов и элементарной геометрии линейного программирования. Именно поэтому, прежде чем излагать алгебраическую технику симплексного метода, мы графически решим задачу с двумя переменными.

Графическая иллюстрация: задача

линейного программирования с двумя переменными

Гончарное предприятие «Wayside Pottery» выпускает два вида глиняной посуды. Первый - это простой глиняный горшок с упроченным ободком. Второй - это меньшая по размеру и более изящная ваза с ручками и орнаментом по бокам. Для изготовления простого глиняного горшка требуются 4 фунта глины и 1 ч работы,, а его реализация приносит 4 долл, прибыли. Для изготовления вазы требуются 3 фунта глины и 2 ч работы. Прибыль от реализации вазы составляет'5 долл. На фирме 40 ч в неделю работает один гончар; допустимый расход глины составляет 120 фунтов в неделю. Сколько горшков и ваз нужно изготовить в неделю, чтобы максимизировать прибыли предприятия?

Решение

Прежде всего следует построить хорошую модель линейного программирования.

Шаг 1. Определение переменных.

Пусть

- количество простых глиняных горшков, производимых за день;

хі — количество ваз, производимых за день.

Шаг 2. Определение целевой функции. Каждый горшок дает 4 долл, прибыли, а каждая ваза - 5 долл. Цель, Z, состоящая в максимизации прибыли, выражается как

Шаг 3. Определение ограничений.

а. Ограничение по труду. Изготовляя горшки или вазы, гончар будет работать максимум 40 ч в неделю. Он может работать меньше, но не больше. Каждый горшок требует 1 ч работы, а каждая ваза -2 ч. Соответственно

б. Ограничение по материалам. Гончар имеет максимум 120 фунтов глины в неделю, расходуемой на производство как горшков, так и ваз. Каждый горшок требует 4 фунтов глины, а каждая ваза - 3 фунтов. Соответственно

Шаг 4. Введение ограничений на значение переменных. Физически невозможно произвести отрицательное количество горшков или ваз. Соответственно

Шаг 5. Построение горизонтальной и вертикальной оси графика. Обозначим горизонтальную ось х, а вертикальную ось — х2. Эти оси определяют границы неотрицательных ограничений. Все точки, лежащие выше горизонтальной оси и справа от вертикальной оси, будут удовлетворять этим ограничениям (рис. ЗІ1.1).

Рис. ЗВ.1. Неотрицательные ограничения

Шаг 6. Построение линии, отражающей первое ограничение. Ограничение по труду выражается неравенством х, + 2хг < 40. Если х2 = 0, то х, < 40, и х( = 40 дает точку пересечения с осью X. Если xt = 0, то х, < 20, и х2 = 20 дает точку, пересечения с осью У. Тогда линия х{ + 2х2 = 40, проведенная между двумя этими точками пересечения, даст верхнюю границу затененной зоны, представленной на рис.

Рис. ЗВ.2. Ограничение по труду

Шаг 7. Построение линии, отражающей второе ограничение. Ограничение по материалам выражается неравенством 4х, + Зх2 < 120. Если х2 = 0, то х, < 30, и х, = 30 дает точку пересечения с осью X. Если х, = 0, то х2 < 40, и х2 = 40 дает точку пересечения с осью Y. Мы проводим линию 4х, + Зх2 = 120 между этими точками пересечения (рис. 35.3).

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

После выполнения шага 7 линия ограничения по материалам пересекает линию ограничения по труду в точке с координатами (24, 8), как это показано на графике, представленном на рис. 35.3. Эти координаты можно найти, решив одновременно оба уравнения:

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

На рис. ЗА4 проиллюстрирован базовый принцип решения задач линейного программирования: проводя параллельные линии, выражающие различные уровни целевой функции Z = 4х, + 5х2, мы получаем решения в углу области допустимых решений. I

Рис. ЗВ. 4. Допустимые решения

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

целевой функции не будет лежать в области допустимых решений. Это демонстрирует линия 4*, + 5х2 = 160.

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

Симплексный метод

Количественное решение задачи линейного программирования симплексным методом вручную или на ЭВЙ имеет два главных преимущества: 1) позволяет получить решение задачи с тремя и более переменными, ибо метод не ограничен трехмерным пространством; 2) значения дополнительных переменных в конечной форме уравнения дают чрезвычайно важную информацию для принятия решения.

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

Первый шаг в решении этой задачи состоит в том, чтобы преобразовать неравенства в уравнения.

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

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

Z = 4х, + 5х2 — МАХ — МА2.

Теперь мы имеем неопределенную систему из четырех уравнений с восьмью переменными: xr х2, sr s2, s3, s4, A\, Av Расхождение между числом переменных и числом уравнений делает их однозначное решение невозможным. Выполняемый вручную или с использованием ЭВМ симплексный метод дает решение задачи для п переменных, где п равно числу ограничений. Каждый раз набор этих переменных изменяется за счет замены одной переменной другой.

Симплексный метод изменяет базисные допустимые решения за счет ряда операций по строкам в табличном формате, называемом «табло». Для того чтобы начать решение симплексным методом, присвоим нулевое значение функциональным переменным, х, чтобы получить начальное базисное допустимое решение. Начальное табло (итерация 0) имеет вид, представленный в табл. Зі?. 1.

Таблица ЗВ. 1

Начальное симплексное табло (итерация 0)

1 Каноническое построение матрицы имеет место, когда каждое число главной диагонвли матрицы п х п равно +1.

Поясненне к начальному табло. Вторая строка содержит заголовки столбцов, включающих все переменные задачи. Строка содержит коэффициенты переменных целевой функции. Они остаются постоянными во всех итерациях. Коэффициенты переменных ограничений показаны в ячейках матрицы п х т, где п равно числу ограничений (четыре строки в нашем случае), а т равно общему числу переменных, включая функциональные переменные, дополнительные переменные и искусственные переменные (восемь столбцов в нашем случае). Каждую ячейку матрицы можно обозначить как а.., где индекс і относится к строке, a j указывает столбец. Правую границу матрицы составляет столбец, обозначенный как Ьг Он содержит правые части ограничений. Назначение столбца, обозначенного как Л( /а.е, будет пояснено далее.

Столбец «базис» показывает, какие базисные переменные входят в текущее базисное допустимое решение. Каждая базисная переменная в своем столбце будет иметь коэффициент 1. Слева от столбца «базис» находится столбец Сь, куда введены коэффициенты базисных переменных, входящих в целевую функцию. Дополнительные переменные входят в целевую функцию с нулевыми коэффициентами, искусственные переменные — с коэффициентами плюс или минус М в зависимости от того, будем ли мы максимизировать или минимизировать целевую функцию. В данном случае мы ее максимизируем, так что знаком будет минус.

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

В начальном табло Z, вычисляется как 0(1) + 0(4) + {-М){ 1) + (-Л/)(0) = -М\ Z2 вычисляется как 0(2) + 0(3) + {—М){0) + {—М){ 1) = -М. Остальные столбцы, включая столбец Л(, вычисляются аналогично. Значение Z в столбце Ь. дает текущее значение целевой функции. В начальном табло это значение равно нулю, поскольку все функциональные переменные приравнены к нему.

Строка Cj — Zj содержит критерии оптимального решения. Если мы максимизируем целевую функцию, то решение будет оптимальным, когда все С — Zf будут нулевыми или отрицательными, а если минимизируем, то решение будет оптимальным, когда все С — Z будут нулевыми или положительными. В данном примере мы максимизируем функцию, и в строке С. — Z присутствуют два положительных элемента. Это означает, что мы не вышли на оптимум и поэтому должны выбрать новый базис.

Выбор нового базиса. Переход к новому базису осуществляется путем замены определенной базисной переменной некоторой небазисной, при этом одна переменная вводится в базис, а другая выводится из него. Сначала выбирается вводимая переменная, и это должна быть та, которая быстрее других наращивает значения Z. Ее определяет наибольшее положительное число в строке C. — Zj. В нашем примере она будет находиться в столбце х2, как это отмечено вертикальной стрелкой в матрице, представленной в табл. ЗВ.2.

Величина, на которую может быть увеличена Z при введении переменной, ограничена значением выводимой переменной, которая может быть уменьшена до нуля, но не может стать отрицательной. Предел приращения от вводимой переменной будет равен отношению Л( к коэффициенту вводимой переменной, аІе, где индекс е указывает на столбец вводимой переменной. Это выражение называется min-отношением. Если а.с равно нулю, то min-отношение будет стремиться к бесконечности. Если аІе отрицательно, то min-отношение также будет отрицательным или нулевым, в зависимости от значения Ь.. В любом из этих случаев оно не определяет вводимую переменную. Для каждой строки существует одно min-отношение. Для данного иллюстративного при-

мера min-отношение помещено в столбец b/afe, как показано в матрице, представленной в табл. ЗВ.2, однако оно может не входить в распечатку, полученную в результате использования компьютерной программы.

Таблица ЪВ.2

Выбор вводимой и выводимой переменных

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

В строке s, значение коэффициента при х2 равно 2. Для того чтобы изменить коэффициент на 0, мы умножаем новую строку х2 на 2 и полученное значение вычитаем из строки s '.

Для строки s2 мы умножаем новую строку х2 на 3 и вычитаем полученное значение из строки s2.

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

Новое табло, полученное в результате таких операций над строками, показано в матрице, представленной в табл. ЗВ.З. Это табло показывает, что значение Сь для строки х2 равняется 5. Это будет коэффициент при х2 в целевой функции. Он используется для вычисления новых значений строк Zj и С*. - Z. Столбец bt показывает, что Z остается равным нулю, что означает отсутствие увеличения целевой функции, однако строка - Zf теперь показывает, что искусственные переменные сводятся к нулю. Это позволяет эффективно удалить искусственные переменные из целевой функции, что желательно сделать как можно быстрее. По этой причине искусственным переменным дается значение М, где М — очень большое число. Значение С — Z. для второй искусственной переменной будет сведено к нулю при следующей итерации. [15]

Таблица ЪВ.Ъ

Табло после 1-й итерации