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

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

Если что-то непонятно — вы всегда можете написать мне в WhatsApp и я вам помогу!

Введение в методы решения линейного программирования

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

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

Возможно эта страница вам будет полезна:

Предмет математическое программирование

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

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

Прежде чем приступить к решению задач линейного программирования, следует остановиться на системах линейных уравнений. Существование решения или решений системы линейных уравнений можно обнаружить с помощью различных критериев (см. [34] *)). Система двух уравнений с двумя неизвестными

имеет единственное решение и , тогда как одно уравнение

имеет бесчисленное множество решений. Из (1.1) получаем

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

следует

а из

вытекает

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

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

имеет три следующих решения:

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

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

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

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

Требуется обратить в минимум линейную форму

при соблюдении следующих линейных ограничений:

здесь и — постоянные. Величины называют иногда коэффициентами стоимости.

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

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

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

Возможно эта страница вам будет полезна:

Решение задач по математическому программированию

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

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

Транспортная задача

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

— число складов, — число магазинов,

— общее количество единиц товара, выделяемое для перевозки -м складом, — количество единиц товара, необходимое -му магазину,

— количество единиц товара, перевозимое с -го склада в -й магазин.

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

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

Если составить таблицу, то для случая и она будет иметь такой вид:

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

Аналогично для склада 2

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

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

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

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

Объединяя уравнения (2.1)—(2.3), линейную форму (2.4) и условия неотрицательности переменных, сформулируем транспортную задачу в терминах линейного программирования:

Найти минимум функции стоимости

при условиях

Задача планирования производства

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

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

Общее количество -го ресурса, используемого согласно общему плану производства , равно

Так как эта величина не должна превосходить запаса (наличия) -го ресурса, получаем для каждого линейное неравенство вида

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

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

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

и обращающего функцию дохода

в максимум.

Как будет показано ниже, эта задача легко сводится к задаче типа (1.3) и (1.4) и, следовательно, может рассматриваться как другая формулировка общей задачи линейного программирования.

Проблема диеты

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

— число химических веществ,

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

— количество единиц -го химического вещества, содержащегося в единице -го продукта, — минимальная дневная потребность в -м химическом веществе,

— стоимость единицы -го продукта, — количество единиц -го продукта, используемое а диете .

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

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

при условиях

Замечания

Читатель может дополнительно ознакомиться с вводным материалом по работам Дорфмана [38], Купера и Чарнеса [16], Гендер-сона и Шлейфера [55] и директората Управления анализов [36].

Возможно эта страница вам будет полезна:

Примеры решения задач по математическому программированию

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

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

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

где и — заданные постоянные величины, а .

Без ограничения общности можно считать все неотрицательными, ибо в противном случае соответствующее уравнение можно умножить на — 1. В различных ситуациях удобно использовать разные виды записи общей задачи линейного программирования. Наиболее употребительными из них являются следующие:

• Минимизировать при условиях

• Минимизировать при условии и

где — вектор-строка, —вектор-столбец, — вектор-столбец и -мерный нулевой вектор-столбец.

• Минимизировать при условии

где -й столбец матрицы и .

Возможно эта страница вам будет полезна:

Заказать работу по математическому программированию

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

В этом параграфе формулируется несколько основных определений и устанавливаются наиболее важные характеристики решений общей задачи линейного программирования. Большая часть этого материала, так же как и материала гл. 4, содержится в работе Данцига [17] и книге Чарнеса, Купера и Гендерсона 112].

Определение 1. Планом задачи линейного программирования называется вектор , удовлетворяющий условиям (1.2) и (1.3).

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

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

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

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

Очевидно, что линейная форма (1.1) является линейным функционалом.

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

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

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

Подобным же образом доказывается, что множества решений системы неравенств (4.4) и системы уравнений (5.1) из гл. 2 являются выпуклыми.

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

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

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

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

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

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

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

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

для

Тогда, поскольку — линейный функционал, получаем:

где — минимум для всех из .

Поскольку все мы не увеличим сумму (2.1), если вместо каждого подставим минимальную из величин . Пусть . Отсюда, учитывая равенство

получаем

Так как, по предположению, для всех из , то

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

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

при

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

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

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

Теорема 3. Если известно, что система векторов линейно независима и такова, кто

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

Здесь -мерный вектор, последние компонент которого равны нулю.

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

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

