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

Линейное программирование — это частный раздел оптимального программирования. В свою очередь оптимальное (математическое) программирование — раздел прикладной математики, изучающий задачи условной оптимизации. В экономике такие задачи возника­ют при практической реализации принципа оптимальности в пла­нировании и управлении.

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

Суть принципа оптимальности состоит в стремлении выбрать такое планово-управленческое решение = (х₁,х₂,...,х_п), где x_j (j= ) — его компоненты, которое наилучшим образом учиты­вало бы внутренние возможности и внешние условия производст­венной деятельности хозяйствующего субъекта.

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

Слова «учитывало бы внутренние возможности и внешние усло­вия производственной деятельности» означают, что на выбор пла­ново-управленческого решения (поведения) накладывается ряд ус­ловий, т.е. выбор осуществляется из некоторой области возмож­ных (допустимых) решений D эту область называют также обла­стью определения задачи.

(1.1)

Таким образом, реализовать на практике принцип оптимальности в планировании и управлении — это значит решить экс­тремальную задачу вида:

(1.2)

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

(1.3)

Задачу условной оптимизации (1.1) и (1.2) записывают также в развернутом виде:

(1.5)

(1.4)

Задача (1.3)-(1.5) - общая задача оптимального (математического) программирования.

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

В задаче линейного программирования (ЗЛП) требуется найти экстремум (максимум или минимум) линейной целевой функции :

(1.8)

(1.7)

(1.6)

где a_ij, b_i, c_j - заданные постоянные величины.

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

Знак означает, что в конкретной ЗЛП возможно любое из перечисленных ограничений.

Вектор , удовлетворяющий системе ограничений (1.7) и (1.8) называют допустимым решением или планом задачи линейного программирования.

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

Канонической формой записи ЗЛП называют задачу вида (1.9) - (1.11):

Найти

(1.9)

при ограничениях

(1.10)

(1.11)

Дата добавления: 2014-12-26