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

1. Нахождение допустимых базисных решений

Определение начального допустимого базисного решения (ДБР) в общем случае представляет значительные трудности. Поэтому для поиска ДБР разработаны специальные методы.

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

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

В общем случае, когда некоторые ограничения имеют знак , например

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

Свободные переменные {xn+1,.,xn+m} в этом случае уже невозможно использовать в качестве начального базиса, так как xn+1<0,.,xn+m<0. Поэтому в уравнения (1.1) дополнительно вводят искусственные переменные xn+m+1,.,xn+m+k. Эти переменные не имеют ничего общего с реальной задачей, и потому их надо вывести из базиса как можно быстрее. Для этого перед началом итераций искусственным переменным в целевой функции приписывают для задач максимизации очень большие по модулю отрицательные коэффициенты (-М), где .

В случае решения задач минимизации искусственные переменные вводят в целевую функцию с большими положительными коэффициентами (+М).

Знаки искусственных переменных xn+m+1,.,xn+m+k должны совпадать со знаками соответствующих свободных членов. Искусственные переменные образуют начальное базисное решение. Применив симплекс-метод, необходимо вывести из базиса все искусственные переменные. Если удается доказать (или показать), что искусственные переменные полностью вывести из базиса невозможно, то это означает, что задача не имеет решения, то есть ее ограничения противоречивы.

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

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

2.1. Структура и свойства двойственной задачи

Задачу максимизации ЛП с экономической точки зрения можно рассматривать как задачу о распределении ограниченных ресурсов b1,.,bm между различными потребителями, например между определенными технологическими процессами, которые представляются столбцами A1,.,An матрицы ограничений задачи.

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

Рассмотрим пример. Предприятие производит три вида продукции x1, x2 и x3, каждый из которых проходит обработку на токарном, фрезеровальном и сверлильном станках. Общий фонд машинного времени для каждого из станков ограничен. Пусть c1, c2 и c3 - прибыль от реализации единицы соответствующего вида продукции. Необходимо определить, какое количество продукции каждого вида следует производить каждую неделю, чтобы обеспечить максимальную прибыль.

Эта задача имеет такой вид:

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

где a1j, a2j, a3j - время, необходимое для обработки единицы j-го вида продукции на токарном, фрезеровальном и сверлильном станках соответственно (j=1, 2 ,3), b1, b2, b3 - недельный ресурс машинного времени для группы токарных, фрезеровальных и сверлильных станков соответственно.

Обозначим через y1, y2, y3- цену единицы времени работы токарного, сверлильного и фрезеровального оборудования.

Тогда a11y1 + a21y2 + a31y3 можно трактовать как затраты на изготовление единицы продукции первого вида;

Предположим, что цены ресурсов y1, y2, y3 выбраны так, что выполняются соотношения

Поскольку b1, b2, b3 - общий использованный ресурс машинного времени для каждого из станков, то b1y1+b2y2+b3y3 - общие затраты на производство (общая стоимость использованных ресурсов).

Тогда можно сформулировать следующую задачу.

Требуется определить цены y1, y2, y3, удовлетворяющие условиям (2.1.3), при которых минимизируются суммарные затраты на производство, а именно:

при ограничениях (2.1.3) и

Задачу (2.1.3), (2.1.4) называют двойственной относительно задачи (2.1.1), называемой прямой.

Запишем прямую и двойственную задачи в общем виде.

Прямая задача:

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

Двойственная задача:

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

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

Прямая задача:

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

Двойственная задача:

при условиях

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

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

2.        Коэффициенты целевой функции прямой задачи c1,...,cn становятся свободными членами ограничений двойственной задачи.

3.        Свободные члены ограничений прямой задачи b1,...,bm становятся коэффициентами целевой функции двойственной задачи.

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

5.        Знаки неравенств в ограничениях изменяются на противоположные.

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

Переменные y1,...,ym двойственной задачи иногда называют теневыми ценами.

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

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

Теорема 2.1.1. Если x0 и y0 допустимые решения прямой и двойственной задач, то есть и , то

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

Доказательство. Умножим выражение (2.1.12) на , получим

Аналогично умножим (2.1.15) на :

Но , а кроме того .

Поэтому, сравнивая (2.1.19) и (2.1.18), получим