Поскольку являются планами, получаем

Переписав эти уравнения в векторной форме, имеем

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

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

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

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

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

где по крайней мере один из коэффициентов . По условию теоремы

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

Таким образом, система уравнений (2.3) имеет два решения:

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

что противоречит предположению о том, что — крайняя точка.

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

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

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

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

Следствие 1. Каждой крайней точке из соответствует линейно независимых векторов из данной системы .

Доказательство. Теорема 4 утверждает, что имеется таких векторов. При следствие доказано. Пусть и существует не более таких векторов , что

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

Итак, каждой крайней точке соответствует линейно независимых векторов таких, что

Доказанные теоремы могут быть объединены в следующем утверждении:

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

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

Из результатов настоящего параграфа следует, что

1) существует такая крайняя точка , в которой линейная форма задачи достигает своего оптимума (минимума);

2) каждый опорный план соответствует крайней точке ;

3) с каждой крайней точкой связаны линейно независимых векторов из данной системы векторов.

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

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

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

Построение опорных планов

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

Тогда

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

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

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

положителен. Задавшись некоторой величиной , умножим на нее обе части равенства (3.2) и вычтем результат из (3.1). Получаем:

Вектор

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

для всех

Из (3.4) имеем

и, следовательно, любое , для которого

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

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

для всех то компонента , для которой достигается минимум, обращается в нуль. Пусть эта компонента стоит на первом месте, т. е.

Мы тогда получаем новый план

где

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

В этом случае при любом >0 мы не получим опорного плана. Как будет показано в гл. 4, в этом случае задача не имеет конечного минимального решения (оптимального плана).

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

причем не все = 0. Поскольку любая подсистема системы линейно независимых векторов также линейно независима, векторы линейно независимы. Отсюда следует, что . Из (3.5) имеем

где

Вычитая (3.6) из (3.2), получаем

Поскольку линейно независимы, все коэффициенты из (3.7) должны быть равны нулю. Но по предположению положительно. Следовательно, допущение линейной зависимости ведет к противоречию, т. е. эти векторы должны быть линейно независимы.

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

Пусть

— некоторый вектор, не входящий в новый базис. Подставив тогда выражение (3.8) для в (3.9), получаем

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

Пример:

Зададимся следующей системой уравнений

В качестве исходного опорного плана принимаем

Отсюда получаем векторное равенство

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

откуда

Умножая (3.11) на и вычитая полученный результат из (3.10), получим

Поскольку оба положительны, то

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

Таким образом, компоненты нового опорного плана суть

Если провести те же самые преобразования, заменив вектор на вектор , где

то получим разложение для по векторам :

Из (3.13) очевидно, что при любом >0 получается план

Поскольку все <0, мы здесь не сможем получить новый опорный план.

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

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

Здесь

Получаем, таким образом, базис

явно выражаются через его векторы в виде

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

Возможно эта страница вам будет полезна:

Помощь по математическому программированию

Симплексный метод

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

Отыскание оптимального плана

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

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

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

где — коэффициент линейной формы задачи, соответствующий вектору .

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

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

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

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

Умножив (1.3) и (1.4) на некоторое число и вычтя результаты из (1.1) и (1.2) соответственно, получаем

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

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

Доказательство в случае 1 проводится следующим образом:

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

где минимум берется по всем >0 (см. § 3 гл. 3). Поскольку мы предположили рассматриваемую задачу невырожденной, т. е. что все ее опорные планы содержат положительных компонент, минимум в (1.7) будет достигаться при единственном . Если подставить вместо в (1.5) и (1.6), то коэффициент, соответствующий этому единственному , обратится в нуль. Таким образом, получен новый опорный план, базис которого состоит из и (—1)-го вектора первоначального базиса. С новым базисом могут проводиться те же операции, что и с предыдущими. Если снова одна из разностей и соответствующее > 0, можно перейти к другому опорному плану, связанному с еще меньшим значением линейной формы. Процесс продолжается до тех пор, пока либо все разности станут неположительными, либо для некоторой разности окажутся неположительными все . Если все , процесс закончен.

Доказательство в случае 2 проводится так:

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

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

Теорема 2. Если для некоторого опорного плана ) справедливы неравенства , , то план является оптимальным*).

Доказательство. Пусть произвольный план,

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

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

Подставив соответствующее каждому выражение для по формуле (1.3) в (1.8), имеем:

или, меняя порядок суммирования,

Аналогично, подставляя для каждого выражение из формулы (1.4) в неравенство (1.10), получаем:

Поскольку система векторов линейно независима, коэффициенты при соответствующих векторах в (1.1) и (1.11) должны быть равны*). Поэтому из формулы (1.12) следует:

или, согласно (1.2), .

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

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

Данциг, Орден и Вольф [32] и Чарнес, Купер и Гендерсон [12] рассмотрели явление вырожденности с теоретической и вычислительной точек зрения. Опыт вычислений, однако, не оправдывает включения их способа устранения вырожденности в обычный симплексный алгоритм. Из множества задач линейного программирования, рассмотренных исследователями на практике, цикл был обнаружен лишь в грех. Примеры циклов были построены Гофманом |58| и Билом [4]. Обычно при вычислениях с вырожденным планом обходятся тай же, как и с невырожденным. Если

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

В гл. 7 мы подробно остановимся на явлении вырожденности и рассмотрим пример цикла, построенный Билом.

Алгоритм симплексного метода

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

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

получаем

и

где

и

— векторы-столбцы.

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

или

Умножив элементы разбитой на части матрицы (2.1) на получим

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

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

Отмечу, что в большинстве практических задач имеет место случай 2. Поэтому он будет рассмотрен более подробно.

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

Предположим, что этими векторами будут .

Тогда матрица

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

где

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

В рассматриваемой задаче, записываемой в виде , положим

для

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

Элементы и помещаются на соответствующие места -й строки таблицы 1. Разности для векторов базиса всегда равны нулю. Если все разности для

то план

является оптимальным и минимальное значение линейной формы равно .

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

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

Положим, что

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

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

Поскольку первоначальный базис

Из (2.3)

Подставив выражение для в (2.2), получаем

или

Таким образом, новый план

, определяемый соотношением

вычисляется по формулам

Аналогично, подставляя (2.5) в (2.4), получаем разложение каждого вектора , не входящего в базис нового плана, по векторам этого базиса

где

Поскольку

непосредственное применение формул (2.7) дает

Аналогично, подставляя выражение для из (2.6) в соотношение

получаем

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

где

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

После того как исходная таблица заполнена, вычисления отдельной итерации производятся в такой последовательности:

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

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

• После выделения направляющей строки и направляющего столбца таблица, соответствующая старому плану, преобразуется по формулам (2.8).

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

После проведения первой итерации получаем таблицу 2.

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

Минимизировать

при условиях

и

Исходный базис (см. табл. 3, первая итерация) состоит из векторов ; ему соответствует план (7, 12, 10). Поскольку

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

равно минимуму для , т. е.

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

соответствующий значению линейной формы, равному — 9. Имеем:

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

соответствующий значению линейной формы, равному —11. Так как

то этот план является оптимальным. Для контроля вычислений величины и полезно определять двояким способом: непосредственно и по рекуррентным формулам (2.8).

Если для оптимального плана некоторая разность = 0 и вектор не входит в последний базис, его можно ввести

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

Возможно эта страница вам будет полезна:

Задачи математического программирования

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

До сих пор мы предполагали, что рассматриваемая задача линейного программирования обладает планами и содержит единичную матрицу, из которой может быть составлен первоначальный базис. Несмотря на то, что корректная постановка задачи обычно гарантирует наличие у нее плана, многие задачи линейного программирования не содержат единичной матрицы. В таких случаях удобно использовать метод искусственного базиса (см. Орден [84]). Этот метод, в частности, позволяет определить, имеет ли вообще задача планы, или же их нет.

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

при условиях

Рассмотрим расширенную задачу, связанную с минимизацией линейной формы

переменные которой подчинены условиям

и для

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

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

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

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

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

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

Эта таблица обрабатывается совершенно аналогично обычной первоначальной симплексной таблице (табл. 1), за исключением того, что вектор, вводимый в базис, связывается теперь с наибольшим положительным элементом -й строки. В первой итерации в базис вводится вектор, соответствующий . Элементы -й строки преобразуются в соответствии с рекуррентными формулами (2.8). Искусственный вектор, исключенный из базиса в результате некоторой итерации, не имеет смысла в дальнейшем вводить ни в один из последующих базисов, и, следовательно, преобразование последних столбцов таблицы излишне. Однако при необходимости обращения окончательного базиса (получения соответствующей обратной матрицы) последние векторов также подлежат преобразованию *). Следует заметить, что иногда в результате отдельной итерации ни один из искусственных векторов не исключается. Для получения оптимального плана при использовании полного искусственного базиса требуется приблизительно 2. итераций.

