Модели линейного программирования.

В общем случае задача линейного программирования(ЛП):

Найти переменные (х₁, х₂….х_n), которые доставляют максимум или минимум целевой функции f (х₁, х₂….х_n) = c₁х₁ + с₂х₂+…+с_nx_n = сумма ∑с_jx_jmax(min).

c₁х_1, с₂х_2,…с_nx_{n ,} а_jx_j– постоянные переменные.

Задача линейного программирования(ЛП) – записанная в симметричной форме, если l = 0.

Задача ЛП записанная в экономической форме, если m = 0.

Любое решение удовлетворяющее системе ограничения задачи – допустимым планом задачи.

План Х^* - оптимальный план задачи, если:

• f(x^*)=>f(x) – для максимума,

• f(x^*) =<f(x) – для минимума.

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

Пример задачи оперативного планирования приводящей к задачи ЛП:

В некотором плановом периоде предприятие предполагает изготовление n видов продукции. В этом случае под (х₁, х₂….х_n) – количество продукции 1, 2,…, n-го вида, которое предприятие будет выпускать в планируемом периоде. Для производства этой продукции предприятие имеет m видов ресурсов. Каждый из ресурсов ограничен велиxbной b_i (j=1,…,m)/ для производства единицы продукции j-того вида необходимо использовать а_ijединиц i-го ресурса. Необходимо определить количество выпускаемой продукции каждого вида при котором суммарная выручка является максимальной. При этом известно, что что в планов в периоде цена реализации единицы продукции является известной и постоянной величиной c_j.

f(x) = ∑c_jх_jmax (планирование в планируемом периоде).

A _n1X1 +A_n2X₂+…._A1nXn=<b₁

……

A_m1X₁ +A_m2X₂+….A_mnX_n=<b_m

X_i => 0

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

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

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

F(x) = c₁x₁+c₂x₂max(min)

Введем декартовую систему координат с осями х₁, х₂.

a₁₁x₁+a₁₂x₂ = b₂

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

Данную область принято называть областью допустимых решении задач ЛП (многоугольником плана).

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

Теорема: множество ограничении задачи ЛП формирует выпуклое множество допустимых планов задачи, если оно не пусто.

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

Теорема: оптимальное решение задачи ЛП, если оно существует совпадает с одним из опорных решений.

Ц елевая функция f(x) = 6х1 +3х2 max

3х₁+4х₂=<24 х₁/8+х₂/6 =<1

2x₁+2.5x₂=>5 x₁/2.5+x₂/2=>1

-6x₁+6x₂=<18 -x₁/3 + x₂/3 =<1

5x₁-2x₂=<10x₁/2- x₂/5 =<1

_j =>0 _j =>0

Общие случаи решения задач лп. Симплекс-метод.

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

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