Симплексный метод решения задач линейного программирования. Какое решение можно считать оптимальным? Оптимальное решение может быть только целым

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

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

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

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

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

Алгоритм симплекс-метода включает несколько этапов:

1) подготовка информации (включает введение переменных
и формирование ограничений);

2) преобразование ограничений и запись их в матрицу;

3) поиск опорного решения;

4) поиск оптимального решения.

К примеру, имеем следующую экономико-математическую
задачу:

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

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

В уравнения дополнительные переменные не вводятся (или вводятся равными нулю):

При этом всякое решение осуществляется из допущения, что

Решение получаем поиском опорного и оптимального решений.

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

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

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

Таблица 5.1 - Симплексная таблица № 1

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

– имеются отрицательные свободные члены;

– имеются 0-значения среди базисных переменных.

Всю информацию при допущении, что заносим в таблицу. Таблица 5.1 содержит т + 2строк (где т - число строк ограничений) и п + 2 столбцов (где п - число небазисных переменных).

Коэффициенты целевой функции в таблице 5.1 записываются
с противоположным знаком.

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

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

Для записи формул, по которым определяются коэффициенты новой симплексной таблицы (таблица 5.2), введем условные обозначения, в частности, - коэффициент, стоящий в строке i
и столбце j . При этом F -строка будет иметь значение i + 1, а столбец свободных членов j = 0.

Таблица 5.2 - Симплексная таблица № 2

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

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

Правила:

1. Новый коэффициент (вместо разрешающего) равен обратному от него, т. е. или в данном случае .

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

т. е. в данном случае - при .

3. Новые коэффициенты строки разрешающего элемента равны коэффициентам предыдущей таблицы этой строки, деленным
на разрешающий коэффициент:

(при ) или , при .

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

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

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

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

Если , то получим меньшее значение, чем от деления других частных .

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

Меняем местами и , после чегопроводим расчеты
по приведенным выше четырем правилам (таблица 5.3).

Таблица 5.3 - Симплексная таблица № 3

В этой таблице содержится опорное решение. Оно получено
при следующих значениях переменных:

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

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

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

Допустим, что от деления С 3 на с 32 было получено наименьшее положительное частное. Следовательно, х 2 и х 1 меняются местами, и мы находим новое решение по четырем правилам.

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

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

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

1. Вырожденность.

2. Альтернативные оптимальные решения.

3. Неограниченные решения.

4. Отсутствие допустимых решений.

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

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

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

Рис. 2.4

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

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

Альтернативные оптимальные решения. Согласно основной теореме линейного программирования, если целевая функция достигает экстремального значения более чем в одной угловой точке, то она принимает это же значение в любой точке, являющейся их выпуклой линейной комбинацией. Графическая иллюстрация для случая двух переменных приведена на рис. 2.5. Максимальное значение целевая функция получает в угловых точках A и B . Предположим, что при использовании симплекс-метода получена точка A как оптимальный план. Тогда небазисной переменной будет соответствовать нулевая оценка, так как при ее введении в базис с последующим переходом к точке B значение функционала не изменится.

Рис. 2.5

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

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

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

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

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

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

Рис. 2.6

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

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

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

Составляющие математической модели

Основой для решения экономических задач являются математические модели.

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

• выбор переменных задачи
• составление системы ограничений
• выбор целевой функции

Переменными задачи называются величины Х1, Х2, Хn, которые полностью характеризуют экономический процесс. Обычно их записывают в виде вектора: X=(X1, X2,...,Xn).

Системой ограничений задачи называют совокупность уравнений и неравенств, описывающих ограниченность ресурсов в рассматриваемой задаче.

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

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

Данная запись означает следующее: найти экстремум целевой функции (1) и соответствующие ему переменные X=(X1, X2,...,Xn) при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3).

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X1, X2,...,Xn), удовлетворяющий системе ограничений и условиям неотрицательности.

Множество допустимых решений (планов) задачи образует область допустимых решений (ОДР).

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

Условие: Для изготовления n видов продукции используется m видов ресурсов. Составить математическую модель.