Руководствуясь элементом -й строки как критерием, продолжают отбирать вектор для введения в базис до тех пор, пока либо

1) все искусственные векторы будут исключены из базиса, либо

2) -я строка не будет больше содержать положительных элементов в столбцах с номерами от 1 до .

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

Теорема 2 утверждает, что не существует другого плана, на котором значение линейной формы будет меньше, чем при этом последнем плане. Если элемент , 0) равен нулю, полученный план первоначальной задачи — вырожденный и содержит по меньшей мере один из векторов искусственного базиса.

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

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

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

Возможно эта страница вам будет полезна:

Задача линейного программирования

Пример:

Максимизировать

при условиях

Эта задача эквивалентна минимизации линейной формы

при сохранении прежних ограничений.

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

причем соответствующее ему значение линейной формы равно 10+35. каждое совпадает со скалярным произведением вектора и вектора-столбца . Например,

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

Преобразуем все элементы первой части таблицы о (первая итерация) по рекуррентным формулам (2.8). Новым планом является

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

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

при значении линейной формы, равном . В результате четвертой итерации получаем решение

при и значении линейной формы, равном — 15. Оптимальное значение линейной формы равно 15, поскольку первоначально мы имели дело с задачей на максимум.

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

Если первоначальная задача была поставлена в виде , то, вообще говоря, необходимо введение искусственных векторов. Далее это описывается в § 1 гл. 10.

Возможно эта страница вам будет полезна:

Примеры решения задач по линейному программированию

Геометрическая интерпретация симплексного метода

Симплексный метод, изложенный ранее с алгебраической точки зрения, имеет геометрическую интерпретацию, описанную Гофманом, Манносом, Соколовским и Вигманом [61 а]. Впервые она была дана Данцигом |17].

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

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

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

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

Поясним сказанное примером. Рассмотрим задачу отыскания минимума линейной формы

при условиях

Имеем

Изобразим эти точки, как показано на рис. 14. Поскольку прямая пересекает конус , задача обладает планами. Можно

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

Поскольку , то в базис следует ввести вектор .

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

вектор . Этот последний базис, состоящий из векторов и , соответствует оптимальному плану.

Симплексный процесс может быть также интерпретирован как движение по соседним крайним точкам *) многогранника условий задачи (см. § 4 гл. 2 и Саати [88J).

На рис. 16 изображен многогранник , определяемый условиями задачи. Крайняя точка, от которой начинается процесс, обозначена через . Через эту точку проведена прямая вида

где — линейная форма рассматриваемой задачи.

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

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

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

Проблема двойственности в линейном программировании

С каждой задачей линейного программирования, определенной в § 1 гл. 4, можно связать некоторую другую линейную задачу, называемую двойственной *). Первоначальную задачу будем называть исходной. Оптимальный план Одной из задач тесно связан с оптимальным планом другой задачи. Если начальная симплексная таблица исходной задачи содержит единичную матрицу порядка , то симплексный процесс, примененный к одной из задач, автоматически приводит к решению другой задачи. В настоящей главе будут сформулированы и доказаны теоремы, связанные с двойственными задачами, принадлежащие Данцигу и Ордену [31]. Дополнительные сведения по этим вопросам читатель Может почерпнуть из работ Гэйла, Куна и Таккера [45], Вайда [97] и Куна и Таккера [68].

Возможно эта страница вам будет полезна:

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

Несимметричные двойственные задачи

Исходная задача **). Определить вектор-столбец

минимизирующий линейную форму

при условиях

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

Двойственная задача. Найти вектор-строку , максимизирующий линейную форму

при условиях

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

Матрица коэффициентов вышенаписанных неравенств совпадает с .

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

Если линейная форма одной из задач не ограничена (для исходной — снизу, для двойственной — сверху), то другая задача не имеет ни одного плана.

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

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

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

Оптимальный план совпадает с вектором причем имеют место следующие соотношения:

где — вектор-строка. Согласно (1.4) я результатам гл. 4,

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

Пусть определяется из соотношения

Тогда согласно (1.6) и (1.9) имеем