Теорема доказана.

Теорема 2.1.2. (основная теорема двойственности). Если x0 и y0 допустимые решения прямой и двойственной задач и кроме того, если cTx0=bTy0, то x0 и y0 - оптимальные решения пары двойственных задач.

Доказательство. Согласно теореме 2.1.1 для всех допустимых решений х и у справедливо неравенство (2.1.17). В частности, для всех допустимых решений х справедливо . Однако из условия теоремы cTx=bTy0 следует . Следовательно, x0 - оптимальное решение.

Вторая часть теоремы доказывается аналогично.

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

Теорема 2.1.3. Если в оптимальном решении прямой задачи (2.1.5) - (2.1.7) i-тое ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей двойственной переменной равно нулю, то есть

где Ai - i-я строка матрицы А.

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

Теорему 2.1.3. дополняет теорема 2.1.4, устанавливающая взаимосвязь между оптимальным решением прямой задачи и ограничениями двойственной.

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

Дадим экономическую интерпретацию теоремы 2.1.4.

Поскольку величины yi (i=1,2,.,m) представляют собой цены соответствующих ресурсов, то - это затраты на j-й технологический процесс, а величина cj - прибыль от реализации единицы соответствующего продукта. Поэтому с экономической точки зрения теорема 2.1.4 означает следующее: если j-й технологический процесс оказывается строго невыгодным относительно оптимальных цен ресурсов yопт, то в оптимальном решении прямой задачи интенсивность использования данного технологического процесса должна быть равна нулю, и соответствующий вид продукции не выпускается как нерентабельный.

Таким образом, теорема 2.1.4 выражает принцип рентабельности для оптимально организованного производства.

Из этой теоремы вытекает также, что если , то

Предположим, что среди переменных x1, x2, ., xn прямой задачи есть множество из m переменных, которые в оптимальном решении прямой задачи имеют ненулевые значения. Пусть, например, такими переменными оказались первые по порядку m переменных.

Тогда на основании уравнения (2.1.22) получаем m условий рентабельности:

где

Доказательства теорем 2.1.3 и 2.1.4 проведем последовательно.

Пусть хопт и yопт - оптимальные решения прямой и двойственной задач. Поскольку эти решения допустимые, то

Умножив неравенство (2.1.24) на , а неравенство (2.1.25) - на , получим

Так как в силу теоремы 2.2 и , то выражения (2.1.26), (2.1.27) строго равны нулю.

Расписав левую часть неравенства (2.1.26), получим

Поскольку и для всех i = 1, 2, ..., m, то левая часть уравнения (2.1.28) может быть равна 0 только в том случае, если каждое слагаемое в отдельности равно нулю.

Таким образом, для каждого i, при котором , имеем , что и требовалось доказать в теореме 2.1.3.

Рассмотрим теперь левую часть неравенства (2.1.27), предварительно расписав ее

где A=[A1,A2,...,An].

Так как все и для всех j=1,.,n, то уравнение (2.1.29) строго равно нулю, если для каждого j, при котором , соответствующая переменная равна нулю.

Приведем еще две важные теоремы теории двойственности.

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

Теорема 2.1.6. (теорема двойственности). Допустимый вектор x0 оптимальный тогда и только тогда, когда в двойственной задаче имеется такое допустимое решение y0, что

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

где n - количество переменных прямой задачи; m - количество ее ограничений;

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

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

2.2. Общий случай двойственности

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

Пусть прямая задача ЛП задана в виде

при условиях

Тогда двойственная задача по отношению к задаче (2.2.1)-(2.2.3) записывается так:

при условиях

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

1.        Если переменная xj прямой задачи предполагается неотрицательной, то j-е условие системы (2.2.5) является неравенством.

2.        Если на переменную xj не накладывается ограничение на знак, то j-е ограничение двойственной задачи (2.2.5) будет равенством.

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

Заметим, что если положить m1=m и n1=n, то получим частный случай пары двойственных задач с ограничениями в форме неравенств.

Докажем справедливость соотношений (2.2.1) - (2.2.3) и (2.2.4) - (2.2.6), связывающих прямую и двойственную задачи.

Свяжем с каждой ЛП - задачей вида (2.2.1) - (2.2.3) следующую задачу с ограничениями в форме неравенств:

