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

Случай 1. Допустимое базисное решение.

Нулевые (небазисные) переменные: x₂, x₄, x₅.

Уравнения: х₁ + 4х₃ = 8,

4х₁ + 2х₂ = 4.

Решение: единственное решение: х₁=0,

х₃=2.

Заключение: базисное решение допустимо, так как х₁,х₃ ≥ 0.

Случай 2. Недопустимое базисное решение.

Нулевые (небазисные) переменные: x₃, x₄, x₅.

Уравнения: х₁ + х₂ = 8,

4х₁ + 2х₂ = 4.

Решение: единственное решение: х₁= -6,

х₃=14.

Заключение: базисное решение недопустимо, так как х₁ ≤ 0.

Случай 3. Решение не единственное.

Нулевые (небазисные) переменные: x₁, x₂, x₅.

Уравнения: 4х₃ + х₄ = 8,

2х₃ + х₄ = 4.

Решение: единственное решение не существует, так как уравнения зависимы (если первое уравнение разделить на 2, то получим второе уравнение).

Заключение: бесконечное количество решений.

Случай 4. Решение не существует.

Нулевые (небазисные) переменные: x₁, x₃, x₄.

Уравнения: х₂ + 3х₅ = 8,

2х₂ + 6х₅ = 4.

Решение: решения не существует, так как уравнения несовместимы.

Заключение: решения не существует.

Свободные переменные и базисные решения.

Свободная переменная в стандартной форме записи задачи ЛП должна быть представлена как разность двух неотрицательных переменных:

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

Пример:

Ресторан быстрого обслуживания McBurger торгует порционными мясными пирогами и чизбургерами. На порцию мясного пирога идет четверть фунта мяса, а на чизбургер — только 0,2 фунта. В начале рабочего дня в ресторане имеется 200 фунтов мяса, можно еще прикупить мясо в течение дня, но уже с наценкой в 25 центов.

Мясо, оставшееся в конце рабочего дня, жертвуется благотворительной организации. Ресторан получает доход 20 центов от одной порции мясного пирога и 15 центов — от одного чизбургера. Как и многие другие, этот ресторан не может продать в день более 900 бутербродов. Какова должна быть доля каждого блюда (т.е.сколько порций мясного пирога и сколько чизбургеров) в ежедневном производстве ресторана, чтобы максимизировать его доход?

Сначала рассмотрим ограничения. Обозначим через х₁ и х₂ соответственно количество

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

В первом случае получаем ограничение в виде неравенства 0,25х₁ + 0,2х₂ ≤ 200, а во

втором — 0,25х₁+ 0,2х2 ≥ 200. Естественно, выбор одного из этих неравенств будет существенно влиять на возможное оптимальное решение. Так как мы не знаем, какое из них необходимо, логично заменить их одним равенством 0,25х₁ + 0,2х₂ + х₃= 200,

где х₃— свободная переменная. Фактически свободная переменная х₃ в данной ситуации одновременно играет роли как остаточной, так и избыточной переменной.

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

Для того чтобы раскрыть "двойственную" природу переменной х₃, используем стандартный математический прием, т.е. представим ее в следующем виде:

x₃ = x₃⁺ - x₃^-, где x₃⁺_,x₃^- ≥0

Если x₃⁺ ≥ 0 и х₃ = 0, то переменная х₃ играет роль остаточной. Если, напротив, x₃^- ≥ 0

и x₃⁺ = 0, то переменная х₃ выступает в роли избыточной. Итак, теперь ограничение можно записать в виде равенства

0,25 х₁ + 0,2 х₂ + х₃⁺- х₃^- = 200.

Целевая функция получает следующее выражение:

Максимизировать z = 0,20 + 0,15х₂ - 0,25 х₃

Алгоритм симплекс- метода.

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

Для описания алгоритма симплекс-метода будем использовать симплексные таблицы.

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

a₁₁x₁+a₁₂x₂+…+a_1nx_n ≤ b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n ≤ b₂

_{………………………………………….}

a_m1 x₁+a_m2x₂+…+a_mnx_n ≤ b_m

 

F=c₁x₁+c₂x₂+…+c_nx_n ® max.

Шаг 1. Введем добавочные переменные в ограничения, чтобы превратить неравенства в равенства. Запишем расширенную систему в виде:

a₁₁x₁+a₁₂x₂+…+a_1nx_n +x_n+1 = b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n + x_n+2 =b₂

_{………………………………………….}

a_m1 x₁+a_m2x₂+…+a_mnx_n + x_n+m = b_m

 

F-c₁x₁+c₂x₂+…+c_nx_n =0.

Шаг 2. Исходную расширенную систему заносим в первую симплексную таблицу. Последняя строка таблицы, в которой приведено уравнение для линейной функции цели, называется оценочной. В ней указываются коэффициенты функции цели с противоположным знаком: b_i=-c_i. В левом столбце записываем основные переменные (базис), в первой строке таблицы - все переменные (отмечая при этом основные), во втором столбце - свободные члены расширенной системы b_1, b₂,..., b_m. Последний столбец подготовлен для оценочных соотношений, необходимых при расчете наибольшего возможного значения переменной. В рабочую часть таблицы (начиная с третьего столбца и второй строки) занесены коэффициенты a_ij переменных из расширенной системы. Далее таблица преобразуется по определенным правилам.

Шаг 3. Проверяем выполнение критерия оптимальности при решении задач на максимум - наличие в последней строке отрицательных коэффициентов b_i<0 (c_i>0). Если таких нет, то решение оптимально, достигнут F=c₀ (в левом нижнем углу таблицы), основные переменные равны 0, т.е. получаем оптимальное базисное решение.

Шаг 4. Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный коэффициент b_i < 0 в последней строке определяет разрешающий столбец s.

