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

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

Если что-то непонятно — вы всегда можете написать мне в 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 **). Там вводится параметр , равный отношению стоимости увеличения выпуска продукции на единицу за один месяц к стоимости хранения единицы продукции за то же время. Прежде чем выбрать некоторый график производства, оптимальный для определенного значения параметра , может оказаться полезным исследовать предварительно систему графиков производства, оптимальных для целого интервала изменения . Благодаря этому можно принять более точное решение, которое не только лучше всего соответствует производственным возможностям и возможностям хранения, но также подходит и по факторам, не включенным в модель линейного программирования. Ниже описывается процесс, дающий возможность определить для различных интервалов соответствующие оптимальные планы. Эта вычислительная схема является некоторым видоизменением обычного симплексного метода.

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

при условиях

где — заданные постоянные. Допустим, что рассматриваемая задача не вырождена и нам известен некоторый опорный план системы (1.2). Используя симплексный метод, можно либо решить задачу при (случай А), либо убедиться, что линейная форма (1.1) при не ограничена снизу на выпуклом множестве, определяемом условиями (1.2) (случай В).

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

Тогда, поскольку мы имеем дело со случаем А,

что означает, что система неравенств

совместна. Для всех

и для всех

Пусть

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

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

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

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

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

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

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

Остается показать, что любое не удовлетворяет системе неравенств (1.5). Имеем

Допустим, что системе неравенств (1.5) удовлетворяет некоторое . Тогда, в частности,

или согласно (1.4) и (1.6)

Поскольку , из последнего неравенства следует

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

Случай В. Здесь возможны две ситуации.

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

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

Пусть

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

и процесс можно продолжать, как и в случае А.

Если не все

в базис можно ввести любой вектор, для которого

Процесс продолжается до тех пор, пока не окажется, что либо

для либо пока не будет обнаружен вектор с

все коэффициенты разложения которого по базису неположительны. Если

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

где , не ограничена снизу.

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

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

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

Если все , то для оптимальных планов не существует.

Подводя итоги, можно заключить, что

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

При помощи электронных вычислительных машин были решены многие крупномасштабные задачи линейного программирования с параметрической линейной формой. Одна из таких задач с 33 уравнениями и 65 неизвестными была решена для всех положительных значений параметра за 53 итерации. Полное решение включало 23 критических решения. Все рассмотренные задачи имели оптимальный план для = О, и исследуемая область изменения параметра составляла полупрямую . В качестве исходного для параметрического процесса принимался оптимальный план задачи при = 0. Этот план вычислялся с помощью обычного симплексного процесса.

Пример:

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

при условиях

где

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

с соответствующей линейной формой

В первой части таблицы 10 система (1.8) записана в виде обычной симплексной таблицы. Поскольку система условий задачи содержит единичный вектор , достаточно использовать лишь искусственный вектор с большим положительным весом w. Таким образом, исходный базис состоит из векторов . Элементы записываемые в виде вводятся в -ю, -ю и -ю строки соответственно. Например, вектор имеет , следовательно, мы вводим 0, —1 и 3 в соответствующие строки под . Значение линейной формы . Поскольку вектор имеет наибольшую положительную величину в -й строке, он вводится в базис, а исключается из базиса (вторая итерация). Подобным же образом вектор заменяется на в третьей итерации. Теперь, поскольку все элементы -й строки равны нулю,

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

Значение линейной формы

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

Вводя в базис вектор

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

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

Поскольку все линейная форма

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

— и не единственный оптимальный план при . Применение рассмотренного здесь метода к решению задач теории игр дано в гл. 12.

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

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

Параметрическая двойственная задача

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

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

который минимизирует

при условиях

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

Поскольку система неравенств

совместна.

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

Для имеем

Положим

Если

Положим

Очевидно, что план (2.1) оптимален для всех из интервала

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

При достаточно большом увеличении одна из величин

становится отрицательной. Если — первая из компонент, меняющих знак, то

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

Теорема 2. Если вектор , соответствующий , исключается из базиса и в базис вводится вектор , для которого

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

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

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

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

Действительно,

откуда

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

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

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

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

Если все , то исследуемая задача при не имеет ни одного плана. Доказательство этого утверждения предоставляется читателю (см. § 2 гл. 9).

Дополнительные вычислительные приемы

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

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

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

