Алгоритм поиска допустимого решения состоит в следующем.

1. Среди элементов первого столбца выбираем любой отрицательный элемент. Пусть этим элементом является b _{k +2}.

2. В строке с выбранным отрицательным элементом находим элементы, одинаковые с ним по знаку. Пусть это будут элементы ν _{k +2,1} и ν _{k +2, m} .

3. Определяем отношение отрицательного свободного члена к каждому отрицательному элементу строки и находим наименьшее из этих отношений. Пусть

< .

Тогда столбец, в котором располагается элемент ν _{k +2,1} выбираем в качестве разрешающего столбца.

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

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

6. Используя правила симплекс-преобразования, переходим к новой симплекс таблице, в которой анализируем элементы первого столбца. При наличии среди них одного или нескольких отрицательных элементов, повторяем операции по п.п.1-5. Процедура продолжается до тех пор, пока не будет найдено допустимое решение. Как только допустимое решение найдено, переходим к поиску оптимального решения, используя известный табличный алгоритм симплекс-метода.

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

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

Задача. Найти неотрицательные значения переменных х ₁, х ₂,..., х ₆ удовлетворяющие системе ограничений:

- 5х₁ + 2х₂ - х₃ = 10

2х₁ + х₂ - х₄ = 8

х₁ - х₂ - х₅ = 2

х₁ + х₂ + х₆ = 10

и обращающие в минимум целевую функцию

L (x) = - 4 х ₁ - 2 х ₂

В качестве свободных переменных выберем переменные х ₁, х ₂. Тогда базисными переменными будут х ₃, х ₄, х ₅, х ₆. На рисунке показаны графики, соответствующие ограничениям задачи и целевой функции, построенные в координатах х ₁О х ₂.

Рис. 3.6

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

Приведем систему ограничений и целевую функцию к виду, удобному для заполнения симплекс-таблицы:

х ₃ = -10 - (5 х ₁ - 2 х ₂)

х ₄ = - 8 - (-2 х ₁ - х ₂)

х ₅ = - 2 - (- х ₁ + х ₂)

х ₆ = 10 - (х ₁ + х ₂)

 

L (x) = 0 - 4(x ₁ + 2 x ₂)

Поиск допустимого решения в соответствии с алгоритмом приводит к следующей последовательности симплекс-таблиц:

Таблица 3.5 Таблица 3.6 Таблица 3.7

СЧ

x 1

x 2

СЧ

x 5

x 2

СЧ

x 5

x 4

L (x)

L (x)

-8

L (x)

-16

x 3

-10

-2

x 3

-20

x 3

-24

x 4

-8

-2

-1

x 4

-4

-2

-3

x 2

4/3

2/3

-1/3

x 5

-2

-1

x 5

-1

-1

x 1

10/3

-1/2

-1/3

x 6

x 6

x 6

16/3

-1/3

-2/3

В строке при переменной х ₃ в таблице 3.7 свободный член отрицателен. В соответствии с п.2 алгоритма поиска допустимого решения в этой строке необходимо найти элементы, одинаковые по знаку со свободным членом. Но такие элементы в строке отсутствуют. Запишем аналитическое выражение базисной переменной:

х 3 = - 24 - х 4 - 3 х 5

(3.27)

Очевидно, что не найдется таких неотрицательных значений переменных х ₃, х ₄, х ₅, при которых уравнение (3.27) было бы справедливым. А это означает, что задача линейного программирования не имеет допустимых решений.

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

 

Транспортная задача

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