Табличное представление задачи ЛП, симплекс-таблица. Симплекс-метод для отыскания опорного решения задачи ЛП

Страницы работы

8 страниц (Word-файл)

Фрагмент текста работы

Этот факт хорошо иллюстрируется геометрическим представлением данной задачи на рисунке 2.5.

Рисунок 2.5 – Геометрическая иллюстрация решения задачи ЛП из примера 2.5

1.1.2. Симплекс-метод для отыскания опорного решения задачи ЛП

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

Описание первого этапа симплекс-метода

Рассмотрим первый этап симплекс-метода.

Пусть в таблице вида (2.12) все свободные члены неотрицательны, т.е.  b1 ≥ 0, …, bm ≥  0. В этом случае таблица вида (2.12) дает возможность сразу получить одно из допустимых опорных решений задачи (2.4) и можно считать, что первый этап выполнен.

Теперь предположим, что в таблице вида (2.12) есть хотя бы один отрицательный свободный член, например, пусть  b i 0 < 0. В этом случае точка (x,y), определяемая данной симплекс-таблицей, соответствует недопустимому решению, так как  у i 0 = b i 0 < 0.

Симплекс-метод для отыскания допустимого опорного решения означает специальное правило перехода от данной точки  Р0 = (x,y) к такой соседней, которую отделяет от выпуклого многогранника D (являющегося множеством допустимых решений исходной задачи) меньшее (во всяком случае не большее) число гиперплоскостей, т.е. для которой в соответствующей таблице содержится меньшее (не большее) число отрицательных свободных членов.

Для осуществления перехода от вершины  Р0 = (x,y) к указанной соседней производим шаг жорданова исключения, выбирая разрешающий элемент согласно ПРАВИЛУ 1. После конечного числа шагов либо установим несовместность системы ограничений, либо перейдем к таблице, не содержащей отрицательных свободных членов, т.е. получим допустимое опорное решение задачи, приравняв нулю все независимые переменные, оказавшиеся на верху таблицы.

ПРАВИЛО 1 выбора разрешающего элемента

1.   Выбираем строку с отрицательным свободным членом, например,  bi<0 (обычно берут строку с наибольшим по абсолютной величине отрицательным свободным членом). Если среди коэффициентов этой строки нет отрицательных, то система ограничений задачи несовместна и, следовательно, задача не имеет решения.

2.  Если же среди коэффициентов рассматриваемой строки есть отрицательные, то берем какой-нибудь из них, например  a i0 s<0, а столбец, содержащий этот коэффициент, т.е.  s-й столбец, берем в качестве разрешающего.

3.  Выбор разрешающей строки производится следующим образом. Вычисляются все неотрицательные отношения   ≥ 0  свободных членов к соответствующим отличным от нуля коэффициентам разрешающего столбца (так называемые "симплекс-отношения").  Среди этих отношений находится наименьшее, которое достигается, например, при  i = r . Тогда  r-ю строку берем в качестве разрешающей, а элемент  ars - разрешающим.

Примечание 3. В случае вырождения, когда  , элемент  ars  выбираем  в качестве разрешающего лишь в том случае, если при  ars >0 .

Пример 2.5 (продолжение)

Рассмотрим таблицу, соответствующую итерации 1 примера 2.5, полученную выше:

Итерация 1

- x1

- x2

1

Пометки

Расчет симплексных отношений

y1 =

- 2

- 1

- 2

Наибольшее нарушение

-2

= 2

-1

y2 =

1

1

4

4

= 4

1

y3 =

0

- 1

Разреш элемент

-1

← Разрешающая строка

-1

= 1

-1

Z' =

-5

- 1

0

Разреш. столбец

Так как y1 = -2 < 0 и y3 = -1 < 0, то точка (x,y)0 = (0; 0; - 2; +4; - 1), определяемая данной таблицей, соответствует недопустимому решению. Поэтому необходимо произвести переход к другой точке с помощью модифицированного жорданова исключения. Разрешающий элемент выбираем по правилу 1. а именно: в первой строке (так как b1 = -2 по абсолютной величине больше b3 = -1) отыскиваем любой отрицательный коэффициент, например, a12 = -1, поэтому 2-ой столбец объявляем разрешающим. Теперь рассчитаем неотрицательные симплексные отношения:      b1 : a12 = (-2) : (-1) = 2 > 0,     b2 : a22 = 4 : 1 = 4 > 0,      b3 : a32 = (-1) : (-1) = 1 > 0. минимальное из них соответствует 3-ей строке, а, следовательно, 3-я строка объявляется разрешающей. При  этом элемент a32 будет разрешающим элементом.

Переходим к следующей 2-ой итерации.

Итерация 2

- x1

- y3

1

Пометки

Расчет симплексных отношений

y1 =

- 2

- 1

Разреш элемент

- 1

Наибольшее нарушение

Разршающая строка

-1

= 1

-1

y2 =

1

1

3

4

= 4

1

x2 =

0

- 1

1

-1

= 1

-1

Z' =

-5

- 1

1

Разреш. столбец

Эта таблица определяет точку (x, y)1 = (0; 1; -1; 3; 0)    (или точку x= (0;1) ). Эта точка соответствует  решению, которое также является недопустимым, так как y1 = -1 < 0. Поэтому переходим к следующей точке, т.е. к следующей таблице. Разрешающий элемент a12 = - 1.

Эта таблица определяет точку (x, y)2 = (0; 2; 0; 2; 1)    (или точку x= (0;2) ).  Полученная точка соответствует допустимому решению, так как в соответствующей таблице все свободные члены bi   положительны.

Итерация 3

- x1

- y1

1

y3 =

2

-1

1

y2 =

-1

1

2

x2 =

2

- 1

2

Z' = 

-3

- 1

 2

1.1.3. Симплекс-метод для отыскания оптимального решения  ЗЛП

Описание второго этапа симплекс-метода

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

x1

xk

ys+1

ym

y1 =

α11

α1 k

α 1, s+1

α1 n

β1

ys =

α s1

α sk

α s, s+1

α sn

βs

(2.13)

xk+1

α k+1, 1

α k+1, k

α k+1, s+1

α k+1, n

βk+1

xn =

α m1

α mk

α m, s+1

α m n

βm

Z =

q1

qk

qs+1

qn

Q

После нескольких шагов жордановых исключений на верх таблицы перешло (m-l) зависимых переменных  yi , а слева от таблицы появилось (n-k)переменных  xj; очевидно, что  m-l = n-k.   Так как первый этап симплекс-метода выполнен, в таблице вида

Похожие материалы

Информация о работе