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

Оглавление:

Введение:

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

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

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

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

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

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

где Методы решения задач линейного программирования обозначает Методы решения задач линейного программирования-й известный коэффициент, 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

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

К оглавлению…

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

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