Решение ЗЛП симплекс-методом

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

Для решения ЗЛП симплекс-методом ее приводят к каноническому виду, т.е. из ограничений – неравенств надо сделать ограничения – равенства. Для этого в каждое ограничение вводится дополнительная неотрицательная балансовая переменная со знаком «+», если знак неравенства «£», и со знаком «–», ели знак неравенства «³».

В целевой функции эти дополнительные переменные входят с нулевыми коэффициентами, т.е. запись целевой функции не изменится. Каждую переменную, на которую не наложено условие неотрицательности, можно представить в виде разности двух неотрицательных переменных: .

Если ограничения задачи отображают наличие и расход ресурсов, то числовое значение дополнительной переменной в плане задачи, записанной в канонической форме, равно объему неиспользованного ресурса.

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

1. Составляем первый опорный план

Задача остается прежней. Приведем стандартную форму системы неравенств (1) в каноническую форму системы уравнений путем введения дополнительных балансовых переменных x ₃, x ₄, x ₅, x ₆.

или

.

В экономическом смысле значения дополнительных переменных x ₃, x ₄, x ₅ определяют остатки сырья после реализации продукции.

Матрица полученной системы уравнений имеет вид:

Видно, что в матрице A базисным минором 4-го порядка является определитель, составленный из единичных коэффициентов при дополнительных переменных x ₃, x ₄, x ₅, x ₆, так как он отличен от нуля и равен 1. Это означает, что векторы-столбцы при этих переменных является линейно независимыми, т.е. образуют базис, а соответствующие им переменные x ₃, x ₄, x ₅, x ₆ являются базисными (основными). Переменные x ₁, x ₂ будут называться свободными (неосновными).

Если свободным переменным x ₁ и x ₂ задавать различные значения, то, решая систему относительно базисных переменных, получим бесконечное множество частных решений. Если свободным переменным задавать только нулевые значения, то из бесконечного множества частных решений выделяют базисные решения – опорные планы.

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

Количество базисных решений и соответствующее ему число групп базисных переменных может быть не более, чем , где n –общее число переменных, r – число базисных переменных, r ≤ m ≤ n.

Для нашей задачи r = 4; n = 6. Тогда , т.е. возможны 15 групп из 4-х базисных переменных (или 15 базисных решений).

Разрешим систему уравнений относительно базисных переменных x ₃, x ₄, x ₅, x ₆:

Полагая, что свободные переменные x ₁ = 0, x ₂ = 0, получим значения базисных переменных: x ₃ = 312; x ₄ = 15; x ₅ = 24; x ₆ = –10, т.е. базисное решение будет = (0; 0; 312; 15; 24; –10).

Данное базисное решение является недопустимым, т.к. x ₆ = –10 ≤ 0, а по условию ограничений x ₆ ≥ 0. Поэтому вместо переменной x ₆ в качестве базисной надо взять другую переменную из числа свободных x ₁ или x ₂.

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

Таблица 1

F –строка называется индексной. Она заполняется коэффициентами целевой функции, взятыми с противоположными знаками, так как уравнение функции можно представить в виде F = 0 – (– 4 x ₁ – 3 x ₂).

В столбце свободных членов b_i есть отрицательный элемент b ₄ = –10, т.е. решение системы является недопустимым. Чтобы получить допустимое решение (опорный план), элемент b ₄ надо сделать неотрицательным.

Выбираем x ₆-строку с отрицательным свободным членом. В этой строке есть отрицательные элементы. Выбираем любой из них, например, «–1» в x ₁-столбце, и x ₁-столбец принимаем в качестве разрешающего столбца (он определит, что переменная x ₁ перейдет из свободных в базисные).

Делим свободные члены b_i на соответствующие элементы a_is разрешающего столбца, получаем оценочные отношения Θ _i = = {24, 15, 12, 10}. Из них выбираем наименьшее положительное (minΘ _i =10), которое будет соответствовать разрешающей строке. Разрешающая строка определяет переменную x_j, которая на следующем шаге выступает из базиса и станет свободной. Поэтому x ₆-строка является разрешающей строкой, а элемент «–1» – разрешающим элементом. Обводим его кружком. Переменные x ₁ и x ₆ меняются местами.

Оценочные отношения Θ _i в каждой строке определяются по правилам:

1) Θ _i = , если b_i и a_is имеют разные знаки;

2) Θ _i = ∞, если b_i = 0 и a_is < 0;

3) Θ _i = ∞, если a_is = 0;

4) Θ _i = 0, если b_i = 0 и a_is > 0;

5) Θ _i = , если b_i и a_is имеют одинаковые знаки.

