Решение задач линейного программирования онлайн

Геометрия задачи линейного программирования

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

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

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

Доказательство теоремы 7.1 будет дано ниже.

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

принимает оптимальное значение данной задачи.

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

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

Указанный способ решения задачи линейного программирования, как правило, требует громоздких вычислений. В § 8.1 и 8.2 мы ознакомимся с так называемым симплекс-методом, представляющим собой целенаправленную процедуру перебора вершин.

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

Пусть точка имеет координаты Заменив последнюю координату нулем, получим точку Будем называть эту точку проекцией точки на координатную плоскость Аналогично определяется проекция точки на любую координатную плоскость. Например, проекция на координатную плоскость есть точка Вообще, сохранив любые координат точки и заменив остальные координаты нулями, получим проекцию точки на соответствующую координатную плоскость.Сделаем сразу же замечание. Как только что сказано, проектирование точки на ту или иную координатную плоскость сводится к сохранению каких-то координат точки и замене остальных координат нулями. Если просто отбросить эти нулевых координат, получим точку пространства Эту точку также можно называть проекцией точки на соответствующую координатную плоскость. Именно так мы и будем понимать дальше проекцию точки Например, проекция точки на координатную плоскость понимается как точка Теорема о проекциях. Если — выпуклая многогранная область в то проекция на любую координатную плоскость снова является выпуклой многогранной областью (в соответствующем пространстве Доказательство. Поскольку взятие проекции для точки сводится к отбрасыванию нескольких координат, то достаточно доказать теорему для случая, когда отбрасывается только одна координата, например Другими словами, мы должны доказать, что если от каждой точки отбросить последнюю координату то полученные точки будут образовывать выпуклую многогранную область в По условию, область выделяется из с помощью некоторой системы нестрогих линейных неравенств. Рассмотрим любое из этих неравенствЕсли то оставим неравенство (7.11) без изменения. Если же то, в зависимости от знака приведем его к виду (при либо Итак, любое из неравенств системы приводится к одному из трех видовгде суть выражения видат.е. многочлены первой степени, не содержащие Таким образом, система равносильна системе из трех блоков:Разумеется, при этом не исключено, что в системе (7.12), (7.13), (7.14) не будет одного или даже двух блоков. Это зависит от знаков чисел Построим теперь систему неравенств с неизвестными следующим образом: для любого неравенства блока (7.12) и любого неравенства блока (7.13) напишем новое неравенство

неравенства же блока (7.14) оставим без изменения. В итоге получится новая система

неравенств с неизвестными Эта система выделяет из пространства выпуклую многогранную область Покажем, что есть проекция области на координатную плоскость чем и завершим доказательство теоремы.Поясним подробнее определение системы (7.15). Может случиться, что в системе из трех блоков (7.12), (7.13), (7.14) первый или второй блок отсутствует. Тогда в системе (7.15) будут только неравенства Если отсутствует блок (7.14), то в (7.15) будут только неравенства Наконец, если отсутствуют блоки (7.12), (7.14) или (7.13), (7.14), то системы (7.15) нет вовсе. Мы будем считать ее в этом случае тождественной, т.е. состоящей из неравенства (или точнее, из неравенства

Фактически мы должны доказать два утверждения.

Доказательство. Утверждение очевидно (если какой-нибудь набор значений неизвестных удовлетворяет системе то он удовлетворяет и системе (7.12), (7.13), (7.14); но тогда для этого же набора выполняются все неравенства системы (7.15)).Докажем утверждение Сначала рассмотрим основной случай, когда в системе (7.15) имеется хотя бы одно неравенство Пусть— какое-нибудь решение системы (7.15). Подставив указанные значения неизвестных в выражения получим некоторые числа Для них выполняются неравенстваМы видим, что каждое из чисел не больше, чем любое из чисел Но в таком случае обязательно найдется такое число которое заключено между всеми числами и всеми числами

Отсюда следует, что набор значений неизвестных

является решением системы (7.12), (7.13), (7.14), а следовательно, и (7.15).

В исключительном случае, когда в системе (7.12), (7.13), (7.14) отсутствует первый или второй блок, рассуждаем следующим образом. Если нет первого блока, в качестве можно взять любое число, удовлетворяющее условиямАналогично при отсутствии второго блока выбираем исходя из условийНаконец, если отсутствуют сразу первый и второй блоки, то в качестве можно взять какое угодно число. Теорема доказана.

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

Предварительно заметим следующее: если в системе линейных неравенств, задающих область одно из неизвестных, например отсутствует, то область не имеет вершин. Действительно, если какая-либо точка принадлежит то и все точки прямойпроходящей через также принадлежат Отсюда следует, что не может быть вершиной Уточним нашу терминологию. Мы будем говорить, что неизвестное реально входит в систему если хотя бы одно из неравенств системы содержит член вида где в противном случае будем говорить, что в систему реально не входит. Это означает: если в систему некоторое неизвестное реально не входит, то область отвечающая системе не имеет вершин.Теперь сформулируем предложение о вершинах. Пусть некоторое неизвестное, например реально входит в систему Рассмотрим область — проекцию на координатную плоскость Предположим, что область имеет вершины, и -одна из них. Тогда справедливо следующее утверждение.Лемма о вершинах. Пусть — выпуклая многогранная область в — ее проекция на координатную плоскость где реально входит в систему неравенств, задающих Если обе области имеют вершины, и — одна из вершин то средиточек области проектирующихся в обязательно имеется вершина области Доказательство. Обозначим множество всех точек области проектирующихся в через Как показывает доказательство теоремы о проекциях, точки множества получаютсяпутем дополнения координат точки значениями координаты удовлетворяющими системе неравенствМножество всех решений системы (7.16) есть либо отрезок либо лучи либо вся числовая прямая. Последнее невозможно, ибо это означало бы, что в системе (7.12), (7.13), (7.14) блоки (7.12) и (7.13) попросту отсутствуют, т.е. система неравенств состоит только из блока (7.14). Это, в свою очередь, означало бы, что в систему неизвестное реально не входит. Однако это, как было сказано ранее, противоречит тому, что по условию имеет вершины.Итак, множество всех решений системы (7.16) есть либо либо Покажем, что точка является вершиной области Предположим противное, т.е. что не является вершиной Тогда существует отрезок имеющий точку своей внутренней точкой. Проекция этого отрезка на координатную плоскость есть некоторый отрезок имеющий своей внутренней точкой; либо же эта проекция совпадает с Первое противоречит тому, что — вершина второе также невозможно, ибо это означало бы, что отрезок состоит из точек вида где изменяется от некоторого до некоторого а это противоречит сказанному выше о множестве решений системы (7.16).Доказательство теоремы 7.1. Сразу заметим, что если целевая функция — константа, то доказывать нечего. Для определенности будем считать, что решается задача нахождения минимума а значит, функция ограничена снизу на Рассмотрим вначале случай, когда Проекция множества на координатную прямую (т.е. на плоскость есть выпуклая многогранная область в Последняя в силу ограниченности снизу есть либо отрезок либо луч В обоих случаях Пусть теперь — какая угодно линейная функция. Хотя бы один из коэффициентов не равен нулю;пусть, например, Перейдем тогда в пространстве к новым координатам по формулам

или, что то же,

Очевидно, любое линейное неравенство с переменными перепишется в виде линейного неравенства с поэтому выпуклая многогранная область в координатах превратится в выпуклую многогранную область в координатах При этом значит, по доказанному, достигает минимума в Теорема доказана.Доказательство теоремы 7.2. Предположим, что решается задача о нахождении минимума. Ограничимся случаем общий случай сводится к этому частному при помощи приема, указанного в доказательстве теоремы 7.1.Как и ранее, систему ограничений данной задачи обозначим через и соответствующую выпуклую многогранную область в — через Выберем одну из неизвестных реально входящую в систему -но только не — и спроектируем на координатную плоскость Обозначим проекцию через а соответствующую систему неравенств в Снова выберем одну из неизвестных, реально входящую в — опять-таки не — и спроектируем на соответствующую координатную плоскость. Получим область И так далее, пока не придем к некоторой области в пространстве т.е. на числовой прямой, определенной с помощью некоторой системы линейных неравенств с одной переменной Учитывая, что минимум существует, получим, что множество решений последней системы есть либо либо где Используя лемму о вершинах, дополним значение значениями некоторых «реальных» неизвестных (значения «нереальных» неизвестных выбираем произвольно) и получим вершину области Для этой вершины координата равна что и требовалось доказать.Оптимальная вершина получается последовательным дополнением значения крайними значениями остальных переменных. В этом отношении нахождение оптимальной вершины полностью аналогично обратному ходу метода Гаусса.Замечание. На самом деле можно показать, что в данном случае «нереальных» неизвестных не будет и процесс исключения состоит ровно из шагов. Действительно, при наличии «нереальных» неизвестных среди чисел — координат вершины имеютсятакие, которые можно варьировать, т.е. менять произвольным образом. Очевидно, это означает, что в исходную систему ограничений эти неизвестные реально не входят. Отсюда, в свою очередь, следует, что область вопреки условию, не имеет вершин.Для полноты приведем доказательство теоремы 7.2, опирающееся на геометрическую интуицию. Прежде всего установим такую лемму. Лемма. Пусть — выпуклое многогранное множество в пространстве Для существования хотя бы одной вершины множества необходимо и достаточно, чтобы не содержало прямых.

Доказательство. Мы должны доказать два утверждения.

Докажем первое утверждение. Пусть существует вершина Рассуждая от противного, допустим, что содержит некоторую прямую Очевидно, (иначе не была бы вершиной Рассмотрим двумерную плоскость м (рис. 7.1), содержащую если — две точки на то состоит из всех точек вида — любые числа. Плоскость можно рассматривать как пространство с координатами Пересечение есть выпуклая многогранная (лучше сказать — многоугольная) область в действительно, любое линейное неравенство из числа тех, что задают после замены переменных линейными функциями от превращается в линейное неравенство относительно Итак, есть выпуклая многогранная область в имеющая вершину и содержащая прямую Непосредственно очевидно, что в такая область невозможна.Докажем второе утверждение. Пусть множество не имеет вершин. Из всех неравенств, задающих оставим только существенные, т.е. такие, которые нельзя удалить, не изменив Рассмотрим одну из граней множества это означает, что одно из существенных неравенств, задающих заменяется равенством. Если в имеется прямая, доказывать нечего.Пусть в нет прямых. Рассмотрим грань множества Если в имеется прямая, доказывать нечего. Рассмотрим грань множества и т.д. Продолжая это рассуждение, придем к множеству задающемуся только уравнениями (неравенств нет). Если содержит две различные точки то содержит и всю прямую Действительно, есть пересечение нескольких гиперплоскостей, но если гиперплоскость содержит две точки то содержит и все точки (проверьте!), т.е. содержит всю прямую Получается, что содержит прямую, что и требовалось доказать. случае же, когда состоит из единственной точки, эта точка есть вершина (см. способ нахождения вершин в § 6.9), чего не может быть по условию. Лемма доказана.Завершим теперь доказательство теоремы 7.2. Так как множество имеет вершины, то оно не содержит прямых. Следовательно, подмножество для которого тоже не содержит прямых, а значит, имеет вершины. Остается показать, что любая вершина является одновременно вершиной Предположим противное: вершина но не вершина Тогда найдутся такие точки — внутренняя точка отрезка Так как — вершина не могут одновременно принадлежать Следовательно, из двух неравенств хотя бы одно должно быть строгим. Отсюда вытекает, что для любого числа из интервала (0, 1) выполняется неравенствоС другой стороны, для некоторого так как — внутренняя точка отрезка Поэтомучто противоречит полученному выше неравенству. Следовательно, всякая вершина множества является вершиной множества Теорема 7.2 доказана.

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

Теорема 7.2′. Если в задаче линейного программирования все переменные подчинены условиям неотрицательности и целевая функция ограничена на допустимом множестве то угловая точка в которой принимает наибольшее (наименьшее) значение среди всех угловых точек является оптимальным решением данной задачи.

Возможно, вас также заинтересует эта ссылка:

Графический метод состоит в следующем.

1. Строится множество всех допустимых решений.2. Если то задача неразрешима.3. Если то рассматриваются прямые уровня а при монотонном изменении При увеличении прямая смещается параллельно в направлении вектора Если — первая точка встречи прямой уровня с областью то прямая уровня при не имеет общих точек с откуда следует, что Аналогичным образом, если — последняя точка пересечения линии уровня с то Если первой точки пересечения линии уровня с не существует (т.е. при всех из некоторого промежутка вида прямая пересекает то и задача на минимум неразрешима. Если не существует последней точки пересечения, то и неразрешима задача на максимум.Таким образом, из чертежа всегда видно, разрешима задача или нет. Из чертежа также видно, имеются ли у допустимого множества вершины. Отметим сразу, что отсутствие вершины — явление довольно редкое, при ограниченной целевой функции допустимое множество без вершины может быть только двух видов:Если у есть хотя бы одна вершина, то (при ограниченной целевой функции) оптимальное значение может быть найдено методом перебора вершин. Для вычисления целевой функции в некоторой вершине допустимого множества необходимо знать точное значение ее координат. Для определения координат вершины решается система линейных уравнений видагде — номера прямых, ограничивающих область на пересечении которых находится вершина Графический метод позволяет избежать полного перебора вершин. Действительно, если из чертежа видно, что — единственная первая (или последняя) точка пересечения линии уровня с то незачем вычислять координаты других вершин, так как — единственное оптимальное решение. Для некоторых задач, однако, из чертежа не ясно, в какой именно точке линия уровня пересекает в первый раз допустимое множество. В этом случае необходимо найти координаты всех «подозрительных» на оптимальность вершин, вычислить для них значения целевой функции и выбрать из них вершины с оптимальным значением. Заметим, что могут оказаться две оптимальные вершины Тогда множество всех оптимальных решений — это отрезок Пусть — оптимальное значение Множество всех оптимальных решений является подмножеством линии уровня и задается системой линейных неравенств. Поэтому возможны лишь следующие случаи:

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

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

Решим графическим методом задачу о банке из § 7.1:

Построим в плоскости полуплоскости, заданные неравенствами 1) … 5). Общая их часть (заштрихованный треугольник на рис. 7.6) — область допустимых решений. Построим вектор и прямую уровня, перпендикулярную вектору и проходящую через начало координат. Перемещая эту прямую параллельно в направлении вектора найдем последнюю точку пересечения прямой уровня и допустимого множества Найденная точка максимума находится на пересечении прямых 1 и 3. Ее координаты получаются решением следующей системы линейных уравнений:Итак, оптимальный портфель активов (точка максимума) имеет структуру Максимальная прибыль составит Рассмотрим теперь случай трех переменных. Для функции аналогом линии уровня является поверхность уровня, т.е. множество всех точек трехмерного пространства, в которых функция принимает определенное значение. Для функции вида всякая поверхность уровня — это плоскость с вектором нормали Теоретически графический метод

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

Рассмотрим производственную задачу с тремя продуктами и тремя видами ресурсов Введем обозначения: — количество доступных единиц ресурса — цена продукта — количество единиц ресурса расходуемых на производство 1 ед. продукта — количество производимых единиц продуктов соответственно.

Приходим к задаче линейного программирования:

Считаем, что все ресурсы при производстве продуктов только расходуются, а не производятся, т.е. Кроме того, естественно предположить, что при производстве каждого продукта расходуется хотя бы один ресурс. Предположим для определенности, что при производстве каждого продукта расходуется ресурс (и, возможно, другие ресурсы тоже). Тогда и Учитывая неотрицательность получаем неравенства Следовательно, при самых общих предположениях допустимое множество в производственной задаче ограничено. Поэтому решение задачи сводится к нахождению угловых точек (метод перебора вершин).Пусть, например, иа числа конкретно не указаны. Уравнения, отвечающие условиям (7.19), имеют вид Чтобы найти вершины многогранника нужно рассмотреть всевозможные подсистемы из трех уравнений, выбрать из них те, которые имеют единственное решение, и проверить, что найденное решение принадлежит Чтобы как-то упорядочить этот процесс, рассмотрим четыре случая.1. Все три координаты равны нулю (система (7.23) -(7.25)), что дает вершину

2. Лишь одна координата равна нулю. Это приводит к вершинам:

(система (7.21), (7.22), (7.23));

(система (7.20), (7.22), (7.24));

(система (7.20), (7.21), (7.25)).

3. Ровно две координаты равны нулю. Это дает вершины

(система (7.20), (7.24), (7.25)); (система (7.21), (7.23), (7.25));

(система (7.22), (7.23), (7.24)).

4. Все три координаты отличны от нуля, что дает вершину

(система (7.20), (7.21), (7.22)).

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

Задача 4.

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

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

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

Составим таблицу (табл. 7.2).

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

Аналогично получаем условия

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

Таким образом, приходим к следующей задаче. Дана система

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

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

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

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

Пусть — система линейных ограничений (т.е. линейных уравнений или нестрогих линейных неравенств) с переменными целевая функция вида

Требуется решить задачу

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

Наиболее часто встречаются две разновидности задачи линейного программирования.

Указанные две разновидности сводятся одна к другой. Покажем сначала, как свести стандартную задачу к канонической.

Пусть дана стандартная задача линейного программирования -будем называть ее задачей где — заданная система линейных неравенств, включающая (7.6).Пусть — число нетривиальных неравенств в системе Рассмотрим любое из этих неравенств:Введем новую дополнительную переменную и заменим неравенство (7.7) двумя ограничениями: уравнениеми условием Если подобную замену произвести с каждым из нетривиальных неравенств системы то получим новую систему состоящую из уравнений, а также условий неотрицательности всех переменных: исходных и дополнительных Заметим, чтодополнительные переменные называют обычно балансовыми.Назовем задачей задачу при условиях Сравнивая задачи нетрудно убедиться в их эквивалентности: любое оптимальное решение задачи дает оптимальное решение задачи если к значениям переменных добавить значения балансовых переменных. Обратно, любое оптимальное решение задачи если отбросить значения балансовых переменных, дает оптимальное решение задачи

В качестве примера сведения стандартной задачи к канонической можно привести задачу о диете.

Введя для первого неравенства системы (7.2) балансовую переменную для второго — для третьего неравенства — получим каноническую задачу:

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

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

Будем считать ее задачей

Применив к системе из двух уравнений (7.8) метод Гаусса, выделим базис неизвестных:

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

но тогда новая задача

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

Возможно, вас также заинтересует эта ссылка:

Задача 8.7.

Решить задачу линейного программирования

После введения балансовых переменных система ограничений (8.33) принимает вид:

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

А именно среди правых частей неравенств вида «больше или равно» находим неравенство с наибольшей правой частью (в рассматриваемом примере это третье неравенство с правой частью 400). Все остальные неравенства такого типа преобразуются по правилу: в системе уравнений (8.35) из выделенного уравнения

следует вычесть почленно данное и записать вместо последнего. Тогда система (8.35) примет вид Поэтому достаточно ввести только одну искусственную переменную в третье уравнение, чтобы привести систему ограничений (8.36) к допустимому базису. Окончательно задача (8.33), (8.34) преобразуется к следующему виду: Поэтому первой фазой решения данной задачи будет решение (8.37)- (8.38). Начальной симплекс-таблицей будет табл. 8.14. В качестве разрешающего элемента удобно взять число 2 в строке и столбце Получим табл. 8.15. На втором шаге из базиса исключается искусственная переменная и вспомогательная целевая функция обращается в нуль. Поэтому можно вычеркнуть строку и столбец (табл. 8.16)- Это означает завершение первой фазы.На второй фазе выбираем разрешающие элементы, используя строку целевой функции (табл. 8.17).Таблица 8.18 является заключительной, поскольку в строке коэффициентов целевой функции нет положительных. Окончательно получим

Теорема о конечности симплекс-алгоритма

Во всех рассмотренных нами примерах на симплекс-метод дело обстояло благополучно в том смысле, что процесс после конечного числа шагов заканчивался либо нахождением оптимального решения, либо установлением того факта, что Всегда ли будет так? Поскольку процесс останавливается при наступлении одного из случаев I или II из § 8.1, то поставленный вопрос равнозначен следующему: не может ли случиться, что, производя (по симплекс-методу) шаг за шагом вычисления, мы никогда не окажемся перед одним из случаев I или II? По этому поводу можно высказать следующие соображения.

Предположим теперь, что процесс продолжается без остановки, образуя бесконечную последовательность базисов

для которых

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

в которых начальное и конечное звенья совпадают. Такие цепочки называются циклами. Ясно, что тогда и

откуда следует в силу (8.40), что

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

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

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

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

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

Ответ и в самом деле оказывается утвердительным. Он содержится в следующей теореме.

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

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

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

Условимся считать вектор

положительным и записывать это

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

или же

или же

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

и линейная функция

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

Условимся называть базис положительным, если все векторы

положительны в указанном ранее смысле. Разумеется, если все свободные члены положительны, то базис будет положительным независимо от того, какие числа стоят в приписанной части табл. 8.19. Однако если какое-либо из чисел равно нулю, то условие положительности базиса накладывает некоторое ограничение на числа первое из них, отличное от нуля, должно быть положительным. Таким образом, свойство базиса быть положительным может зависеть не только от самой системы ограничений (8.41), но и от приписанных чисел

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

Очередной шаг симплекс-метода начинается с выбора разрешающего элемента. Напомним, как производится этот выбор. Находим среди чисел последней строки положительное число после чего просматриваем все числа столбца Для каждого положительного составляем отношение и затем среди этих отношений выбираем наименьшее, допустим Тогда элемент и будет разрешающим. Если минимум отношения достигается сразу при нескольких значениях то в качестве мы берем любое из этих значений. Возможность подобного выбора вносит в расчеты некоторый элемент произвола. Теперь мы устраним этот произвол и условимся выбирать разрешающий элемент в соответствии со следующим правилом: сравниваются векторы для всех положительных и берется наименьший из них — в смысле того отношения порядка, о котором говорилось выше. Допустим, что наименьшим является Тогда в качестве разрешающего элемента берется Нетрудно понять, что этим правилом выбор разрешающего элемента определен однозначно. Действительно, средивекторов не может быть равных, в противном случае две строки матрицы оказались бы пропорциональными, что противоречит невырожденности этой матрицы.Введем в рассмотрение еще один вектор После очередного шага симплекс-метода числа, стоящие в приписанной части таблицы, конечно, изменяются; в частности, вектор заменяется другим вектором Докажем, что если исходный базис был положительным, то выполняются следующие утверждения:

1) новый базис снова будет положительным;

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

показывает, что новый базис является положительным. Наконец, заметим, что

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

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

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

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

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

• Рассчитываемая диета должна была включать 77 видов пищи. Формулировка задачи в терминах линейного программирования включала 9 уравнений с 86 неизвестными, из которых 9 были дополнительными. Оптимальное решение, конечно, удовлетворяло всем требованиям задачи.

Однако, поскольку симплекс-метод дает только базисное решение, оптимальная диета включала лишь 9 различных видов пищи (пшеничную муку, кукурузу, сгущенное молоко, растительное масло, сало, говяжью печень, капусту, картофель и шпинат). Ясно, что подобная диета не вполне отвечала бы требованиям вкуса и разнообразия пищи. Правильная постановка задачи должна, разумеется, учитывать и такие требования.

Возможно, вас также заинтересует эта ссылка:

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

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

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

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

Задача об использовании сырья. Пусть предприятие выпускает продукцию

Задача об использовании сырья                                                                                        Таблица 20.4

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

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

Пусть рассматривается задача, является моделью задачи об использовании сырья (20.5), составленная относительно только двух переменных, а именно: 

Дадим геометрическую интерпретацию этой задачи. Каждое неравенство (20.6) определяет на плоскости

Рис. 20.3

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

Рассмотрим алгоритм графического решении задачи на примере.

Цех имеет возможность производить продукцию двух видов

Расходы сырья на единицу продукции и ее запасы                                                        Таблица 20.5

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

Решение. Построим математическую модель задачи. Обозначим через

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

Кроме того, количество продукции не может быть отрицательной, то есть существует ограничение на знаки:

Следовательно, математическая модель задачи имеет вид:

Применим к решению задачи графический метод (рис. 20.4). Для построения многоугольника, что определяет множество решений системы ограничений, в первой четверти координатной плоскости построим прямые по уравнениям:

Построим линию уровня функции

Рис. 20.4

Найдем координаты этой вершины, решая систему уравнений, соответствующих линиям

Для определения решения воспользуемся формулами Крамера:

где

Отсюда имеем: 

Решение общей задачи линейного программирования

Симплекс-метод

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

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

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

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

Среди неотрицательных решений системы (8.1) нужно найти такое, которое минимизирует функцию (8.2).

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

Пример допустимой системы:

здесь свободные члены равны соответственно 5, 4 и 0. Можно ли привести систему уравнений к допустимому виду и как это сделать, рассмотрим в § 8.2.

Неизвестные в допустимом виде системы, которые выражены через остальные неизвестные, называются базисными, а весь набор этих неизвестных, который мы обозначим для краткости одной буквой — допустимым базисом; остальные неизвестные называются свободными. Например, в системе (8.3) допустимый базис образован неизвестными неизвестные же — свободные.

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

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

а система ограничений приведена к виду (8.3), то новое выражение для будет

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

а целевая функция — к виду

Напомним, что решается задача о минимизации при ограничениях (8.4) и условиях

Положим все свободные неизвестные равными нулю

и найдем из системы (8.4) значения базисных неизвестных:

Полученное таким путем решение системы (8.4)

будет неотрицательным; оно называется базисным решением, отвечающим базису Для базисного решения значение функции равно

Возможны три случая.

I. Все коэффициенты при свободных неизвестных в выражении для неотрицательны: Тогда для любого неотрицательного решения системы (8.4) имеем значит, Таким образом, т.е. базисное решение является оптимальным — задача решена.II. Имеется свободное неизвестное, коэффициент при котором в выражении отрицателен, а все коэффициенты при этом неизвестном в уравнениях (8.4) неотрицательны.Пусть, например, Будем тогда, отправляясь от базисного решения (8.6), наращивать значение (не меняя Значения базисных неизвестных также будут меняться; мы получимт.е. решение будет оставаться неотрицательным. При этом и ввиду того, что значение с ростом будет неограниченно уменьшаться. Таким образом, в этом случае т.е. задача решения не имеет.III. Имеется свободное неизвестное, коэффициент при котором в отрицателен, но и среди коэффициентов при этом неизвестном в уравнениях (8.4) также есть отрицательные.В этом случае производится шагу а именно от базиса мы переходим к новому базису с таким расчетом, чтобы значение уменьшилось или, по крайней мере, не увеличилось: Разумеется, изменение базиса влечет за собой соответствующую перестройку систем (8.4) ограничений и выражения (8.5) для функции Опишем конкретно содержание шага. Пусть, например, отрицательны, а — положительно или равно 0:Если снова, как в случае II, наращивать значение то будем иметьПоскольку значения будут уменьшаться,а значение будет оставаться неотрицательным (так как попрежнему При наращивании наступит момент, когдаодно из неизвестных или обратится в нуль: для таким моментом будет а для будет Выберем изэтих отношении наименьшее; пусть, например, это будет — Тогда наращивание возможно только от 0 до При неизвестное обратится в нуль, а при дальнейшем росте неизвестное станет уже отрицательным, что допускать нельзя. Полагая в системе (8.4) получим неотрицательное решениедля которого значение функции будет (поскольку Таким образом, с ростом ‘первым» из базисных неизвестных обращается в нуль неизвестное Это служит для нас сигналом к замене базиса а именно: из старого базиса удаляется неизвестное и вместо него в базис вводится неизвестное (из числа прежних свободных).Смена базиса, как уже говорилось, влечет за собой перестройку системы (8.4). Из первого уравнения (для выражаем и подставляем это выражение для в остальные два уравнения. В итоге получим систему вида

с базисным решением

которое должно совпадать с решением (8.8), поскольку, как видно из самой системы (8.9), двух разных решений с условиями быть не может. Таким образом, базисное решение (8.10) является снова неотрицательным.Что же касается нового значения функции то оно равнои, таким образом, (следует учесть, что и поэтому Итак, с переходом от базиса система ограничений сохранила допустимую форму ((8.10), где а значение функции для базисного решения уменьшилось или осталось прежним.Переход от базиса к новому базису и означает шагу который, напомним, делается в случае III. Разумеется, старое выражение для т.е. (8.5), должно быть теперь заменено новым:которое получается из (8.5) заменой неизвестного по формуле (8.9).Если для полученной задачи (8.10), (8.13) снова имеет место случай III, то делаем следующий шаг, т.е. переходим к новому базису длякоторого

Шаги повторяются до тех пор, пока не придем к одному из случаев I или П. Тогда процесс заканчивается.