В этой главе будут изложены некоторые приемы, позволяющие сократить объем вычислительной работы для большинства задач линейного программирования. Эти приемы приводят к уменьшению общего числа итераций, требуемых для получения оптимального плана. Некоторые из них описываются ниже, в § 1. Предварительно следует рассмотреть ряд особенностей симплексного метода. Симплексный метод подразделяется на два различных вычислительных этапа. Этап I связан с определением исходного плана; этап II, начинающийся с этого плана, ведет к построению оптимального плана. Опыт вычислений показывает, что для решения задачи требуется примерно итераций (где — число уравнений рассматриваемой задачи), если вычисления начинаются с имеющегося базиса, состоящего из единичных векторов. При использовании полного искусственного базиса число итераций увеличивается примерно до 2. Очевидно, что выгодно либо совсем исключить этап I, либо начать вычисления с возможно меньшего числа искусственных векторов.

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

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

Большинство вычислительных приемов, позволяющих получить «хорошее» первое приближение, основывается на приведенных здесь соображениях и связано с видоизменениями симплексного алгоритма (Гасс [461 и Орчард-Хейс [82]).

Определение исходного плана

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

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

1. Система не содержит единичных векторов, и вычисления начинаются с полного искусственного базиса.
2. Система содержит различных единичных векторов, и этап I процесса начинается при наличии искусственных векторов.
3. Система содержит базис, состоящий из единичных векторов, и вычисления начинаются с этапа II.

Если система условий задачи имеет вид

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

Третья форма условий задачи имеет вид

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

где

— неотрицательный вектор-столбец.

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

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

Рассмотрим для иллюстрации этой схемы систему неравенств

Перепишем систему (1.6) в виде системы уравнений

Здесь

Применяя формулы (1.5) и (1.7), получаем окончательную систему уравнений:

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

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

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

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

• Система векторов линейно независима (обратная матрица существует).

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

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

• Система векторов линейно зависима, и матрица ее имеет ранг . В этом случае можно перейти к этапу I, введя либо , либо искусственных векторов (более подробно об этом смотри Гасс [46]). Можно также продолжать выбор векторов из числа оставшихся до тех пор, пока не будет получена линейно независимая система из векторов. Порядок дальнейшего выбора может быть подсказан конкретной задачей (по этому поводу см. работу Орчарда-Хейса [82]).

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

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

Формулы (1.8), справедливые для , соответствуют вычитанию -й строки таблицы из всех других строк и умножению -й строки на —1. Это преобразование приводит к базису, состоящему из — 1 векторов из числа выбранных и одного искусственного вектора, соответствующего переменной Новыми элементами -й строки являются:

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

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

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

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

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

Такую задачу можно решить следующим способом.

Пусть исходная задача заключается в минимизации

при условиях

Одновременно с (1.10) — (1.12) необходимо также решить следующую совокупность задач:

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

при условиях

Сначала решается задача (1.10) — (1-12). При использовании обычного симплексного метода таблица дополняется векторами , которые преобразуются обычным образом. Если после определения оптимального плана задачи (1.10)— (1.12) все компоненты всех останутся неотрицательными, то этот план является оптимальным для всех . Предположим теперь, что для некоторого не все компоненты преобразованного вектора неотрицательны. Для получения исходного плана этой задачи найдем минимальную компоненту преобразованного вектора и применим формулы (1.8) и (1.8′). В результате образуется базис, состоящий из одного искусственного вектора и — 1 векторов из базиса предшествующего оптимального плана. После этого задача решается обычным способом.

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

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

для всех . Здесь — вектор-строка. Таким образом, служит базисом оптимального плана задачи (1.10) — (1.12). Допустим, что не является базисом ни одного из планов задачи, связанной с ограничениями

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

при условиях

Из (1.13) следует, что базис связан с планом двойственной задачи . Действительно,

Этот план двойственной задачи не является ее решением. Вычислительный способ, связанный с решением двойственной задачи и называемый двойственным симплексным методом, был впервые предложен Лемке [70].

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

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

при условиях

Соответствующая двойственная задача формулируется следующим образом:

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

при условиях

Допустим, что мы выбрали такой базис

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

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

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

2) значение линейной формы двойственной задачи увеличится или останется неизменным *).

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

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

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

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

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

причем соответствующее значение линейной формы равно

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

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