Вектор , таким образом, является планом двойственной задачи, поскольку он удовлетворяет ее условиям (1.5), При этом соответствующее значение линейной формы двойственной задачи (1.4) равно . Учитывая, далее, соотношения (1.7) и (1.8), получаем

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

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

Для любого -мерного вектора , удовлетворяющего условиям (1.2) и (1.3), и любого -мерного вектора , удовлетворяющего условиям (1.5), получаем

Сравнивая (1.11) и (1.12), приходим к неравенству

справедливому для любых и , являющихся планами двойственной и исходной задач соответственно. Отсюда следует, что экстремальные значения (1.1) и (1.4) связаны соотношением

Для плана двойственной задачи согласно (1.10) имеем

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

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

Для доказательства второй части заметим, что в случае неограниченности линейной формы исходной задачи из (1.13) следует

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

Возможно эта страница вам будет полезна:

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

Пример:

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

при условиях

и

Здесь

Двойственная задача. Максимизировать

при условиях

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

Соответствующим решением является

и минимальное значение линейной формы равно

Из окончательной симплексной таблицы (см. табл. 4, третья итерация) получаем

Вектор для оптимального плана равен

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

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

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

Подставляя этот план в условие двойственной задачи, получаем :

Значение двойственной линейной формы равно

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

По определению

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

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

Заметим, что если в исходной симплексной таблице единичный вектор с -й компонентой, равной единице, расположен в -м столбце, то .

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

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

Возможно эта страница вам будет полезна:

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

Симметричные двойственные задачи

Исходная задача. Найти вектор минимизирующий линейную функцию

при условиях

Двойственная задача. Найти вектор , максимизирующий линейную функцию

при условиях

Покажем теперь, что теорема двойственности из § 1 справедлива также и для симметричных двойственных задач.

Преобразуем условия (2.2) исходной задачи с помощью неотрицательных компонент вектора в систему равенств. Матричная запись эквивалентной задачи линейного программирования имеет следующий вид: Минимизировать

при условиях

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

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

при условиях

Очевидно, что неравенство (2.11) расщепляется на неравенства (2.5) и (2.6), т. е. и — . Последнее неравенство равнозначно условию .

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

Как указывалось Голдманом и Таккером [51], симметричные двойственные задачи удобно представлять с помощью следующей таблицы:

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

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

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

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

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

является оптимальным планом задачи минимизации

при условиях

Исследуем вкратце экономическую интерпретацию задачи планирования производства, упомянутой в § 2 гл. 1, и двойственной ей задачи *). Исходная задача заключается в максимизации

при условиях

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

при условиях

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

при условиях

Двойственная задача сводится к минимизации

при условиях

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

при условиях

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

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

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

Переменные именуются в различных источниках по-разному. Например, они называются учетными, неявными или фиктивными ценами.

Допустим, что при помощи симплексного метода определено решение задачи планирования производства. Поскольку линейная форма максимизировалась, все входящие и не входящие в базис векторы имеют соответствующие разности . Вследствие некоторых внешних условий, например правительственного регулирования производства или рыночной конъюнктуры, задача может обусловить, что производство -гo вида продукции должно быть в заключительном решении положительным. Однако оптимальный базис может не включать вектора . Мы должны тогда изменить наш оптимальный план, введя в его базис вектор и отказавшись от производства какого-либо другого вида продукции. Если предположить, что решение задачи единственно, то и введение в базис вектора уменьшает максимальное значение линейной формы на величину . Эта величина совпадает с убытком предпринимателя под влиянием внешних условий. Величина равна чистой стоимости производства единицы 6-го вида продукции, где — косвенная стоимость единицы -го вида продукции, a — ее прямая стоимость. Проанализировав симплексную таблицу оптимального плана задачи планирования производства, можно получить соотношение между чистыми стоимостями и учетными ценами факторов производства. Система косвенных стоимостей, т. е. элементов , соответствующих дополнительным переменным, совпадает с системой учетных цен, решающей двойственную задачу*). Если все дополнительные переменные входя г в окончательный базис, то не производится никакой продукции, не используется никаких средств и максимальный доход равен нулю. Применительно к двойственной задаче это означает, что минимальная величина всех затраченных средств также равна нулю. Это следует из равенства нулю всех косвенных стоимостей, соответствующих дополнительным переменным **). Если решение исходной задачи не включает в себя никаких дополнительных переменных, принимающих положительные значения, исходная задача приводит к оптимальному доходу при использовании всех имеющихся ресурсов. В этом случае ни одна из косвенных стоимостей, соответствующих дополнительным векторам, не равна нулю, минимальное значение общих затрат положительно и равно максимальному доходу.

