6.3.Симплекс метод. Общий случай.

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

Найдем наибольшее значение функции

=c₁x₁+c₂x₂+ ... +c_nx_n (1)

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

а₁₁x₁+а₁₂x₂+ ... +а_1nx_{n =} b₁

а₂₁x₁+а₂₂x₂+ ... +а_2nx_{n =} b₂ (2)

... ... ... ... ... ... ... ...

а_m1x₁+а_m2x₂+ ... +а_mnx_{n =} b_m

х₁  0, х₂  0 ... х_n  0 (3)

Если система (2) не имеет решения, то и вся задача линейного программирования не имеет решения. Если система (2) имеет единственное решение, то оно и будет решением задачи линейного программирования (других просто не может быть). Поэтому для нас представляет интерес случай, когда система (2) имеет не единственное решение ( в алгебре показывается, что в этом случае решений будет бесчисленное множество). В этом случае часть переменных будет свободными переменными, а остальные – базисными. Базисные переменные выражаем через свободные. Пусть х₁ , х₂ ,... х_s – базисные переменные, а – свободными переменными.

Представим (2) в виде

причем будем считать, что ( в противном случае изменим свободные переменные как это делали в предыдущем примере).

Подставляя в(1) вместо базисных переменных их выражения из (4) запишем целевую функцию через свободные переменные

f( )= (5)

Возможны три случая.

А. Все числа , , …, неположительны. Тогда ( решение задачи линейного программирования. Действительно, в этом случае max f=f(0,…,0)= , так как при увеличении значение функции f может только уменьшиться.

Б. Среди чисел есть положительные (пусть, например числа (коэффициенты при в (4) )неотрицательны. Тогда задача линейного программирования не имеет решения.

Действительно, положим в этом случае

.

Тогда (4) примет вид

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

В. Среди чисел есть положительные (пусть, например, ), но среди чисел имеются отрицательные.

В этом случае мы поступаем следующим образом (в дальнейшем будем говорить делаем шаг).

Находим такое отрицательное число для которого величина наименьшая. Далее переводим в свободную переменную, а в базисную переменную, для чего в (4) выражаем переменные через переменные и через эти переменные выражаем функцию f.

Отсюда следует алгоритм решения задачи линейного программирования симплекс-методом.

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

2. Если среди чисел нет положительных, то задача решена (случай А).

3. Если среди чисел есть положительные (пусть, например числа (коэффициенты при в (4) )неотрицательны. Тогда задача линейного программирования не имеет решения. (случай Б)

4. Если среди чисел есть положительные (пусть, например, ), но среди чисел имеются отрицательные, то мы делаем шаг.

5. Для этого находим такое отрицательное число для которого величина наименьшая. Далее переводим в свободную переменную, а в базисную переменную. После этого переходим к пункту 2.

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

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

2. Если среди чисел нет отрицательных, то задача решена

3. Если среди чисел есть отрицательные (пусть, например числа (коэффициенты при в (4) )неотрицательны. Тогда задача линейного программирования не имеет решения.

4. Если среди чисел есть отрицательные (пусть, например, ), но среди чисел имеются отрицательные, то мы делаем шаг.

5. Для этого находим такое отрицательное число для которого величина наименьшая. Далее переводим в свободную переменную, а в базисную переменную. После этого переходим к пункту 2.