Признак неограниченности целевой функции

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

С экономической точки зрения неограниченность целевой функции ЗЛП свидетельствует только об одном: разработанная модель недостаточно точна.

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

Решение

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

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

Итак, запишем задачу в каноническом виде. Для этого добавим к левым частям неравенств дополнительные переменные x₃, x₄, x₅. В целевую функцию они сводятся с коэффициентами, равными нулю:

Задача имеет предпочтительный вид.

Переменные x₃, x₄, x₅ – базисные, а x₁, x₂ – свободные. Положим, что x₁ = x₂ = 0, тогда x₃ = 14, x₄ = 3, x₅ = 36. Следовательно, x₀ = (0; 0; 14; 3; 36) является начальным опорным планом.

При этом 6 × 0 + 3 × 0 + 0 × 14 + 0 × 3 + 0 × 36 = 0. Заносим условие задачи в симплексную табл. 2.

Таблица 2

БП	сБ	А0	x1	x2	x3	x4	x5
x3			(2)
x4
x5
		–6	–3

Наличие в индексной строке ( -строке) отрицательных оценок при решении задачи на максимум свидетельствует о том, что оптимальное решение не получено. От табл. 2 перейдем к табл. 3.

Таблица 3

БП	сБ	А0	x1	x2	x3	x4	x5
x1
x4
x5				–5	–2

Разрешающий столбец находим по max{|–6|; |–3|} = 6. Разрешающая строка определяется по минимуму отношений свободных членов к положительным элементам разрешающего столбца, т. е.

.

На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент 2.

В табл. 3 вместо x₃ в базис вводим переменную x₁.

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

В индексной строке табл. 3 нет отрицательных элементов. Следовательно, мы получаем оптимальный план x^* = х_опт = (7; 0; 0; 3; 8). Тогда = z(х_опт) = 42, z_min = z(х_опт) = –42.

Ответ: х_опт = (7; 0; 0; 3; 8), z_min = –42.

Пример 3. Решить задачу

Решение

Сведем задачу к каноническому виду. Получим

Занесем условие в симплексную табл. 4. Начальный опорный план имеет вид x₀ = (0; 0; 3; 10), z(x₀) = 0.

Таблица 4

БП	сБ	А0	x1	x2	x3	x4
x3			–1
x4
zj – cj		–2	–1

Задача решается на максимум. Опорный план x₀ неоптимальный, так как существуют отрицательные оценки. Находим разрешающий столбец по max{|–2|, |–1|} = 2.

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

Ответ: .

2.9. Метод искусственного базиса (М-задача)

Решение задачи линейного программирования симплекс-методом начинается с нахождения какого-либо опорного плана.

Рассмотрим третий случай построения начального опорного плана (первый и второй описаны в пункте 2.1).

Пусть система ограничений имеет вид

.

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

.

Теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные x_n+i входят в левую часть (при b_i 0) с коэффициентами, равными –1. В этом случае вводится так называемый искусственный базис путем перехода к М-задаче.

К левым частям ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные w_i. В целевую функцию переменные w_i вводят с коэффициентом M в случае решения задачи на минимум и с коэффициентом –M – для задачи на максимум, где M – большое положительное число. Полученная задача называется М-задачей, соответствующей исходной. Она всегда имеет предпочтительный вид.

Пусть исходная задача линейного программирования имеет вид

;	(7)
;	(8)
	(9)

При этом ни одно из ограничений не имеет предпочтительной переменной. М-задача будет записываться следующим образом:

;	(10)
	(11)
	(12)

При этом знак “–” в функции (10) относится к задаче на максимум. Задача (10)–(12) имеет предпочтительный вид. Ее начальный опорный план имеет вид

.

Если некоторые из уравнений (8) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема 5.Если в оптимальном плане х_опт = М-задачи (10)–(12) все искусственные переменные , то план является оптимальным планом исходной задачи (7)–(9).

Теорема 6 (признак несовместности системы ограничений). Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то система ограничений исходной задачи несовместна.

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

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

Решение

Сведем задачу к каноническому виду. Получим

Первое ограничение имеет предпочтительную переменную х₃, а второе – нет. Поэтому вводим в него искусственную переменную w₁. Приходим к М-задаче

Занесем условие М-задачи в симплексную табл. 5. Начальный опорный план имеет вид x₀ = (x₁; x₂; x₃; x₄; w₁) = (0; 0; 2; 0; 12), z(x₀) = 0 – 12M.