Известны:

• bi (i = 1,2,3,...,m) - запасы каждого i-го вида ресурса;
• aij (i = 1,2,3,...,m; j=1,2,3,...,n) - затраты каждого i-го вида ресурса на производство единицы объема j-го вида продукции;
• cj (j = 1,2,3,...,n) - прибыль от реализации единицы объема j-го вида продукции.

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

Решение:

Введем вектор переменных X=(X1, X2,...,Xn), где xj (j = 1,2,...,n) - объем производства j-го вида продукции.

Затраты i-го вида ресурса на изготовление данного объема xj продукции равны aijxj, поэтому ограничение на использование ресурсов на производство всех видов продукции имеет вид:
Прибыль от реализации j-го вида продукции равна cjxj, поэтому целевая функция равна:

Ответ - Математическая модель имеет вид:

Каноническая форма задачи линейного программирования

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

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

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

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

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

• А - матрица коэффициентов системы уравнений
• Х - матрица-столбец переменных задачи
• Ао - матрица-столбец правых частей системы ограничений

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

Приведение общей задачи линейного программирования к канонической форме

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

Возьмем линейное неравенство a1x1+a2x2+...+anxn≤b и прибавим к его левой части некоторую величину xn+1, такую, что неравенство превратилось в равенство a1x1+a2x2+...+anxn+xn+1=b. При этом данная величина xn+1 является неотрицательной.

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

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

Решение:
Перейдем к задаче на отыскивание максимума целевой функции.
Для этого изменим знаки коэффициентов целевой функции.
Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x4 x5 (на математической модели эта операция отмечена буквой Д).
Переменная х4 вводится в левую часть второго неравенства со знаком "+", так как неравенство имеет вид "≤".
Переменная x5 вводится в левую часть третьего неравенства со знаком "-", так как неравенство имеет вид "≥".
В целевую функцию переменные x4 x5 вводятся с коэффициентом. равным нулю.
Записываем задачу в каноническом виде:

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

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

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

Метод искусственного базиса

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

Пусть требуется найти максимум функции

при условиях

где первы n элементы нули. Переменные называются искусственными . Векторы столбцы

(28)

образуют так называемый искусственный базис m -мерного векторного пространства.

Так как расширенная задача имеет опорный план, то ее решение можно найти симплекс методом.

Теорема 4. Если в оптимальном плане расширенной задачи (24)−(26) значения искусственных переменных , то является оптимальным планом задачи (21)−(23).

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

Значение целевой функции при опорном плане (27):

Замечаем, что F(X) и состоят из двух независимых частей, одна из которых зависим от M , а другая − нет.

После вычисления F(X) и их значения, а также исходные данные расширенной задачи заносят в симплекс таблицу, как было показано выше. Разность заключается лишь в том, что данная таблица содержит на одну строку больше, чем обычная симплекс таблица. При этом в (m +1)-ю строку помещают коэффициенты, не содержащие M , а в (m +2)-ю строку − коэффициенты при M .

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

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

m +2 строки, столбца x 0 отрицателен, то исходная задача не имеет решения.

Если же не все искусственные переменные исключены из базиса и элемент m +2 строки, столбца x 0 равен нулю, то опорный план исходной задачи является вырожденным и базис содержит минимум один из векторов искусственного базиса.

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

Если в ходе итераций m +2 строка больше не содержит отрицательных элементов, то итерационный процесс продолжают с m +1 строкой, до тех пор, пока не найден оптимальный план расширенной задачи или не выявлен неразрешимость задачи.

Таким образом, процесс нахождения решения задачи линейного программирования (21)−(23) методом искусственного базиса включает следующие основные этапы:

• Составляют расширенную задачу (24)−(26).
• Находят опорный план расширенной задачи.
• Используя симплекс метод исключают искусственные векторы из базиса. В результате находят опорный план исходной задачи или фиксируют ее неразрешимость.
• Используя найденный опорный план ЗЛП (21)−(23), или находят оптимальный план исходной задачи, или устанавливают ее неразрешимость.

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

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

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

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

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