В заключение этого параграфа, посвященного симметричным двойственным задачам, дадим формулировку следующей теоремы Данцига и Ордена [31а]:

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

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

Возможно эта страница вам будет полезна:

Заказать работу по линейному программированию

Модифицированный симплексный метод

Использование обычной формы обратной матрицы

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

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

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

где — вектор-столбец, компонентами которого являются искомые коэффициенты. Таким образом,

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

при условиях

Если допустить, что матрица , соответствующая первым векторам , такова, что

где , то опорный план выражается в виде

Разложения векторов, составляющих матрицу , по векторам базиса определяются формулой (1.1) для

В § 1 гл. 4 для базиса любого опорного плана были определены величины

для , где — коэффициент линейной формы. С помощью (1.1) равенство (1.3) может быть переписано в виде

где — вектор-строка. Следовательно, задавшись для базиса В некоторого плана вектором-строкой

можно подсчитать соответствующее . Из соотношений (1.1), (1,2) и (1.4) следует, что данные, необходимые для перехода от одного опорного плана к другому, могут быть получены, если известны для каждого базиса обратная матрица и условия задачи, состоящие из матрицы и векторов . Эти соображения послужили основанием для построения так называемого модифицированного симплексного метода, являющегося некоторым усовершенствованием обычного симплексного процесса (Данциг, Орден и Вольф [32] и Данциг [20]. [21]).

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

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

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

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

Рассмотрим новый базис который отличается от старого базиса тем, что вектор заменен на вектор . Имеем тогда

и из (1.1)

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

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

или

Первая скобка (1.7) является скалярным произведением первой строки матрицы на , которое согласно (1.5) равно 1; вторая скобка содержит скалярное произведение -й строки на которое равно 0. Следовательно, выражение (1.7) равно 1. Аналогичным образом вычисляя элементы произведения матриц, можно показать, что и, следовательно, формулы (1.6) определяют .

Перейдем теперь к описанию вычислительной схемы модифицированного симплексного метода, развитой Данцигом [1&] и Орчардом-Хейсом [81]. Мы не будем рассматривать модифицированный симплексный метод так же подробно, как это было сделано при описании обычного симплексного метода в гл. 3 и гл. 4.

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

Для облегчения использования модифицированного процесса ниже вводятся и определяются две новые переменные

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

при условиях

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

задача (1.8) — (1.10) эквивалентна задаче минимизации

при условиях

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

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

где

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

при условиях

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

Из (1.11) и (1.13) получаем

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

Как следует из соотношений (1.12) — (1.14), расширенная задача состоит из уравнений с переменными. В этой задаче опорный план должен содержать переменных из системы .

Знаки двух последних переменных не оговариваются, и эти переменные всегда входят в план. Если в оптимальном плане расширенной задачи переменные при равны 0, величины составляют оптимальный план задачи (1.8) — (1.10) при значении линейной формы, равном . Этот план является также оптимальным для задачи (1.8а) — (1.10а), причем соответствующее значение линейной формы равно — .

Вычислительный процесс для расширенной задачи начинают с опорного плана, включающего дополнительных переменных и переменные и . Для отыскания первого опорного плана *) необходимо применить этап I процесса, где задача о максимизации при условиях (1.13) и (1.14) решается без всяких ограничений на знаки переменных и . Если максимальное значение оказывается равным нулю, то все для также должны быть равны нулю, и переменные при , входящие в полученный оптимальный план, представляют опорный план для задач (1.8) — (1.10) и (1.8а) — (1.10а). Если максимум меньше нуля, то из этого вытекает, что по меньшей мере одна из дополнительных переменных в решении этапа 1 не равна нулю, и, следовательно, исходная задача не имеет ни одного плана. В первом случае осуществляется переход к этапу И, на котором максимизируется при условиях (1.13) и (1.14). При этом полагается, естественно, равным нулю. Окончательным результатом этапа II является искомый оптимальный план.

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

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

