Наиболее оптимальное решение в случае. Линейное программирование

Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных x1, x2, …, xn, удовлетворяющие m условиям - равенствам

и обращающие в максимум линейную функцию этих переменных

Для простоты предположим, что все условия (1) линейно независимы (r=m), и будем вести рассуждения в этом предположении.

Назовём допустимым решением ОЗЛП всякую совокупность неотрицательных значений x1, x2, …, xn, удовлетворяющую условиям (1).Оптимальным назовём то из допустимых решений, которое обращает в максимум функцию (2). Требуется найти оптимальное решение.

Всегда ли эта задача имеет решение? Нет, не всегда.

ЗЛП неразрешима (не имеет оптимального решения):

Из-за несовместности системы ограничений. Т.е. система не имеет ни одного решения, как показано на рисунке 1.

Рисунок 1 - Несовместность системы ограничений

Из-за неограниченности целевой функции на множестве решений. Другими словами при решении ЗЛП на max значение целевой функции стремится к бесконечности, а в случае ЗЛП на min - к минус бесконечности, как показано на рисунке 2.

Рисунок 2 - Неограниченность целевой функции на множестве решений

ЗЛП разрешима:

Множество решений состоит из одной точки. Она же и является оптимальной, как показано на рисунке 3.

Рисунок 3 - Множество решений состоит из одной точки

Единственное оптимальное решение ЗЛП. Прямая, соответствующая целевой функции в предельном положений пересекается с множеством решений в одной точке, как показано на рисунке 4.

Рисунок 4 - Единственное оптимальное решение

Оптимальное решение ЗЛП не единственно. Вектор N перпендикулярен к одной из сторон множества решений. В этом случае оптимальной является любая точка на отрезке АВ, как показано на рисунке 5.

Рисунок 5 - Оптимальное решение не единственно

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

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

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

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

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

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

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

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

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

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

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

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

Таким образом, применение симплексного метода распадается на два этапа:

Нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности;

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

Алгоритм перехода к следующему допустимому решению следующий:

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

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

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

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

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

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

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 недостижим

Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП

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

• - задача об оптимальном использовании ресурсов при производственном планировании;
• - задача о смесях (планирование состава продукции);
• - задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");
• - транспортные задачи (анализ размещения предприятия, перемещение грузов). Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:
• - математические модели большого числа экономических задач линейны относительно искомых переменных;
• - данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;
• - многие задачи линейного программирования, будучи решенными, нашли широкое применение;
• - некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования. Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных. В общем виде модель записывается следующим образом:
• - целевая функция:

C1x1 + c2x2 + ... + cnxn > max(min);- ограничения:

a11x1 + a12x2 + ... + a1nxn {? = ?} b1,

a21x1 + a22x2 + ... + a2nxn {? = ?} b2

am1x1 + am2x2 + ... + amnxn {? = ?} bm;

Требование неотрицательности:

При этом aij, bi, cj () - заданные постоянные величины. Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3). Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми. Вектор, удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программирования. План, при котором функция (2.1) достигает своего максимального (минимального) значения, называется оптимальным.

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

1. Задача об оптимальном использовании ресурсов при производственном планировании. Общий смысл задач этого класса сводится к следующему. Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц. Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида (). Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj. В планируемом периоде значения величин aij, bi и cj остаются постоянными. Требуется составить такой план выпуска продукции, при реализации которого прибыль преприятия была бы наибольшей. Далее приведем простой пример задачи такого класса.

Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В - 72 н-часа и участка С - 10 н-часов. Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?

Условия задач указанного класса часто представляют в табличной форме (см. таблицу 2.1).

По данному условию сформулируем задачу линейного программирования. Обозначим: x1 - количество выпускаемых ежедневно хоккейных клюшек, x2 - количество выпускаемых ежедневно шахматных наборов. Формулировка ЗЛП:

4x1 + 6x2 ? 120,

Подчеркнем, что каждое неравенство в системе функциональных ограничений соответствует в данном случае тому или иному производственному участку, а именно: первое - участку А, второе - участку В, третье - участку С.

Система переменных величин в задаче по оптимизации структуры посевных площадей с учётом севооборотов

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

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

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

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

Переменными задачи называются величины Х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 вводятся с коэффициентом. равным нулю.
Записываем задачу в каноническом виде:

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

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

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

Имеется несколько вариантов алгоритма симплекс-метода: обычный, 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

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

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

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