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

Коротков М.

Гаврилов М.

24 апреля 2003 г.

СОДЕРЖАНИЕ 2

Содержание

1 Линейное программирование. 3

1.1 Задача............................... 3 1.2 Графический метод... .................... 6 1.3 Дополнительные переменные.................. 8 1.4 Анализ чувствительности.................... 9 2 Симплекс-метод 2.1 Стандартная форма задачи................... 2.2 Базисные решения........................ 2.3 Алгоритм симплекс-метода................... 2.4 Искусственные начальные решения.............. 2.5 Особые случаи.......................... 3 Теория симплекс-метода 3.1 Матричное представление задачи............... 3.2 Основные теоремы........................ 3.3 Обоснование симплекс-метода................. 4 Модификации симплекс-метода 4.1 Мультипликативное представление обратной матрицы (модифицированный симплекс-метод)............... 4.2 Метод решения задач с ограниченными переменными... 5 Марковские процессы с бесконечным числом этапов 6 Транспортная задача 6.1 Вспомогательные теоремы................... 6.2 Решение транспортной задачи................. 6.3 Метод потенциалов....................... 1 Линейное программирование.

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

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

Это, несколько тяжеловесное определение можно объяснить на примерах конкретных задач.

Замечание 1 (О линейных зависимостях) Следует помнить, что “полностью линейные” зависимости редко встречаются в практических задачах. Нелепо утверждать, что стоимость перевозки одной книжки составляет 50% стоимости перевозки двух книжек. Также, можно предположить что при покупке 10000 буханок хлеба потраченная сумма не в 10000 раз отличается от стоимости одной буханки. Задача оказывается линейной, если можно выбрать единицы измерения так, чтобы зависимости можно было считать линейными. (Можно предположить, что для перевозки книжек контейнерами стоимость перевозки линейно зависит от количества контейнеров) Любая задача линейного программирования включает следующие три элемента.

(i) Переменные.

(ii) Целевая функция (функция, подлежащая минимизации или максимизации) (iii) Ограничения, которым переменные должны удовлетворять.

Рассмотрим конкретный пример.

1.1 Задача Задача 1 Типография “Веселая печать” печатает книги математического и художественного содержания. На 1000 экземпляров математических книг уходит 6 тонн бумаги и 1 бочка типографской краски, а на 1000 экземпляров художественных – 4 тонны бумаги и 2 бочки краски (они тоньше и с картинками :). Причем типография может использовать не более 24 тонн бумаги и 6 бочек краски в месяц, дабы избежать протестов со стороны Greenpeace.

Ежемесячный тираж художественных книг был ограничен 2 тысячами штук (из-за отсутствия надлежащего спроса на них), кроме того, министерство образования поставило условие, чтобы тираж художественных книг превышал тираж математических не более чем на 1000 штук (дабы население повышало уровень собственного образования). Одна математическая книга приносит доход в 5 рублей, а одна художественная – 4. Типография заботится не только об уровне математического образования населения, но и о собственной выгоде и хочет максимизировать свой доход.

Выпишем данные задачи в таблицу:

математические художественные максимальный книги книги объем бумага, тонн на 1000 штук 6 4 краска, бочек на 100 штук 1 2 доход, рублей 5 Теперь попробуем в данной задаче выделить основные элементы.

(i) Переменные. Здесь это тиражи соответствующих типов книг.

x1 – ежемесячный тираж математических книг (1000 штук).

x2 – ежемесячный тираж книг художественного содержания ( штук).

(ii) Используя эти переменные мы можем построить целевую функцию.

Логично предположить, что это будет функция суммарного дохода.

z = 5x1 + 4x Эта функция измеряется в тысячах условных рублей. Таким образом задача оптимизации следующая:

Максимизировать z = 5x1 + 4x (iii) Итак, нам осталось определить последний элемент – ограничения на переменные. То есть описать ограничения на количество продукции и объем сырья.

(i) Во-первых, объем сырья (бумаги и краски) не должен превышать максимально допустимый объем. Из таблицы имеем следующее: Используется 6x1 + 4x2 тонн бумаги и x1 + 2x бочек краски. Вспомнив, что Greenpeace требует ограничить использование сырья, получаем следующие ограничения (ii) Кроме того, у нас есть ограничение на спрос (печатать не более 2000 художественных книг в месяц), которое запишется как (iii) А также ограничение со стороны минобразования; его можно сформулировать так: разность ежемесячных тиражей художественной и математической литературы не превышает единицы, то есть x2 x1 1) (iv) Еще одно, сразу неочевидное, ограничение: типография не занимается утилизацией собственной продукции, значит, она выпускает неотрицательное число книг, что запишется как x Таким образом, задача получается следующая:

Определение 2 Назовем допустимым любое решение удовлетворяющее ограничениям.

Например, решение печатать 3000 математических и 1000 художественных книг в месяц (x1 = 3; x2 = 1) будет допустимым, в чем легко удостоверится. Прибыль при этом составит 19 тысяч рублей. Итак, наша цель – нахождение оптимального допустимого решения, то есть допустимого решения максимизирующего нашу целевую функцию.

1.2 Графический метод Здесь мы рассмотрим графический метод решения задачи линейного программирования.

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

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

Далее, мы хотим максимизировать z = 5x1 + 4x2. Рассмотрим семейство соответствующих прямых. Направление возрастания функции z = 5x1 +4x2 есть перпендикуляр к прямым соответствующего семейства.

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

В нашем случае оптимальное решение соответствует точке С. То есть лучшим решением будет выпускать 3000 математических и 1500 художественных книг в месяц, получая при этом прибыль в 21000 рублей.

Таким образом, мы “выиграли” 2000 рублей “недополученной” типографией прибыли (по сравнению с первым решением).

Замечание 3 (Об угловой точке) Очевидно, что если область задана произвольным многоугольником, а максимизируемая функция имеет общий вид z = ax + by, то решение (оптимум) все равно будет достигаться в угловой точке.

1.3 Дополнительные переменные В нашем примере мы использовали неравенства (, ), кроме того все переменные предполагались неотрицательными. Теперь введем несколько дополнительных понятий.

(i) Остаточная переменная. Неравенства F c (где F – линейная комбинация переменных, а c – число) обычно можно интерпретировать как ограничения на использование некоторых ресурсов. В нашем примере неравенство 6x2 + 4x2 24 задает ограничения на использование бумаги. Для случая двух переменных неравенство – остаточная переменная. (То есть s1 можно интерпретировать как остаток соответствующего типа сырья.) (ii) Избыточная переменная. Аналогично, неравенства F c, интерпретируются, как ограничения на минимальный выпуск некоторой продукции (или минимальное использование некоторого сырья). Для случая двух переменных неравенство ax + by c можно записать в виде ax + by S1 = c, где S1 0, S1 – избыточная переменная. (Ее значение показывает избыток продукта по отношению к допустимому минимуму) (iii) Свободная переменная. Очевидно, допустима ситуация, когда переменная может принимать как положительные, так и отрицательные значения. Пусть переменная x принимает любые значения.

В таком случае представим её как x = x+ x, где x+ 0 и x 0.

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

• Изменение коэффициентов целевой функции.

Общий вид задачи: минимизировать (максимизировать) значение z = ax + by. Очевидно, что при изменении значений констант a и b решение может переместиться в другую угловую точку. Наша задача – определение интервалов изменения соответствующих параметров при сохранении решения в той же угловой точке.

Вспомним нашу задачу 1 о типографии. Оптимальным решением была точка C. При изменении коэффициентов целевой функции точка С останется точкой оптимума, пока угол наклона прямой z = c1 x1 + c2 x лежит между углами наклона прямых, точкой пересечения которых является точка С. Это прямые То есть при выполнении условия Точка С остается точкой оптимума.

• Стоимость ресурсов.

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

Легко показать, что при изменении количества бумаги от 20 до тонн решением остается точка С - точка пересечения прямых заданных ограничениями на ресурс. Отрезок [20, 36] называется интервалом осуществимости для ресурса, здесь для бумаги. “Cтоимостью” бумаги логично назвать следующую величину изменение количества соответствующего ресурса на интервале осуществимости. Для бумаги получим 750 рублей за тонну, это означает, что изменение количества доступной бумаги на 1 тонну приведен к изменению значения целевой функции на 750 рублей. Аналогично можно рассчитать стоимость краски.

Ниже мы перейдем к более общему методу решения задач линейного программирования – к симплекс-методу.

2 Симплекс-метод Из графического способа решения мы узнали, что решением всегда является угловая точка пространства решений. Этот факт важен при построении алгебраического метода решения задач линейного программирования.

2.1 Стандартная форма задачи Задача дана в стандартной форме если она удовлетворяет следующим условиям.

(i) Все ограничения – равенства с неотрицательной правой частью.

(ii) Все переменные неотрицательны.

(iii) Целевая функция минимизируется.

