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

Далее вверх Предыдущая страница
Далее: Графическое решение 2-var Up: Формулировка LP и Предыдущее: Прототип задачи LP:

Общая формулировка ЛП

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

Целевая функция:

  уравнение 95

s.t.
Технологические ограничения:

  уравнение 99

Подписать Ограничения:

  уравнение 109

где `урснеограниченность в знаке.

Формулировка уравнений 6-8 имеет общую структуру задачи математического программирования. Представленную во введении этого раздела. Но она далее характеризуется тем. Что функции. Участвующие в задаче объективной и левой части технологических ограничений, являются

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

Чтобы лучше понять концепцию линейности. Предположим. Что различные переменные решения tex2html_wrap_inline1519соответствуют различным видам деятельности. Из которых в конечном итоге будет синтезировано любое решение. А значения. Присвоенные переменным любым данным решением. Указывают на уровень активности в рассматриваемом плане(планах). Например, в приведенном выше примере двумя видами деятельности являются производство предметов tex2html_wrap_inline1429иtex2html_wrap_inline1431, в то время как уровни активности соответствуют ежедневному объему производства.

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

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

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

Интересно отметить. Как вышеприведенное утверждение отражает логику. Которая была применена. Когда мы вывели технологические ограничения примера прототипа: (i) Наше предположение о том. Что обработка каждой единицы продукта на каждой станции требует постоянного количества времени. Устанавливает пропорциональность свойство для нашей модели. (ii) Предположение о том. Что общее время обработки. Необходимое на каждой станции для достижения уровня производства обоих продуктов. Является совокупностью времени обработки. Необходимого для каждого продукта. Если соответствующая деятельность происходила независимо. Подразумевает. Что наша система имеет

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

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

Другой аппроксимирующий элемент во многих реальных LP-приложениях является результатом так называемого предположения делимости. Это предположение относится к тому. Что для того. Чтобы теория LP и алгоритмы работали. Переменные задачи должны быть реальными. Однако во многих формулировках ЛП значимые значения для уровней вовлеченных действий могут быть только

целыми. Так обстоит дело, например. С производством изделий tex2html_wrap_inline1429и tex2html_wrap_inline1431в нашем прототипном примере. Введение требований интегральности для некоторых переменных в формулировке LP превращает задачу в одну. Принадлежащую к классу (Смешанное) Целочисленное программирование (MIP). Сложность задачи MIP намного выше, чем у LP. На самом деле общая формулировка ИС. Как было показано. Относится к пресловутому классу NP-полных задач. (Это класс проблем. Которые были `формальноУчитывая возросшую трудность решения задач ИС. Иногда на практике близкие к оптимальным решения получаются путем решения формулировки ЛП. Возникающей в результате ослабления требований интегральности — известного как

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

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

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


Далее вверх Предыдущая страница
Далее: Графическое решение 2-var Up: Формулировка LP и Предыдущее: Прототип задачи LP:

UAL Data
Fri Jun 20 15:03:05 CDT 1997