Обозначим -й вектор-столбец матрицы через . Сравним, матрицу с исходной таблицей вычислений по методу искусственного базиса для обычного симплексного процесса (см. табл. 4 гл. 4). Очевидно, что матрица, образованная из строк столбцов таблицы, совпадает с матрицей , за исключением того, что -я и -я строки матрицы равны соответствующим строкам таблицы, взятым со знаком минус. Как и в обычном методе, для подсчета разностей при наличии в плане искусственных переменных используется -я строка, а в случае их исключения — -я строка.

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

Первые строк и столбцов матрицы совпадают с обращенным начальным базисом . Две последние строки используются для определения вектора, подлежащего вводу в базис, причем на этапе I данные берутся из -й строки, а на этапе II — из -й. Примем матрицу за исходную вычислительную таблицу и преобразуем ее элементы описанным ранее способом. Обозначим через элементы матрицы и через векторы-строки — строки этой матрицы. Для удобства описания вычислительного процесса примем, что через обозначена как первоначальная, так и преобразованная -я строка матрицы . Матрица является обратной по отношению к матрице порядка , столбцами которой являются векторы из условий (1.13). Расположим матрицу и исходный план для =

как показан в исходной части таблицы 6. Этапы состоят из следующих шагов:

Этап I. План содержит положительные искусственные переменные.

Шаг 1. Если

подсчитываем

и переходим к шагу 2.

Если

переходим к шагу 1 этапа II. Шаг 2. Если все

является максимумом и, следовательно, задача (1.8) — (1.10) не имеет ни одного плана.

Если по крайней мере одна из , то индекс переменной , которая подлежит вводу в план, определяется формулой

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

для

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

минимум берется только для

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

Шаг 4. Новые значения переменных в опорном плане определяются по формулам

Новые элементы матрицы преобразуются по формулам

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

Этап II. Искусственные переменные плана , равны нулю.

Шаг 1. Здесь = 0. Подсчитываем

Шаг 2. Если все , то достигают своей максимальной величины и соответствующий опорный план является оптимальным. Величина , взятая со знаком минус, совпадает с минимальным значением линейной формы исходной задачи.

Если по крайней мере одно из , необходим переход к новому базису. Пусть

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

Шаг 3. Подсчитываются

для

Переменная , подлежащая исключению из старого плана, определяется из соотношения

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

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

Если все , линейная форма Задачи не ограничена сверху.

Шаг 4. Новые значения переменных определяются соотношениями

Элементы матрицы преобразуются по формулам

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

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

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

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

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

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

Возможно эта страница вам будет полезна:

Помощь по линейному программированию

Пример:

Максимизировать

при условиях

Здесь

Линейная форма соответствующей задачи минимизации равна

Сформулируем пример применительно к модифицированному процессу с полным искусственным базисом: Максимизировать при условиях

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

Коэффициенты при переменных

пятого уравнения и правая часть этого уравнения получены по формулам (1.11).

Матрицей в примере является

а матрицей

Вся последовательность вычислений представлена в таблице 7.

Возможно эта страница вам будет полезна:

Контрольная работа по линейному программированию

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

Выше выведены формулы (1.6), дающие возможность вычислять матрицу, обратную базису , который отличается от базиса с известной обратной матрицей лишь одним вектором. Используя обозначения § 1, имеем:

Выпишем матрицу:

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

Следовательно, умножение на слева эквивалентно применению формул (1.6). Как и в (1.6), это преобразование можно проделать, зная лишь и Если принять

то можно записать как

Итак, элементарная матрица полностью определяется индексом особого столбца и совокупностью его элементов . Используя сокращенную запись, положим

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

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

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

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

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

где

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

Заметим здесь, что в произведении любого вектора-строки

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

На третьем шаге лучше всего подсчитывать по формуле

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

Новая элементарная матрица и текущий план получаются на четвертом шаге по формулам

где и определяются из соотношений (2.1) и (2.2).

Описанные выше преобразования применяют и к этапу II, на котором вместо подсчитывается

где

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

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

Вырожденные задачи

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