Следующие действия позволяют привести задачу к стандартной форме.

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

(ii) Освобождение задачи от свободных переменных Свободную переменную xj представим в виде разности двух неотрицательных переменных После решения задачи выполняется обратная подстановка.

(iii) Преобразование задачи максимизации в задачу минимизации. Осуществляется минимизация функции f = f Рассмотрим пример приведения задачи к стандартной форме.

Задача 1 Максимизировать при выполнении условий Выполним следующие действия (i) Вычтем из левой части первого неравенства избыточную переменную и домножим неравенство на 1.

(ii) Добавим остаточную переменную к левой части второго неравенства.

(iii) Выполним замену x3 = x+ x.

Таким образом получим следующую форму:

Задача 2 Максимизировать при выполнении условий 2.2 Базисные решения Записанная в стандартной форме задача линейного программирования содержит m линейных равенств и n неизвестных переменных, причем m < n. Разделим эти переменные на два множества: n m равных нулю и m, определенных как решение соответствующей системы. Если это решение единственное – назовем эти переменные базисными, а остальные – небазисными. В этом случае получившееся решение называется базисным решением. Если при этом все переменные неотрицательны, то такое решение называем допустимым, а в противном случае – недопустимым.

Несложно показать, что для свободной переменной невозможно, чтобы обе переменные ее разложения x+ и x были базисными. (То есть одна из них обязательно должна быть нулевой). Действительно, если они обе ненулевые, то решение гарантировано не единственное, так как при подстановке x+ = x+ + 1, x = x + 1 решение остается истинным.

2.3 Алгоритм симплекс-метода Доказательство нижеследующего утверждения будет дано позднее.

Утверждение 1 Решение задачи линейного программирования может быть найдено путем перебора всех базисных (допустимых) решений.

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

Рассмотрим работу этого алгоритма подробнее на примере. Вспомним задачу о типографии и запишем ее в стандартной форме.

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

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

x1 следует печатать 3000 математических книг в месяц x2 следует печатать 1500 художественных книг в месяц z доход при этом составляет 21000 рублей Замечание 1 Мы уже умеем вычислять стоимость ресурсов и рассмотрели проблему чувствительности. Теперь рассмотри вопрос о статусе ресурсов. Ресурсы бывают дефицитными (переменная ассоциируемая с соответствующим ресурсом равно 0) и недефицитными. В нашей задаче ограничения на сырье – дефицитны, а ограничения на спрос – нет.

2.4 Искусственные начальные решения По прочтении предыдущего параграфа возникает вопрос: а как получить это допустимое базисное решение для произвольной задачи? Для этого существуют различные искусственные приемы.

• М-метод Рассмотрим задачу, записанную в стандартной форме. Теперь в каждое равенство не содержащее дополнительной остаточной переменной введем некоторую новую переменную Ri, которая является искусственной и войдет начальное решение. Так как эта переменная не несет никакого смысла для данной задачи, то следует добиться того чтобы ее значение в результате равнялось нулю (и тогда нам не важен ее смысл, ведь никто не запрещает прибавить к 21 тысяче рублей 0 динозавров). То есть возьмем некий большой штраф М (данный метод также называют методом больших штрафов) и для каждой “неосмысленной” переменной прибавим (в случае максимизации) или вычтем (в противном случае) из целевой функции выражение M Ri. Если размер штрафа достаточно велик, то процесс симплекс-метода приведет к нулевым значениям переменных Ri.

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

Замечание 2 Использование метода больших штрафов может и не привести к обнулению всех новых переменных. Если условие несовместно (исходная задача не имеет допустимого решения, то одна или несколько введенных переменных Ri могут иметь ненулевые значения). Это индикатор некорректной постановки задачи.

Замечание 3 Теоретически требуется, чтобы M, с учетом условий компьютерной реализации М должна быть достаточно велика.

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

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

(i) Первый шаг делается по аналогии с М-методом. Записываем задачу в стандартной форме и добавляем искусственные переменные. Решаем задачу минимизации суммы искусственных переменных, при удовлетворении исходным ограничениям. Если минимальное значение этой искусственной целевой функции больше нуля то задача не имеет допустимых решений, в противном случае переходим ко второму этапу.

(ii) Базисное решение полученное на предыдущем этапе используется для решения исходной задачи.

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

2.5 Особые случаи • Вырожденность Вырожденный случай – случай, в котором одна из базисных переменных имеет нулевое значение. Что означает, что в исходной задаче присутствует избыточное ограничение.

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

