Линейное программирование

Линейное программирование

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

Найти   f₀(x)=c₁x₁+c₂x₂+...+c_nx_n                       (1)

где  x=(x₁,x₂,...,x_n)-вектор переменной

        c_j, j=1,2,...,n- коэффициенты целевой функции

Рекомендуемые материалы

        a_ij, i=1,2,...,n; j=1,2,...,n- коэффициент ограничений

        b=(b_1,b₂,...,b_n)-вектор свободных членов

        A=[a_ij]_m´n      

ЗЛП в стандартной форме записи:

[f₀(x)=]                          [g₀(y)=]

R=                             Q=

Где: А^Т-транспонированная матрица A^Т=[a_ij]_m´n      

ЗЛП в канонической форме записи:

[f₀(x)=]                          [g₀(y)=]

R=                             Q=

Эквивалентные преобразования ЗЛП.

  Эквивалентные преобразования не изменяют решения ЗЛП , то есть эквивалентность относительно решения.

1. Переход от задачи  max к задаче min:

[f₀(x)=]-от этой задачи перейти к задаче на min

f₀(x)= -[f₀(x)]

f₀(x)==[-]

g₀(y)== -g₀(y)=[]

2.Переход от ограничения равенства к ограничению неравенства (заключается в переходе к двум противоположным неравенствам).

³b_i

£b_i

При решении задачи  на  f₀(x) имеем следующие ограничения:

-£b_i

£b_i

При решении задачи на f₀(x) ограничения следующие:

³b_i

-³b_i

3. Переход от ограничений неравенств к ограничениям равенства:

£b_i  добавляется неотрицателбная часть: +x_n+i=bi, где x_n+i³0 (дополнительная переменная)

³c_j        вычтем константу :  -x_m+j=c_j ,где x_м+j³0

4. Переход от переменной неопределённого знака к неотрицательной переменной.

      x   ³£ 0   

Введём две новые переменные:U_j³ 0;

                                                      V_j³0.

Получим: x_j=  U_j -V_j

5. Переход от переменной, ограниченной сверху к неотрицательной переменной:

x_k³d_k, d_k=const,d_k>0

Введём новые переменные: W_k=x_k-d_k , W_k>0

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

Симплекс – метод решения задачи линейного программирования на максимум в стандартной форме записи при .

         Симплекс – метод для решения задачи линейного программирования на максимум основан на методе Жордана (1838-1922) решения систем линейных алгебраических уравнений.

         Американский математик Дж. Данциг в 1949 году введением строки для целевой функции применил этот метод для решения задачи линейного программирования.

         Основоположником же рассматриваемого метода считается Канторович, представивший в 1938 году “метод допустимого улучшения плана”, предполагая, что начальное решение уже имеется, в отличие от Данцига, у которого начальное решение находится с помощью симплекс – преобразований. Однако Нобелевская премия была получена им лишь в 1975 году.

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

         Рассмотрим симплекс – метод решения задачи линейного программирования на максимум в стандартной форме записи на следующем примере:

.

От задачи (1) – (3) перейдем к задаче в канонической форме записи. Для этого введем дополнительные переменные  и разрешим относительно них систему ограничений – равенств, при этом :

.

        

Введем вектор , т. е.

Тогда

     Заметим, что симплекс – метод применяется только при выполнении ограничения (3).

         Введем множество базисных переменных  и множество небазисных переменных  и применим приведенный ниже алгоритм решения задачи линейного программирования на максимум к рассматриваемой задаче:

1.

2. - начало итерационного процесса

3.

4.  иначе см. пункт 12 (столбец  будет разрешающим)

5.  иначе см. пункт 14

6.

7.

8.

9.

10. - переход к следующей итерации.

11. - новый базис. Далее переходим на пункт 3.

Особенности алгоритма.

12. Если , то существует альтернативный оптимум, и см. пункт 5

13. , то найдено оптимальное решение, иначе см. пункт 14.

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

15. Конец