при условиях

где n2=n-n1 - число переменных задачи (2.2.1) - (2.2.3), на которые не наложено условие неотрицательности.

Установим соответствие между переменными задач (2.2.1) - (2.2.3) и (2.2.7) - (2.2.10). Сравнивая формы их записи, убеждаемся, что n-мерный вектор х={x1,.,xn} и (n+n2)-мерный вектор связаны соотношением

Очевидно, каждому (n+n2)-мерному вектору x' соответствует единственный n-мерный вектор x, и вместе с тем произвольному n-мерному вектору x соответствует целое семейство (n+n2)-мерных векторов х'.

Таким образом, соответствие, устанавливаемое формулой (2.2.11), является однозначным только в одну сторону.

Вместе с тем среди семейства векторов х', соответствующих x, всегда существуют векторы с неотрицательными компонентами.

Пусть вектор - план задачи (2.2.7) -(2.2.10). Используя соотношение (2.2.11), можно легко получить, что соответствующий вектор x является планом задачи. И наоборот, если x - план задачи (2.2.1) - (2.2.3), то существует целое семейство планов x' задачи (2.4.38) - (2.4.41), среди которых имеются заведомо неотрицательные.

Одним из них является вектор где

j = 1, 2, ., n1,

j = n1+1, n1+2, ., n,

j = n+1, n+2, ., n+n2.

Неотрицательность всех компонентов очевидна, а соответствие векторов x и следует из равенства

где j=n1+1; n1+2,.,n...

Рассмотрим задачу (2.2.4) - (2.2.6), двойственную к задаче (2.2.1) - (2.2.3). Нетрудно показать, что она приводится к виду (2.2.1) - (2.2.3). Для этого достаточно положить . При этом задача (2.2.4) - (2.2.6) переходит в задачу

при условиях

Поэтому задаче (2.2.4) - (2.2.6) соответствует следующая задача с ограничениями в форме неравенств:

при условиях

где m2 = m - m1 - число переменных yi, на которые не наложено условие неотрицательности.

Вектор y={y1,.,ym} и соответствующий ему (m+m2) мерный вектор связанны соотношением

Следовательно, каждому плану y' задачи (2.2.17) - (2.2.20) соответствует план у задачи (2.2.4) - (2.2.6), и наоборот: любой неотрицательный вектор, соответствующий плану (решению) задачи (2.2.4) - (2.2.6), является решением задачи (2.2.18) - (2.2.20). При этом, если у' и у - два соответствующих друг другу решения, то из оптимальности одного из них непосредственно следует оптимальность другого.

Запишем задачу, двойственную к (2.2.7) - (2.2.10). Непосредственной проверкой можно убедиться в том, что получим задачу в форме (2.2.17) - (2.2.20). Таким образом, задачи (2.2.7) - (2.2.10) и (2.2.17) -(2.2.20) с произвольными ограничениями (неравенства - равенства) также представляют собой двойственную пару.

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

Рассмотрим для примера теорему 2.2.1.

Если х и у - допустимые решения прямой (2.2.1) - (2.2.2) и двойственной (2.2.4) - (2.2.6) задачи и если при этом , то х и у - оптимальные решения этих задач.

Доказательство. Допустим, что задача (2.2.1) - (2.2.2) разрешима и x-ее допустимое решение, а у - допустимое решение (план) задачи (2.2.4) - (2.2.6). Рассмотрим вектор , связанный с вектором х соотношениями (2.2.11), с неотрицательными компонентами. По доказанному выше х' является решением задачи (2.2.7).

Воспользуемся тогда теоремой 2.2.1 для задач с ограничениями - неравенствами.

Согласно этой теореме, если х' и у' - допустимые решения пары двойственных задач и выполняется равенство

то х' и у' - оптимальные решения этой пары задач.

Используя соотношения (2.2.11), (2.2.21), связывающие соответствующие планы х' и х, у и у', получим

Таким образом, соотношения (2.2.22) и (2.2.23) - (2.2.24) - эквивалентны, поэтому планы х' и у'- оптимальны.

Но по доказанному выше каждому оптимальному х' соответствует единственный оптимальный план х, а каждому оптимальному плану у' соответствует единственный план у. Теорема доказана.

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