• Неограниченные решения Иногда, обычно в случае некорректной постановки задачи (не учтен некоторые параметры) решение может неограниченно возрастать (убывать – в случае минимизации). Если на некоторой итерации коэффициенты в ограничениях для небазисной переменной неположительны, а коэффициент в z-строке отрицателен, то значение целевой функции неограничено (в случае задачи максимизации).

• Отсутствие допустимых решений Возможны также случаи, когда допустимых решений нет. То есть области заданные неравенствами имеют пустое пересечение. Это означает, что задача плохо сформулирована (или действительно не имеет решений :).

3 Теория симплекс-метода 3.1 Матричное представление задачи Ниже мы обоснуем приведенный в предыдущей главе метод. Для начала нам понадобится другое (матричное) представление задачи.

Мы имеем m ограничений на n переменных и перед нами стоит задача минимизировать или максимизировать при этом задано начальное допустимое базисное решение.

Здесь E – единичная матрица, под записью (A, E) будем понимать матрицу, полученную “дописыванием матрицы E справа к матрице A”, далее будем обозначать I := (A, E). X = (x1,..., xn )T, C = (c1,..., cn ) Систему линейных ограничений (ограничения записаны в виде равенств IX = b), можно записать и как где Pj – вектор, j й столбец матрицы I. Набор m из этих векторов является базисом, если определитель матрицы B, состоящей из них отличен от 0.

Пусть det(B) = 0, тогда существует обратная матрица B 1. Для системы можно выбрать набор из m векторов (базисный), и соответственно набор XB из m элементов вектора X. Всем остальным элементам вектора X присвоим нулевые значения. Тогда решение данной системы (BXB = b) будет единственным:

XB – базисное решение системы IX = b. Это решение допустимое, если B1 b 0, где 0 = (0,..., 0)T.

Требуемое представление задачи получается, если заданное начальное допустимое базисное решение состоит из переменных xnm+1,..., xn (в противном случае мы можем просто перенумеровать переменные).

Пример 1 Минимизировать z = 2x1 4x2 при ограничениях После приведения к стандартной форме мы получаем задачу минимизации функции z = 2x1 4x2 при ограничениях В этой задаче 4 переменных (m) и 2 ограничения (n). Переменные x3, – дополнительные. Соответственно в матричном виде:

3.2 Основные теоремы Определение 1 Отрезком XY называется множество точек, определяемых соотношением z = x + (1 )y, [0, 1].

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

Определение 3 Выпуклой комбинацией точек p1,..., pk метрического пространства называется точка Заметим, что выпуклая комбинация любых двух точек выпуклого множества – точка этого множества.

Определение 4 Крайняя точка выпуклого множества – это точка, не представимая в виде выпуклой комбинации каких-либо двух различных точек данного множества.

Рассмотрим множество допустимых решений задачи линейного программирования Теорема 1 Если ограничения имеют допустимое решение, то они имеют и базисное решение.

Доказательство: Докажем это, построив базисное допустимое решение. Пусть в допустимом решении nr переменных равны 0, а остальные положительны. Тогда без потери общности можно считать нулевыми переменные xr+1,..., xn. А значит:

Если P1, P2,..., Pr линейно независимы, то r m (m – ранг матрицы I) и решение является базисным допустимым решением.

Если P1, P2,..., Pr линейно зависимы, то можно составить линейную комбинацию r Pj j = 0, причем не все j = 0. Пусть k > 0, тогда Выбрав k так, что то значения неотрицательны и поэтому являются допустимыми решениями, в которых по крайней мере r 1 переменная имеет строго положительное значение. Продолжая рассуждения таким же образом (т. е. уменьшая количество строго положительных переменных), в конце концов придем к ситуации, при которой r m, т. е. получим базисное допустимое решение.

Теорема 2 Множество Q – выпуклое.

Доказательство: Пусть точки x и y принадлежат допустимой области [0, 1], то имеем:

т. е. z Q, что и означает выпуклость Q.

Замечание 1 В выпуклом множестве любая содержащаяся в нем точка может быть представлена линейной комбинацией крайних точек.

Теорема 3 Точка x – крайняя точка пространства решений Q, если и только если x – базисное решение системы Ix = b, причем x 0.

Доказательство: Пусть x0 = (x1,..., xm, 0,..., 0)T - базисное допустимое решение. Тогда x0 является единственным решением уравнения Ax = b, где x 0 b последние n m координат вектора x равны 0.