Для преодоления вырожденности в двойственной задаче Лемке [70| ввел в рассмотрение измененную двойственную задачу с ограничениями

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

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

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

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

при условиях

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

при условиях

Исходным базисом является

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

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

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

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

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

Общее для обеих задач оптимальное значение линейной формы равно 2.

Существуют достаточно эффективные способы решения общей задачи линейного программирования, основанные на комбинированном использовании общего симплексного процесса и двойственного метода. Такими способами являются комбинированный симплексный алгоритм (Данциг [23] и Орчард-Хейс [83]) и альтернативный *) алгоритм (Данциг,

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

Все упомянутые способы тесно связаны с обычным симплексным методом. Некоторые опенки трудоемкости этих методов даны в работе Гоффмана, Манноса, Соколовского и Виг-мана [61а].

Для решения задач линейного программирования существуют алгоритмы, не основанные на идеях симплексного метода. К ним относятся метод двойного описания (Райффа, Томпсон и Тролл [86]), численные методы для решения игр двух лиц с нулевой суммой (Браун [8] и фон Нейман [79]), релаксационный метод (Эгмон [1] и Моцкин и Шейнберг [77]) и метод проекций (Томкинс [94]). Однако эти алгоритмы менее эффективны по сравнению с группой симплексных методов.

Применение Excel экселя для решения задач линейного программирования

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

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

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

I. Фирма «Берроуз Корпорейшн», Электродэйта Дивижн, Пассадена, штат Калифорния. Вычислительная машина ДАТАТРОН. Размер задачи

Способ — симплексный метод с искусственным базисом.

И. Фирма «Ферранти Лимитед», Англия. Вычислительная машина ПЕГАС. Размер задачи

Способ — симплексный метод с искусственным базисом.

III. Фирма «Интернейшнл Бизнес Мэшин», Нью-Йорк.

А. Вычислительная машина ИБМ-650.

• Размер задачи (включая искусственные векторы)

Способ — симплексный метод с искусственным базисом.

• Размер задачи

Способ — модифицированный симплексный метод.

• Размер задачи

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

• Размер задачи

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

B. Вычислительная машина ИБМ-701. Размер задачи

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

C. Вычислительная машина ИБМ-702. Размер задачи

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

D. Вычислительная машина ИБМ-704. Размер задачи

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

E. Вычислительная машина ИБМ-705. Размер задачи

Способ — модифицированный симплексный метод.

IV. Фирма «С перри Рэнд Корпорейшн», Нью-Йорк.

А. Вычислительная машина УНИВАК-1.

• Размер задачи

Способ — симплексный метод с искусственным базисом.

• Размер задачи

Способ — модифицированный метод.

B. Вычислительная машина 1103. Размер задачи

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

C. Вычислительная машина ПОЗА. Размер задачи

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

Вычислительные процессы для решения транспортной задачи*)

I. Фирма «Ферранти Лимитед», Англия. Вычислительная машина ПЕГАС. Размер задачи

II. Фирма «Интернейшнл Бизнес Мэшин», Нью-Йорк.

A. Вычислительная машина ИБМ-650. Размер задачи примерно

B. Вычислительная машина ИБМ-701. Размер задачи

C. Вычислительная машина ИБМ-702. Размер задачи

D. Вычислительная машина ИБМ-704. Размер задачи

E. Вычислительная машина ИБМ-705. Размер задачи

III. Фирма «Сперри Рэнд Корпорейшн», Нью-Йорк.

A. Вычислительная машина УНИВАК-1.

• Размер задачи

• Размер задачи

Способ — модифицированный симплексный метод, приспособленный для решения транспортной задачи (Сузуки [93]).

• Размер задачи

Способ — метод, описанный в работе Герстенхабера и Кел-ли [49].

B. Вычислительная машина 1103. Размер задачи

Способ основан на методе, приведенном Сузуки [93].

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

Одной из первых проблем, для исследования которых были с успехом применены методы линейного программирования, явилась транспортная задача. Поставленная первоначально Хичкоком [57], транспортная задача позднее была детально разобрана Купмансом [66]. Формулировка ее как задачи линейного программирования и методы решения впервые были даны Данцигом [18]*). Предложенный им вычислительный процесс является детализацией симплексного метода применительно к транспортной задаче. В дальнейшем мы коснемся метода Данцига, не вдаваясь, однако, в подробное его обсуждение. Отсылаем читателя, желающего познакомиться с этим методом в деталях, к работе Данцига [18]. Другой процесс для решения задачи транспортировки предложен Фордом и Фулкерсоном [43].

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

Общая транспортная задача

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

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

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

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

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

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

Дадим теперь математическую формулировку транспортной задачи:

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

при условиях

Уравнения (1.2) получаются из строк таблицы 12, уравнения (1.3) — из столбцов этой таблицы. Для совместности уравнений (1.2) и (1.3) необходимо, чтобы

Отметим здесь, что задача (1.1) — (1.4) является задачей линейного программирования с уравнениями и переменными.

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

Доказательство. Поскольку

величины

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

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

Выпишем для

уравнения, соответствующие (1.2) и (1.3). Мы получим тогда следующие восемь (т. е. ) уравнений с 15 (т. е. ) неизвестными:

Если мы сложим уравнения d) — h) и вычтем из результата уравнения Ь) и с), то получим уравнение а). Последнее, следовательно, является лишним и нет необходимости включать его в систему. Обобщая, можно заключить, что одно уравнение из системы (1.2) или (1.3) можно исключить, в результате чего транспортная задача сводится к —1 независимым уравнениям с переменными. Для выписанных уравнений получаем следующую укороченную матрицу (здесь из системы (1.2) исключено первое уравнение):

Вектор соответствует переменной . Обозначим через

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

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

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

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

Конструктивным доказательством теоремы может послужить процесс получения первого опорного плана, предложенный Данцигом [18] и названный Чарнесом и Купером [10] «правилом северо-западного угла». Применим это правило к следующей таблице:

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

если

то

и все

для

Если

то

и все

для

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

Шаг 1. Примем

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

Если допустить, что

Это показано в шаге 2. Количество продукта, которое осталось перевезти из пункта отправления 2, теперь равно ; потребность первого пункта назначения полностью удовлетворена. Шаг 2. Допустим, что

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

Шаг 3. Положим

Шаг 4. Допустим, что

Из шага 4 видно, что

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

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

Продемонстрируем теперь правило «северо-западного угла» на двух числовых примерах.

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

В примере 2 это имеет место для

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

Обозначим через базис, образованный этими векторами. Тогда решение системы должно совпадать с планом, получаемым по правилу «северо-западного угла». Здесь

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

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

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

Докажем теорему 3 с помощью следующего утверждения:

Лемма 1. Каждую систему из линейно независимых векторов транспортной задачи можно расположить в виде треугольной матрицы.

Для иллюстрации этого утверждения перестроим в треугольную матрицу базис примера 1. Исходная система имеет такой вид:

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

Из системы уравнений, соответствующей полученной треугольной матрице, немедленно следует, что и . Подставив эти значения в уравнение Ь), получаем . Решив подобным образом уравнения е), d), а) и с), получим

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

Теорема 4. Любая транспортная задача обладает оптимальным планом.

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

Систему уравнений с переменными можно, разумеется, решить с помощью обычного симплексного метода. Однако даже при малых значениях и получающаяся в результате система уравнений громоздка и неудобна для ручных вычислений. Может оказаться, что такие системы будут слишком велики даже для решения на вычислительных машинах. Эта трудность устраняется путем видоизменения симплексного алгоритма применительно к транспортной проблеме. Для начала соответствующего итеративного процесса необходимо иметь опорный план задачи. Мы знаем, что векторы, связанные с переменными опорного плана, линейно независимы. Если опорный план невырожден, то он удовлетворяет требованиям процесса. Это перестает быть верным для вырожденных планов таких, как в случае примера 2. Если вырожденный опорный план содержит положительных переменных, то необходимо дополнительно выбрать нулевых переменных. векторов, связанных с этими нулевыми переменными, и k векторов, связанных с положительными переменными, должны быть линейно независимы. Указанный выбор может быть произведен с помощью -приема для транспортной задачи (Данциг [18]).

Обратимся к таблице, использованной для получения первого плана по правилу «северо-западного угла». Если на шаге 1

то ни , ни не могут быть положительны. Аналогично, если на шаге 2

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

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

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

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

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

Метод решения транспортной задачи

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

Данциг показал также, что если

для переменных, не входящих в опорный план, и если все разности

то опорный план является оптимальным. Если же это условие оптимальности не выполняется, то легко может быть получен новый опорный план, связанный с меньшим, чем предыдущий, значением линейной формы (задача здесь предполагается невырожденной). Вычислительный процесс Данцига дает возможность получать опорный план без составления обычной симплексной таблицы и исследовать его на оптимальность, т. е. вычислять без предварительного разложения векторов, не входящих в базис, по векторам этого базиса. Теоретическое рассмотрение этого метода дано в работах Гендерсона и Шлейфера [55] и Чарнеса и Купера [10]. Здесь этот процесс будет проиллюстрирован на числовом примере.

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

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

единиц. Заметим, что

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

Например, стоимость перевозки одной единицы между пунктом отправления 3 и пунктом назначения 2 равна . В общем случае могут быть произвольными действительными числами. Применяя правило «северо-западного угла», получаем исходный план:

где

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

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

Определим для положительных переменных опорного плана чисел и чисел таких, что

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

Пусть в (2.1)

тогда систему легко решить для оставшихся и . Если

поскольку

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

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

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

Поскольку все уравнения системы (2.1) удовлетворяются, имеем