Совершаем шаг модифицированного жорданова исключения (ШМЖИ) с разрешающим элементом и составляем новую таблицу (табл. 2) по следующему правилу:

1) на месте разрешающего элемента (РЭ) устанавливается величина, ему обратная, т.е. ;

2) элементы разрешающей строки делятся на РЭ;

3) элементы разрешающего столбца делятся на РЭ и знак меняется;

4) остальные элементы находятся по правилу прямоугольника:

.

Из табл. 2 видно, что свободные члены в b_i -столбце являются неотрицательными, следовательно, получено первоначальное допустимое решение – первый опорный план = (10; 0; 182; 5; 4; 0). При этом значение функции F () = 40. Геометрически это соответствует вершине F (10; 0) многоугольника решений (рис. 1).

Таблица 2

2. Проверяем план на оптимальность. Опорный план не оптимальный, так как в F -строке имеется отрицательный коэффициент «–4». Улучшаем план.

3. Нахождение нового опорного плана

Выбираем разрешающий элемент по правилу:

- выбираем наименьший отрицательный коэффициент в F -строке «–4», который и определяет разрешающий столбец – x ₆; переменную x ₆ переводим в базисные;

- находим отношения Θ _i, среди них выбираем наименьшее положительное, которое соответствует разрешающей строке:

min Θ _i = min {14, 5, 2, ∞} = 2, следовательно, x ₅-строка – разрешающая, переменную x ₅ переводим в свободные (переменные x ₅ и x ₆ меняются местами).

- на пересечении разрешающих строки и столбца стоит разрешающий элемент «2»;

- выполняем шаг ШМЖИ, строим табл. 3 по вышеприведенному правилу и получаем новый опорный план = (12; 0; 156; 3; 0; 2).

Таблица 3

4. Проверка нового опорного плана на оптимальность

Опорный план также не является оптимальным, так как в F -строке имеется отрицательный коэффициент «–1». Значение функции F () = 48, что геометрически соответствует вершине E (12; 0) многоугольника решений (рис. 1). Улучшаем план.

5. Нахождение нового опорного плана

x ₂-столбец – разрешающий, так как в F -строке наименьший отрицательный коэффициент «–1» находится в x ₂-столбце (Δ₂ = –1). Находим наименьшее Θ _i: min Θ _i = min {≈ 9, 6, ∞, 24} = 6, следовательно, x ₄-строка – разрешающая. Разрешающий элемент «1/2». Меняем местами переменные x ₂ и x ₄. Выполняем шаг ШМЖИ, строим табл. 4, получаем новый опорный план = (9; 6; 51; 0; 0; 5).

6. Проверка опорного плана на оптимальность

В F -строке все коэффициенты неотрицательны, следовательно, опорный план является оптимальным. Геометрически соответствует точке D (9;6) (см. рис. 1). Оптимальный план дает максимальное значение целевой функции у.е.

Таблица 4

Таким образом, необходимо производить 9 единиц продукции I вида (x ^*₁ = 9) и 6 единиц продукции II вида (x ^*₂ = 6). Значения коэффициентов F -строки – ненулевые, поэтому полученный оптимальный план является единственным. F -строка позволяет представить целевую функцию через свободные переменные x ₄ и x ₅: .

В оптимальном плане фигурируют значения дополнительных переменных x ₃ = 31; x ₆ = 5. Это означает, что сырье вида С недоиспользовано на 51 кг, а сырье видов А и В (x ₄ = 0; x ₅ = 0) израсходовано полностью и является дефицитным. Значение дополнительной переменной x ₆ = 5 означает превышение общего количества произведенной продукции над ограничением: x ₁ + x ₂ ≥ 10.

Замечания:

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

2) Если на каком-либо шаге в разрешающем столбце все коэффициенты будут a_is ≤ 0 (т.е. во всех уравнениях будут бесконечные оценочные отношения Θ _i = ∞ той переменной x_i, которая переводится в основные), то задача не имеет конечного оптимума, целевая функция не ограничена на ОДР (F_max = ∞, F_min = –∞) и задачу решить нельзя.

3) Если в столбце Θ _i содержатся два или несколько одинаковых наименьших значений отношения, то новый план будет вырожденным (одна или несколько базисных переменных станут равными нулю). В этом случае следующий шаг не вызовет изменения функции F (Δ F = 0), хотя приведет к новому опорному плану. Наличие «пустых» шагов может привести к зацикливанию, т.е. многократному повторению процесса вычислений, не позволяя завершить задачу. Избежать зацикливания можно с помощью определенных мер, например, способом Креко. Задачи с зацикливанием встречаются редко.