Если x0 – не вершина, то можно найти две другие точки u Q и v Q, такие, что x0 = u + (1 )v для некоторого (0, 1). Но тогда для последних n m координат имеем Откуда, из неотрицательности всех "компонент"левой части (, 1, ui, vi ) cледует, что ui = vi = 0i = m + 1,..., n. А значит, в силу того, что x0 – базисное решение, получаем противоречие с выбором u и v, что и доказывает, что x0 – вершина.

Пусть теперь x0 – вершина допустимой области. Пусть r ее координат строго положительны. Покажем, что r не превосходит m, что и означает, что x0 – базисное допустимое решение.Пусть r > m, т. е.

xj > 0, j = 1,..., r. Тогда P1,..., Pr (столбцы матрицы I) оказываются линейнозависимыми. Найдем такие k, не все равные нулю, что j=1 j Pj = 0. возьмем такое, что А тогда векторы где удовлетворяют условиям области Q, действительно: Ax1,2 = A(x0 + a) = Ax0 + Aa = b. А это означает, что x0 = 1/2 · (x1 + x2 ), т. е.

x0 не является вершиной, что приводит к противоречию и доказывает, что r m.

Теорема 4 Оптимальное решение задачи линейного программирования достигается в крайней точке множества Q. (В случае, если это решение конечно).

Доказательство: Не уменьшая общности будем считать, что перед нами стоит задача нахождения минимального решения. Пусть допустимым базисным решениям соответствуют точки x1,..., xk, тогда (с учетом замечания), любая точка x Q представима как линейная комбинация этих точек. Пусть целевая функция z = Cx достигает минимума в некоторой точке x, причем x = k i xi, k i = 1. Но тогда где x0 = minj=1,...,k Cxj. А это и означает, что оптимальное решение достигается в крайней точке множества Q – в точке x 3.3 Обоснование симплекс-метода Приведенные теоремы доказывают, что конечное оптимальное решение достигается в крайней точке пространства решений. Все точки этого пространства можно определить как базисные решения системы IX = b, X 0, которые, таким образом, становятся главным объектом наших исследований.

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

В стандартной задаче линейного программирования (максимизировать z = CX при ограничениях IX = b, X 0) разобьем вектор X на вектора X1 и X2, причем X2 соответствует начальному базису B (является начальным допустимым решением). Вектор C также разделим на Для текущей итерации XB – базисный вектор переменных, CB – вектор коэффициентов целевой функции, соответствующих этому базису. Так как небазисные переменные равны нулю, то задача эквивалентна задаче с целевой функцией z = CB XB и ограничениями BXB = b, где решение удовлетворяет уравнению XB = B1 b, записываемому как Симплекс-таблица получается из исходной задачи путем вычисления по следующей формуле то есть имеет вид Таким образом вычислений требует лишь матрица B1, она строится на каждом шаге алгоритма на основании принятого решения об исключаемом базисном и вводимом небазисном векторах.

Чтобы выяснить, какой вектор нам наиболее "выгодно"вводить в базис, рассмотрим коэффициент при переменной xj в z-строке таблицы, который равен zj cj = CB B1 Pj cj, для базисных переменных эта разность равна нулю. Пусть – множество небазисных переменных, тогда для целевой функции имеем Таким образом ясно, что увеличение значения переменной xj приводит к увеличению целевой функции z выше текущего значения (равного CB B1 b), если zj cj 0 (условие оптимальности).

Теперь выберем исключаемый вектор. Проверим равенство соответствующее i й базисной переменной.

Пусть Pk – вводимый вектор, xk – вводимая переменная. Все прочие небазисные переменные равны 0, значит мы можем переписать ограничение (XB )i = (B1 b)i (B1 Pk )i xk, что означает, что базисная переменная (XB )i не станет отрицательной, если i((B1 b)i (B1 Pk )i xk 0) (условие допустимости). Выпишем максимальное значение вводимой переменной Базисная переменная, на которой минимум достигается, оказывается исключаемой.

4 Модификации симплекс-метода После того как мы обсудили теорию симплекс-метода имеет смысл описать некоторые его модификации.

4.1 Мультипликативное представление обратной матрицы (модифицированный симплекс-метод) Мы не будем производить преобразования строк методом Гаусса-Жордана, как это делалось в обычном симплекс-методе, а будем использовать обратную матрицу B1. Последовательные базисы при итерациях симплексметода отличаются одним столбцом (идет замена исключаемого вектора вводимым). Положим B1 = LB1, и попытаемся вычислить матриnext цу L. Pj и Pr – вводимый и исключаемый из базиса вектора, тогда L – получается из единичной матрицы E заменой r столбца на Доказательство: Рассмотрим матрицу F, получаемую из E заменой одного столбца F = (e1,..., er1, B1 Pj, er+1,..., em ). Легко проверить, что Bnext = BF. Теперь осталось, 4.1 Мультипликативное представление обратной матрицы где L = F1.

