Задачи математического программирования и их виды. Постановка задачи линейного программирования

Общая постановка задачи математического программирования.

              Z=å C _J X_J ®min (max) целевая функция (1)

 {spoiler=Подробнее}

a₁₁x₁+a₁₂x₂+a_1nx_n £b₁

              a₂₁x₁+a₂₂x₂…a_2nx_n £b₂         (2)

……………………..

a_n1x₁+a_n2x₂…a_nnx_n £b_n

              x₁ ³0,   x₂³0,…,x_n ³0       (3)

Системы неравенств (2) и (3) называются ограничениями, а х_1, х₂ ,…,х_т – искомые переменные.

Цель является найти такие значения х, при выполнении систем ограничений (2),(3) линейная форма (1) принимает желаемый min (max).

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

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

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

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

5.В задачах математического программирования неизвестные х₁,х₂,...,х_n является функциями времени, т.е. х₁=х₁(t),х₂=х₂(t),...,х_n=х_n(t) в таком случае задача называется задачами динамического программирования.

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

Действительно, путь необходимо исследовать на экстремум линейную функцию

Z=å C_jx_j

 при линейных     ограничениях

а₁₁х₁+а₁₂х₂+...+а₁₂х_n=b₁,

а₂₁х₁+а₂₂х₂+...а_2nx_n=b₂,

.....................................

a_m1x₁+a_m2x₂+...+a_mnx_n=b_m.

         Так как, Z - линейная функция,  то dz/dx_j=C_j (j=1,2,…,n),                  но все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку  частные производные являются константами.

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

Z=C₁x₁+C₂x₂+....+C_nx_n                                       (1)

и система линейных ограничений

           (2)

x_j³0 (j=1,2......,n),                                                        (3)

где а_ij  ,в_i  и  С_j -заданные постоянные величины.

Найти такие неотрицательные значения х₁ ,х₂ ,. . . х₃ ,которые удовлетворяют системе ограничений (2) и доставляют линейной функции (1) минимальное значение.

Как отмечалось ранее ,в системе ограничений (2) все b_i  (i= 1,2,...,m) можно  считать неотрицательными. Общая  задача имеет несколько форм записи.

Векторная форма записи. Минимизировать линейную функцию Z=Cх при ограничениях     A₁x₁+A₂x₂+...............A_nx_n=A₀, x³0.  (4)

где  С=(c₁, c₂,.......,c_n);  X=(x₁,x_2,.....,x_n);  Cx-скалярное произведение; векторы

состоят  соответственно из коэффициентов при неизвестных и свободных членов.      

Матричная  форма записи. Минимизировать линейную функцию Z=Cх при ограничениях Ах=А₀ , х³ 0 ,где С=c₁, c₂,....c_nматрица  строка :

А =(a_ij ) - матрица системы:  - матрица столбец ,  -матрица столбец.

Запись с помощью знаков суммирования. Минимизировать линейную функцию  при ограничениях., i=1,2,...,m; x_j³0, j=1,2,...,n.

Определение 1. Планом или допустимым решением задачи линейного программирования называется вектор Х=(x₁, x₂, ..., x_n), удовлетворяющий условиям  (2) и (3).

Определение 2. План Х= (x₁,x_2,  ....,x_n) называется опорным, если  векторы  А_i= (i=1, 2, ..., m) входящие в разложение (4) с положительными коэффициентами х  , являются линейно независимыми.

Так как векторы  А  являются  m-мерными, то   из определения опорного плана следует, что число его положительных компонент не может превышать m.

Определение 3. Опорный план называется невырожденным, если он содержит m положительных компонент, в противном  случае опорный план называется вырожденным.

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

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

Выпуклые множества

Пусть на плоскости    х₁Ох₂   заданы две точки: А₁ (x₁⁽¹⁾; x₂⁽²⁾ ) и

А₂ (x₁⁽¹⁾; x₂⁽²⁾ ), определяющие прямолинейный  направленный отрезок  А₁  А₂ . Найдем координаты произвольной внутренней точки  

А (x₁ ;x₂ ) данного отрезка через  координаты его начала и конца.

Векторы А _­1А(x₁-x₁⁽¹⁾) ; x₂ -x₂ ⁽¹⁾ ) и  А₁ А₂=(x₁⁽²⁾-x₁⁽¹⁾ ),  параллельны и одинаково направлены, поэтому A₁A= t(A₁A₂),где 0 £ t £ 1, или x₁ - x₁⁽¹⁾=t (x₁⁽²⁾- x₁⁽¹⁾), x₂-x₂⁽¹⁾=t(x₂⁽²⁾-x₂⁽¹⁾). Отсюда x₁=(1-t)x₁⁽¹⁾+tx₁⁽²⁾, x₂=(1-t)x₂⁽¹⁾+tx₂⁽²⁾. Полагая 1-t = l₁, t = l₂, получаем

x₁=l₁x₁⁽¹⁾+l₂x₁⁽²⁾,

x₂=l₁x₂⁽¹⁾+l₂x₂⁽²⁾,                                      (5)

l₁³ 0, l₂³ 0, l₁+l₂ =1.

Учитывая, что в (5) координаты точки А являются суммами одноименных координат точек А₁ и А₂, умноженными соответственно на числа l₁ и l₂, окончательно имеем:

А=l₁А₁+l₂А₂,                                                    (6)

l₁³ 0, l₂³ 0, l₁+l₂=1                               (7)

Точка А, для которой выполняются условия (6 ) и (7 ), называется выпуклой линейной комбинацией точек А₁ и А₂. При l₁=1 и l₂= 0 точка А совпадает с концом отрезка А₁, при l₁=0 и l₂=1 - с концом отрезка А₂, Таким образом, если t пробегает все значения от 0 до 1 , то точка А описывает отрезок А₁А₂. Точки А₁ и А₂ называются угловыми или крайними точками отрезка А₁А₂.

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

Пусть  имеется   n  точек  А_{2 ,}  А_{2 ,   ... ,}  А_n.  Точка А-  выпуклая  линейная  комбинация,  если  выполняются   условия

А=l₁А₁+l₂А₂,+......+l_n A_n,

l₁³ 0(j=1, 2,.....,n),

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

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

{/spoilers}