Как известно, упорядоченная совокупность значений n переменных , , … представляется точкой n-мерного пространства . В дальнейшем эту точку будем обозначать Х =( , , … ).

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

, A – матрица размера ,

Точка Х =( , , … ), удовлетворяющая всем условиям, называется допустимой точкой . Множество всех допустимых точек называется допустимой областью .

Оптимальным решением (оптимальным планом) задачи линейного программирования называется решение Х =( , , … ), принадлежащее допустимой области и при котором линейная функция Q принимает оптимальное (максимальное или минимальное) значение.

Теорема . Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

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

Точка Х называется выпуклой линейной комбинацией точек если выполняются условия

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

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

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

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

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

Из приведенных теорем вытекает важное следствие:

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

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

Данному случаю соответствует взаимная противоречивость ограничений, входящих в задачу.

2) Допустимое множество - выпуклый ограниченный многогранник.

Допустимое множество - выпуклое неограниченное многогранное множество.

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

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

1) Задача не имеет оптимальных решений .

Данный случай может возникнуть: либо тогда, когда допустимое множество решений пусто ("не из чего выбирать" оптимальный план),

либо когда допустимое множество представляет собой неограниченное многогранное множество, и целевая функция на нем неограниченно возрастает (если L  max) или неограниченно убывает (при L min).

2) Задача имеет единственное решение (единственный оптимальный план).

Это решение обязательно совпадает с одной из вершин допустимого множества.

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

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

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

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

1. Графоаналитический способ решения задач линейного программирования

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

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

(1.7)

где с 1 , с 2 , а i 1 , а i 2 , b i - заданные действительные числа; знаки в неравенствах произвольны; целевая функция либо максимизируется, либо минимизируется.

Каждое из неравенств (1.7) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми
;i =1,…,m . В том случае, если система неравенств (1.7) совместна, допустимая область решений задачи есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых значений является выпуклое множество, которое называютмногоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств.

Множеством допустимых решений для данной частной задачи может быть:

пустая область;

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

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

Практическая реализация решения задачи линейного программирования (1.6) – (1.7) на основе ее геометрической интерпретации включает следующие этапы:

1. Построить прямые, уравнения которых получаются в результате замены в ограничениях (1.7) знаков неравенств на знаки равенств.

2. Найти полуплоскости, определяемые каждым из ограничений.

Соответствующая полуплоскость может быть найдена подстановкой в неравенство координат какой-нибудь «простой» точки - (0,0), (0,1) или (1,0). Главное - чтобы эта точка не принадлежала границе полуплоскости. Если после подстановки неравенство окажется справедливым, то выбирается та полуплоскость, где содержится эта точка. Если неравенство не справедлива, то выбирается альтернативная полуплоскость.

3. Определить многоугольник решений, как пересечение найденных полуплоскостей.

4. Построить градиент целевой функции, т.е. вектор
, координатами которого служат коэффициенты целевой функцииL .

Этот вектор определяет направление наискорейшего возрастания целевой функции.

5. Построить ряд линий уровня целевой функцииL , т.е. прямых перпендикулярных градиентуL . При этом построение линий уровня следует вести в направлении градиента, если решается задача на максимум, и в противоположном направлении (в направлении «антиградиента»), если решается задача на минимум. В результате отмечается точка (точки), в которой линии уровня в последний раз касаются допустимого множества.

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

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

Заканчивая рассмотрение геометрической интерпретации задачи (1.6) – (1.7), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 1.1 – 1.3. Рис. 1.1 характеризует такой случай, когда целевая функция принимает оптимальное значение в единственной точке А, одной из вершин допустимого множества. На рис. 1.2 оптимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 1.3 изображен случай, когда оптимальное значение целевой функции недостижимо.

Рис. 1.1. Оптимум функции L достижим в точке А

Рис. 1.2. Оптимум функцииL достигается в любой точке отрезка АB

Рис. 1.3. Оптимум функции L недостижим