В нашем алгоритме начальный базис есть единичная матрица E, тогда матрица Bi1 на i итерации есть B1 = Li... L1 E. Теперь мы не должны вычислять обратных матриц.

У модифицированного симплекс метода следующие преимущества:

(i) Число арифметических действий меньше чем в обычном методе, например за счет разреженности матриц.

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

Пример 1 Еще раз вспомним о задаче 1 o типографии.

Максимизировать z = (5, 4, 0, 0, 0, 0)(x1,..., x6 )T при ограничениях Пусть коэффициенты целевой функции C = (c1,..., c6 ), а столбцы матрицы ограничений (A, E) = I = (P1,..., P6 ). b – вектор правых частей.

Теперь будем действовать по итерациям:

• Итерация Условие оптимальности CB0 B1 = 0, {zj cj }j=1,2 = CB0 B1 (P1, P2 ) (c1, c2 ) = (5, 4).

откуда вектор P1 – вводимый.

Условие допустимости 4.1 Мультипликативное представление обратной матрицы и вектор P3 – исключаемый.

• Итерация Вычислим B1, мы знаем что B1 P1 = (6, 1, 1, 0)T. В матрице B заменялся первый столбец (r = 1).

Тогда XB1 = B1 b =(4, 2, 5, 2)T, z = CB1 XB1 = Условие оптимальности Вектор P2 – вводимый.

Условие допустимости Вектор P4 – исключаемый.

• Итерация Условие оптимальности Таким образом решение XB2 оптимально:

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

Рассмотрим простой случай, когда заданы только нижние границы на значения переменных(X L). В этом случае подстановка X = L + X, X 0 сводит задачу к обычной задаче линейного программирования, результат получается обратной подстановкой.

Если же в задаче присутствуют верхние границы(X U), то прямая замена переменных (X = U X, X 0) невозможна, т. к. обратная подстановка не гарантирует неотрицательность X. Для решения задачи ЛП с верхними границами мы применим следующую модификацию для симплекс-метода: при проверки условия допустимости мы будем дополнительно учитывать ограничение X U.

Из уравнения ограничения относительно базисной переменной xi (заметим, что оно верно, только если все небазисные переменные равны нулю) мы получаем требуемые условия:

1) Базисная переменная (XB )i должна остаться неотрицательной. Это требование будет заведомо выполняться, если 2) Базисная переменная (XB )i не должна превышать своей верхней границы ((XB )i (UB )i ), что будет иметь место, если 3) Вводимая переменная xj не может принять значения, большего своей верхней границы, т. е. должно выполняться неравенство xj uj.

Все три неравенства относительно xj можно обобщить в виде следующего условия:

Базис, формируемый для следующей итерации симплекс-метода, зависит от того, какое значение (1, 2, uj ) примет переменная xj. Предполагая, что (XB )r - исключаемая переменная, имеем следующие правила формирования базиса:

1) Если xj = 1, то переменная (XB )r исключается из базиса и принимает нулевое значение. Новый базис формируется точно так же, как в обычном симплекс-методе с вводимой переменной xj и исключаемой (XB )r.

2) Если xj = 2, переменная (XB )r исключается из базиса и принимает значение своей верхней границы. Новый базис формируется точно так же, как в обычном симплекс-методе, но с учетом того, что переменная (XB )r равна верхней границе (а не нулю). Кроме того, поскольку значения 1 и 2 получены при условии, что все небазисные переменные равны нулю, для корректной работы алгоритма в дальнейшем необходимо выполнить преобразование над новой небазисной переменной (XB )r, чтобы она также приняла нулевое значение. Это достигается с помощью 4.2 Метод решения задач с ограниченными переменными подстановки (XB )r = (UB )r (XB )r, где (XB )r 0. Не имеет особого значения, когда выполняется эта подстановка: до или после вычисления нового базиса.

3) Если xj = uj, то базисный вектор XB остается неизменным, поскольку в данном случае никакая из текущих базисных переменных не принимает ни нулевого значения, ни значения своей верхней границы.

Таким образом, переменная xj остается небазисной, но со значением своего верхнего предела. После подстановки xj = uj xj выполняется следующая итерация симплекс-метода.

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