для всех , входящих в опорный план. Далее, для всех комбинаций подсчитываются величины

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

Например,

Как будет показано ниже, рассмотренные три элементарных этапа можно объединить в один. Подсчитаем разности . Если все

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

Для рассматриваемого плана имеем

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

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

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

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

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

где цифры, набранные жирным шрифтом, соответствуют отвечающим векторам базиса. Очевидно, что

Вводя в клетку (2,4), нужно следующим образом прибавить и вычесть из :

Получаем = 6; исключается из плана и вводится в него при значении, равном = 6. Новое значение линейной формы равно

Новый план имеет такой вид:

Соответствующая запись таблицы и матрицы имеет такой вид:

Здесь все

и этот последний вырожденный план

и все другие =0) является оптимальным. Значение линейной формы равно 28. Отметим, что

а в план не входит. Поэтому можно ввести в план и получить другое решение. Подставляя в клетку (1.3), получаем:

Имеем тогда при

новый вырожденный оптимальный план:

Разумеется, значение линейной формы осталось равным 28. Заметим, что в данном случае компоненты плана не изменились, поскольку = 0.

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

единиц однородного продукта. Стоимости перевозок между фиктивным, или -м, пунктом отправления и пунктами назначения принимаются равными нулю. Если первоначальная задача имела размеры 3 X 4 размеры новой задачи 4 X 4. Эта задача может быть решена подобно любой другой транспортной задаче:

Здесь все

Если имеет место противоположное неравенство

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

Стоимости перевозок в этот фиктивный пункт опять берутся равными нулю.

Задача 3X4 сводится в этом случае к обычной транспортной задаче размера 3 X 5:

При решении любой задачи линейного программирования можно, вообще говоря, ожидать, что общее число необходимых итераций зависит от того, насколько первый план близок к оптимальному. Поскольку в правиле «северо-западного угла» значение не учитывается, нельзя ожидать, что при вычислении исходного плана по этому правилу соответствующее значение линейной формы будет близким к минимальному. Было предложено несколько других методов, которые можно применить для машинных вычислений. Продемонстрируем три из них на примере, заимствованном из работы Данцига [18]:

В этом примере правило «северо-западного угла» приводит к плану, связанному с значением линейной формы, равным 52.

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

Этот план является оптимальным; соответствующее значение линейной формы равно 13.

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

при значении линейной формы, равном 17.

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

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

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

Видоизменения транспортной задачи

А*). Задача о назначении персонала **). Концерну необходимо заполнить три вакансии, связанные с различными квалификациями. На эти вакансии имеются три претендента, каждый из которых может занять любое вакантное место с одной и той же оплатой труда. Однако вследствие различия в способностях, образовании и опыте полезность каждого кандидата для компании зависит от должности, на которую он назначается. Годовые доходы компании от каждого кандидата, принятого на одну из трех вакантных должностей, записаны ниже:

Желательно таким путем назначить кандидатов на должности, чтобы общий доход компании был максимальным. В данной задаче имеются возможных вариантов назначений. Нам необходимо определить характеристики назначений -го кандидата на -ю должность, . Полагаем при этом, что может принимать значения либо 0, либо 1. Равенство характеристики назначения нулю означает, что -й кандидат не назначен на -ю должность. Характеристика назначения, равная 1, указывает на принятие -го кандидата на -ю должность. Поскольку каждого претендента можно назначить только на одну должность и, обратно, каждая должность может быть занята только одним работником,

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

при условиях

Эта задача сводится к обычной транспортной задаче, состоящей в минимизации

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

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

при условиях

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

Если

в задачу вводится фиктивная категория личного состава, содержащая

лиц. Когда

используется фиктивная должностная категория, состоящая из

должностей.

Двайер [41] и Вото совместно с Орденом [97а] предложили приближенные методы решения задачи о назначении персонала, а следовательно, и задачи транспортировки. С другими способами решения рассмотренных задач читатель может ознакомиться по работам фон Неймана [78] и Эгер-вари [42].

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

1) цену единицы товара или товаров;

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

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

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

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

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

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

-му складу требуется единиц указанного продукта,

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

и при этом функция

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

В общем случае можно ожидать, что предложение превышает спрос, т. е.

Если ввести в рассмотрение фиктивный -й склад с потребностью

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

Эти и другие подобные условия можно учесть, используя различные вычислительные способы, близкие к методам решения транспортной задачи. Некоторые из этих схем рассмотрены Стэнли, Хонигом и Гейненом [91]. Типичная задача о заключении контрактов и ее решение рассматривались Директоратом управления исследованиями [36].