Составляем оценочные ограничения каждой строки по следующим правилам:

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

2) ¥, если b_i=0 и a_is<0;

3) ¥, если a_is=0;

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

5)çb_i/a_is÷, если a_i0 a_is имеют одинаковые знаки.

Определяем min{ çb_i/a_is÷ }. Если конечного минимума нет, то задача не имеет конечного оптимума (F_max= ¥). Если минимум конечен, то выбираем строку q, на которой он достигается (любую, если их несколько), и называем ее разрешающей строкой. На пересечении разрешающих строки и столбца находится разрешающий элемент a_qs.

Шаг 5. Переходим к следующей таблице по правилам:

а) в левом столбце записываем новый базис: вместо основной переменной x_q -

переменную x_s;

б) в столбцах, соответствующих основным переменным, проставляем нули и единицы: 1- против «своей» основной переменной, 0 – в последней строке для всех основных переменных;

в) новую строку с номером q получаем из старой делением на разрешающий элемент a_qs;

г) все остальные элементы a¹_ij вычисляем по правилу прямоугольника:

a¹_ij= a_ij- a_is a_qj/ a_qs.

b¹_ij= b_i- a_is a_qj/ a_qs.

Далее переходим к шагу 3.

 

Пример. Решим симплексным методом задачу

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

 

L =

6 x1

+ 5 x2

+ 9 x3

 

при следующих ограничениях

 

			x1	+		x2	+		x3
		x1	+		x2	+		x3
		x1				+		x3

 

Решение:

Нам необходимо найти начальное опорное (абсолютно произвольное) решение для функции L, которое бы удовлетворяло системе наложенных ограничений. Далее, применяя симплекс таблицы, мы будем получать решения, при которых значение функции будет, как минимум, не убывать. И так до тех пор, пока не достигнем оптимально решения, при котором функция достигает своего максимума. Если, конечно, рассматриваемая нами линейная функция обладаем максимальным значением при заданной системе ограничений. Перед применением симплекс таблиц, необходимо преобразовать систему линейных ограничений и рассматриваемую нами функцию L к вполне определенному виду:

· Свободные члены системы ограничений должны быть неотрицательными;

· Система ограничений должна быть приведена к каноническому виду.

 

Ø К левой части неравенства 1 системы ограничений прибавляем неотрицательную переменную x₄ - преобразуем неравенство 1 в равенство.

 

Ø К левой части неравенства 2 системы ограничений прибавляем неотрицательную переменную x₅ – преобразуем неравенство 2 в равенство.

Ø К левой части неравенства 3 системы ограничений прибавляем неотрицательную переменную x6 – преобразуем неравенство 3 в равенство.

x1

+

x2

+

x3

+

x4

=

x1

+

x2

+

x3

+

x5

=

x1

+

x3

+

x6

=

L =

6 x1

+ 5 x2

+ 9 x3

 

Система ограничений приведена к каноническому виду, т.е. все условия системы представляют собой уравнения.

 

2. Определимся с начальным опорным решением.

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

· Переменная x₄ входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x₄ - базисная переменная;

· Переменная x₅ входит в уравнение 2 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x₅ – базисная переменная;

· Переменная x₆ входит в уравнение 3 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x₆ - базисная переменная;

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

X _нач = (0, 0, 0, 25, 20, 18)

 

Вернемся к рассмотрению функции L. Функция L не содержат базисных переменных.

Для составления начальной симплекс таблицы мы выполнили все условия.

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

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

2. В противном случае - функция не является ограниченной.

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

Шаг 1:

За ведущий выберем столбец 3, так как -9 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу свободных членов не рассматриваем.

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

базисные переменные	x1	x2	x3	x4	x5	x6	свободные члены	отношение
x4
x5								20/2
x6								18/3
L	- 6	- 5	- 9					-

 

Разделим элементы строки 3 на 3.

базисные переменные	x1	x2	x3	x4	x5	x6	свободные члены	отношение
x4
x5
x6
L	- 6	- 5	- 9					-

От элементов строки 1 отнимает соответствующие элементы строки 3, умноженные на 3.

От элементов строки 2 отнимает соответствующие элементы строки 3, умноженные на 2.

От элементов строки L отнимает соответствующие элементы строки 3, умноженные на -9.

базисные переменные	x1	x2	x3	x4	x5	x6	свободные члены
x4						- 1
x5	-					-
x3
L		- 5

 

X ₁ = (0, 0, 6, 7, 8, 0)

L =

-6 x1

+ 5 x2

-3 x6

 

 

Значение функции L для данного решения: L (X ₁) = 54

Шаг 2:

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

базисные переменные	x1	x2	x3	x4	x5	x6	свободные члены	отношение
x4						- 1
x5	-					-
x3								-
L		- 5						-

 

Разделим элементы строки 2 на 6

базисные переменные	x1	x2	x3	x4	x5	x6	свободные члены	отношение
x4						- 1
x5	-					-
x3								-
L		- 5						-

 

От элементов строки 1 отнимает соответствующие элементы строки 2, умноженные на 2.

От элементов строки L отнимает соответствующие элементы строки 2, умноженные на -5.

базисные переменные	x1	x2	x3	x4	x5	x6	свободные члены
x4					-	-
x2	-					-
x3
L

 

X ₂ = (0, 4/3, 6, 13/3, 0, 0)

L =	182/3	-83/18 x1	-5/6 x5	-22/9 x6

Значение функции L для данного решения: L (X ₂) = 182/3

Учитывая, что все x _i 0, по условию задачи, наибольшее значение функции L равно свободному члену 182/3, т.е. мы получили оптимальное решение.

Теперь можно записать ответ:

X _опт = (0, 4/3, 6, 13/3, 0, 0)

Значение функции: L = 182/3