Таблица 5

БП	сБ	А0	x1	x2	x3	x4	w1
				–M
x3				(1)
w1	–M					–1
zj – cj		–6	–4
–12M	–3M	–4M		M

Сделаем необходимые пояснения.

Индексную строку удобно разбить на две. В первой из них записываются свободные члены выражений D₀ = c_Б × А₀ и D_j = c_Б × A_j – c_j, а во второй – коэффициенты, содержащие M. Например, для табл. 5:

Признак оптимальности проверяем сначала по второй строке индексной строки. Так как в ней существуют отрицательные оценки, то план x₀ не является оптимальным.

Переходим к новой табл. 6.

Разрешающий столбец находим по max{|–3M|; |–4M|} = 4M, разрешающая строка определяется по . Следовательно, 1 – разрешающий элемент.

Таблица 6

БП	сБ	А0	x1	x2	x3	x4	w1
				–M
x2
w1	–M		–5		–4	–1
zj – cj
–4M	5M		4M	M

В индексной строке нет отрицательных оценок. Следовательно, по признаку оптимальности опорный план (0; 2; 0; 0; 4) оптимален. Но так как в оптимальном плане искусственная переменная w₁ не равна 0, то по теореме 6 система ограничений исходной задачи несовместна. Задача решения не имеет.

Ответ:нет решения.

Пример 5. Решить с использованием искусственного базиса задачу

Решение

Упорядочим запись исходной задачи. Умножим второе неравенство на –1:

Сведем задачу к каноническому виду. Получим

Первое и четвертое ограничения имеют предпочтительные переменные, а второе и третье – нет. Поэтому вводим в них искусственные переменные w₁ и w₂. Приходим к М-задаче

Занесем условие М-задачи в симплексную табл. 7. Начальный опорный план имеет вид x₀ = (0; 0; 10; 0; 0; 4; 3; 9), z(x₀) = 0 + 12M.

Таблица 7

БП	сБ	А0	x1	x2	x3	x4	x5	x6	w1	w2
	–1					M	M
x3
w1	M		(1)	–3		–1
w2	M						–1
х6			–1
zj – cj		–1
12M	4M	–2M		–M	–M

Мы решаем задачу на минимум. Признак оптимальности проверяем сначала по второй строке индексной строки. Так как в ней существует положительная оценка, то план x₀ не является оптимальным. Переходим к новой табл. 8.

Таблица 8

БП	сБ	А0	x1	x2	x3	x4	x5	x6	w2
	–1					M
x3
x1				–3		–1
w2	M			(10)			–1
x6				–2		–1
zj – cj			–2		–1
		10M		3M	–M

По мере вывода из базиса искусственных переменных соответствующие им столбцы можно опускать. Разрешающий столбец находим по max{4M} = 4M, разрешающая строка определяется по . Следовательно, 1 – разрешающий элемент.

Так как существуют положительные оценки, то план x₁ = (3; 0; 7; 0; 0; 7; 0; 0) не является оптимальным.

Переходим к табл. 9. Разрешающий столбец находим по max{10M; 3M} = 10M, разрешающая строка определяется по .

Итак, 10 – разрешающий элемент.

Таблица 9

БП	сБ	А0	x1	x2	х3	x4	x5	x6
	–1
x3
x1
x2	–1
x6
zj – cj

Так как все оценки неположительны, то получен оптимальный план. Итак, x^* = х_опт = (3; 0; 7; 0; 0; 7), z_min = (x^*) = 3.

Ответ: х_опт = (3; 0; 7; 0; 0; 7), z_min = 3.

Вопросы для самоконтроля

1. Суть симплекс-метода. Свойства задач линейного программирования, на которых он основан.

2. Последовательность этапов практической реализации алгоритма симплекс-метода при решении задач линейного программирования.

3. Построение начального опорного плана (3 случая).

4. Случаи, когда опорный план оптимален.

5. Переход к нехудшему опорному плану.

6. Симплексные преобразования.

7. Признак бесконечности множества оптимальных планов.

8. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание.

9. Признак неограниченности целевой функции.

10. Необходимость использования симплекс-метода с искусственным базисом (М-метода). Суть этой модификации симплекс-метода.

11. Определение искусственной переменной. Случаи, при которых она вводится. Коэффициент, соответствующий ей в линейной функции. Проведение анализа плана по индексной строке.

12. Признак несовместности системы ограничений.