все коэффициенты и по крайней мере один из них равен нулю. В гл. 4 при обосновании симплексного процесса предполагалась невырожденность всех опорных планов задачи. Это допущение гарантировало уменьшение значения линейной формы после каждой итерации симплексного метода. Так как любая задача обладает лишь конечным числом базисов, то оптимальный план определяется в этом случае через конечное число итераций. Приведенное доказательство теряет силу, как только мы допустим существование вырожденных опорных планов, что является, разумеется, более близким к действительности. В случае вырожденного плана может оказаться, что (см. формулы (1.6) и (1.7) гл. 4). Тогда при переходе к новому опорному плану мы не изменим значения линейной формы задачи *). Теоретически возможно выбрать последовательность базисов, приводящую к циклу, т. е. последовательность базисов, периодически выбирающихся и не удовлетворяющих критерию оптимальности. Очевидно, что в этом случае оптимальный план никогда не будет достигнут. Возможность зацикливания реальна только в том случае, когда в текущем опорном плане более чем для одного (см. упражнение 2 гл. 4). В случае, если по крайней мере для двух значений , существует возможность появления неоднозначности при выборе вектора, подлежащего исключению из базиса при . Отмеченная неоднозначность может иметь место и в невырожденной ситуации. Однако в этом случае и новый план приводит к уменьшению значения линейной формы. При этом вследствие неоднозначности, имевшейся в старом плане, новый план будет вырожденным.

Приведенные выше замечания показывают, что любой способ распространения вычислительных методов на вырожденные задачи должен гарантировать единственность выбора вектора, подлежащего исключению из базиса. Было предложено несколько таких способов (Данциг [17), Чарнес [9] и Данциг, Орден и Вольф [32]). Опыт конкретных вычислений уменьшил значение этих приемов, так как до сих пор ни одна из практических задач не привела к зацикливанию. Другими словами, успешное решение сотен задач не зависело от применения таких методов. По этой причине они не включаются в большинство вычислительных программ. Тем не менее следует отметить, что приемы, гарантирующие от зацикливания, делают симплексный метод пригодным для доказательства многих теорем без ограничения общности (Гофф-ман [59]).

Способы устранения зацикливания

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

положительную комбинацию векторов достаточно малой, полагая ее (см. Чарнес [9|) равной

где — некоторое малое положительное число. Ограничения новой задачи принимают вид

Геометрическая интерпретация условий представлена на рис. 18.

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

в виде

Пусть векторы

образуют базис . Тогда

является планом исходной задачи и

— планом измененной задачи. Пусть

Тогда соотношение (1.4) можно представить в виде

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

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

(Условия задачи всегда можно перенумеровать таким образом, чтобы векторы базиса занимали первые мест.) Для определения вектора подлежащего исключению из базиса задачи (1.2), вычисляем

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

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

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

Если

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

Например, если для базиса

то подсчитываем

и сравниваем результаты. Если

то вектор подлежит исключению. Если

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

Если

образуем отношения

и опять проводим сравнение до тех пор, пока не будет получено неравенство. Из (1.8) следует, что для некоторого это обязательно случится.

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

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

Применительно к модифицированному процессу можно предложить другой эффективный способ решения вырожденной задачи, требующий лишь знания обратной матрицы текущего базиса (Данциг, Орден и Вольф [32]). Мы не будем здесь подробно излагать этот метод, а сформулируем лишь правило однозначного определения вектора, выводимого из базиса. Это правило, данное Данцигом, заключается в следующем:

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

Примеры зацикливания

В литературе имеется только два примера задач, в которых при решении по обычному симплексному методу встречается зацикливание (Гоффман [58] и Бил [4]). Известный пример Била [4] относится к двойственной задаче. Здесь мы проиллюстрируем явление зацикливания в терминах исходной задачи. Приводимый ниже пример, также принадлежащий Билу, публикуется впервые.

Задача заключается в минимизации

при условиях

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

Однако при использовании правила, описанного в § 1 этой главы, можно выбрать другую последовательность планов, приводящую к решению задачи. Соответствующие итерации сведены в таблицу 9, где шестой план является оптимальным. Мы видим, что в процессе решения ни один из планов не повторяется. Неоднозначность при подсчете 60 появляется в первой и третьей итерациях. Первые три плана таблиц 8 и 9 совпадают. Различие начинается при переходе от третьего к четвертому плану, где во втором случае вместо вектора исключается . Минимальное значение линейной формы равно — .

Возможно эта страница вам будет полезна:

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

Параметрическое линейное программирование

Линейная форма с коэффициентами, зависящими от параметра

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

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

Исследования по параметрическому программированию применительно к изменению коэффициентов линейной формы возникли в связи с изучением задачи планирования производства, описанной в § 1 гл. 11 **). Там вводится параметр