Замечание 1 Подстановка xj = uj xj изменяет исходные значения cj, Pj и b на cj = cj, Pj = Pj и b = b uj Pj. Это означает, что при выполнении модифицированного симплекс-метода на каждой итерации все вычисления (таких величин, как B1, XB и zj cj ) должны основываться на измененных значениях C, A и b.

Пример 2 Решим следующую задачу линейного программирования вышеописанным методом решения задач с ограниченными переменными.

Максимизировать z = 3x1 + 5y + 2x3 при ограничениях Так как переменная y ограничена положительными константами не только сверху, но и снизу, делаем замену y = x2 + 7, где 0 x • Итерация 4.2 Метод решения задач с ограниченными переменными Имеем, XB = B1 b = (7, 15)T. Принимая переменную x2 в качестве вводимой в базис переменной, получаем B1 P2 = (1, 4)T. Откуда следует 1 = min 7, 15 = 3.75, что соответствует переменной x5, 2 = (поскольку B1 P2 > 0).

Так как по условию x2 3, получаем значение, принимаемое переменной x2.

Поскольку x2 = u2 базис остается неизменным; переменная x2 в базис не вводится (остается небазисной), но принимает значение своей верхней границы. После подстановки x2 = 3 x2 получаем новую симплекстаблицу.

Базис x1 x2 x3 x4 x5 Решение • Итерация Вводимая в базис переменная - x1. Базисный вектор XB и обратная матрица B1 такие же, как на предыдущей итерации. Вычисляем B1 P1 = (1, 2)T. Отсюда следует 1 = min 4, 3 = 1.5, что соответствует переменной x5, 2 = (поскольку B1 P1 > 0), 3 = 4.

Таким образом x1 = min{1.5,, 4} = 1.5 = 1.

В данной ситуации переменная x1 становится базисной со значением 1.5, переменная x5 выводится из базиса и принимает нулевое значение. Получаем следующую симплекс-таблица.

• Итерация Имеем новую обратную матрицу:

Значения базисных переменных вычисляются так: XB = (x4, x1 )T = B b = (5/2, 3/2)T, где b = (4, 3)T - значения правых частей ограничений, вычисленные в конце нулевой итерации.

Определяем x2 как вводимую в базис переменную. Учитывая, что P2 = P2, получаем B1 P2 = (1, 2)T.

Далее вычисляем 1 = min 1,, что соответствует x4, 2 = min, 22 = 1.25, что соответствует x1, 3 = 3.

Таким образом x2 = min{2.5, 1.25, 3} = 1.25 = 2.

Таким образом, переменная x2 вводится в базис (со значением 1.25), из которого исключается переменная x1, с ненулевым значением, равным ее верхней границе. Получаем следующую симплекс-таблицу.

Поскольку переменная x1 становится небазисной с ненулевым значением (= 4), применяем подстановку x1 = 4 x1, что приводит к следующей симплекс-таблице.

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

Оптимальные значения переменных x1, x2 и x3 получаем обратной подстановкой: x1 = u1 x1 = 4 0 = 4, x2 = u2 x2 = 3 5/4 = 7/4 и x3 = 0.

Теперь вычисляем значение переменной y : y = 7 + x2 = 7 + 7/4 = 35/4.

Оптимальное значение целевой функции равно z = 223/4.

5 Марковские процессы с бесконечным числом этапов Введем некоторые обозначения:

K - количество альтернативных стратегий;

S - количество стационарных стратегий;

S - множество всех возможных стационарных стратегий;

Ps и Rs - матрицы переходных(одношаговых) вероятностей и доходов, соответствующие применяемой стратегии s;

is - ожидаемый доход, получаемый за один этап при стратегии s для заданного состояния i, i = 1, 2,..., m;

i - долгосрочные стационарные вероятности матрицы переходных вероятностей (т. е. s Ps = s и 1 + 2 + · · · + m = 1).

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

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

при ограничениях Заметим, что при каждом i должно быть только одно k, что qi = 1.

Обозначим wik = i qi, т. е. wik - это совместная вероятность пребывания в состоянии i и принятия решения k, а это означает, что i = wik. Следовательно, При таком способе определения qi ограничения m 1 = 1 и K qi = 1 выполняются автоматически.

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

Сформулированная в таком виде задача представляет собой задачу линейного программирования с переменными wik.

Покажем теперь, что ее оптимальное решение автоматически гаранk тирует, что qi = 1 только для одного k при любом i. Заметим, что в задаче линейного программирования имеется m независимых уравнений.

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

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

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

Задача 1 Задача о перевозке товара. m поставщиков товара поставляют A = (a1,..., am ) единиц товара, и n потребителей потребляющих B = (b1,..., bn ) единиц товара. Причем m ai = n bi. Задана стоимость перевозки cij, нужно вычислить сколько товара каждый поставщик должен поставлять каждому потребителю для минимизации общей стоимости перевозок.

Или, в терминах линейного программирования:

Минимизировать При ограничениях 6.1 Вспомогательные теоремы Рассмотрим прямоугольную решетку A, некоторые узлы которой выделены. Множество всех узлов назовем, а множество выделенных узлов. Пусть Av – множество столбцов решетки, Ag – множество строк. Назовем рядом столбец или строку и обозначим множество рядов как Ar.

Определение 1 Цепь – ломаная состоящая из горизонтальных и вертикальных отрезков с изломами только в выделенных узлах.

Определение 2 Цикл – замкнутая цепь.

Положим X = # – количество выделенных узлов, а Xmax – максимальное количество выделенных узлов при котором не образуется цикл.

Лемма 1 Если X = Xmax, то в любом ряду есть выделенный узел.

Действительно, если мы выделим любой узел в ряду где нет выделенных узлов, то в этом узле не будет излома.

Лемма 2 Если X = Xmax, то любая пара выделенных узлов принадлежит некоторой цепи.

Теорема Доказательство: Индукция по m. Для m = 1 – очевидно. Пусть для k строк Xmax = k + n 1, тогда добавим строку. В каждом столбце матрицы есть выделенный узел (1). Добавить два выделенных узла в новую строку не удастся (2). Можно добавить один узел.

6.2 Решение транспортной задачи Условия транспортной задачи запишем в виде таблицы.

an cn1... cnn Наша задача заключается в построении соответствующей таблицы перевозок an xn1... xnn Будем считать клетки таблицы узлами, а множество выделенных узлов – множество клеток с xij 0.

Теорема 2 Оптимальное решение достигается на ациклическом наборе.

Доказательство: Пусть мы нашли допустимый набор перевозок, содержащий цикл. Тогда занумерует клетки цикла (в порядке обхода) и разобьем цикл на два множества odd и even с суммами cij равными Codd Ceven. Если Codd Ceven, то возьмем перевозку с минимальным весом r в четном полуцикле, теперь для xij = xij r(ij even), xij = xij + r(ij odd). Тогда цикл разрушится, а общая стоимость перевозки не увеличится.

6.3 Метод потенциалов Теперь перейдем к описанию метода решения транспортной задачи.

• Инициализация Воспользуемся жадным алгоритмом по строкам (берем в строке перевозку минимальной стоимости и исчерпываем её ресурс). Для всех строк кроме последней, в случае исчерпания ресурсов как потребителя так и поставщика, заполняем фиктивной (нулевой) перевозкой клетку минимальной стоимости.

Теорема 3 В ходе инициализации получен ациклический набор.

Теорема 4 В ходе инициализации получен набор из n + m 1 клеток.

• Выбор клетки для загрузки Введем числа ui и vj, сопоставив их строкам и столбцам соответственно. Причем так, чтобы для загруженной клетки ui + vj = cij. Положим дополнительно u1 = 0, тогда таблица примет вид.

Для удобства мы записываем выбранные перевозки x в левом нижнем углу клетки.

Теорема 5 Все u, v вычисляются однозначно.

Доказательство: Пусть удалось вычислить не все, тогда можно переставить местами некоторые ряды и получить Тогда в блоках II и III нет загруженных клеток. Вследствие ацикличности набора в блоке IV их не более p + q 1, тогда в блоке I более (n p) + (m q) загруженных клеток, что приводит к наличию цикла.

Выберем теперь незагруженную клетку для которой ui + vj > cij.

Пусть эта клетка – первая при обходе, тогда Codd > Ceven, найдем минимальную перевозку r на четном полуцикле вычтем её из перевозок четного полуцикла и прибавим к нечетному. Будем продолжать действия пока есть клетка для разгрузки.

СПИСОК ЛИТЕРАТУРЫ

Теорема 6 Если для всех незагруженных клеток потенциал pij = ui + vj cij, неположителен то получена наилучшая система перевозок.

Список литературы [1] Хэмди А. Таха, Введение в линейное программирование.

[2] В. И. Рублинецкий, Введение в мир алгоритмов.