Смекни!
smekni.com

Линейное программирование 4 (стр. 2 из 2)

Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные X1, X2, ..., Xr и что при этом b1, b2,..., br ≥ 0 (соответствующее базисное решение является опорным).

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

Далее эта система оформляется в виде симплекс-таблиц:

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

Порядок работы с симплекс таблицей

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

Алгоритм перехода к следующей таблице такой:

  • просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов
    ) выбирается наименьшее отрицательное число при отысканииmax, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;
  • просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту в последней строке- ключевой столбец, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет;
  • среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка в которой он находится ключевой;
  • в дальнейшем базисная переменная, отвечающая строке разрешающего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу разрешающего элемента, вводится в число базисных. Строится новая таблица, содержащая новые названия базисных переменных:
  • разделим каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы.
  • строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.
  • в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.
  • столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.
  • строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же.
  • в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

В результате получают новую симплекс-таблицу, отвечающую новому базисному решению.

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

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

Пример 2.4.1

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

(2.16)

Этому способу разбиения переменных на основные и неосновные соответствует базисное решение (k1 , k2, ... , km , 0, 0, ... , 0). Рассмотрим общий случай, когда это решение является недопустимым. От полученного базисного решения следует сначала перейти к какому-нибудь допустимому базисному решению. Причем не обязательно, чтобы этот переход осуществлялся сразу, за один шаг.
По предположению исходное базисное решение недопустимо. Следовательно, среди свободных членов системы ограничений (2.16) имеется хотя бы один отрицательный (число отрицательных свободных членов этой системы совпадает с числом отрицательных компонент исходного базисного решения). Пусть им является свободный член i-го уравнения ki , т. е. основная переменная xi в соответствующем базисном решении отрицательна.
Для перехода к новому базисному решению необходимо: выбрать переменную, которую следует перевести из неосновных в основные; установить, какая основная переменная при этом перейдет в число неосновных переменных. При переводе неосновной переменной в основные ее значение, как правило, возрастает: вместо нуля в исходном базисном решении оно будет положительно в новом базисном решении (исключая случай вырождения). Вернемся к i-му уравнению системы (2.16), содержащему отрицательный свободный член k1. Оно показывает, что значение переменной xi растет при возрастании значений тех неосновных переменных, которые в этом уравнении имеют положительные коэффициенты. Отсюда следует, что в основные можно переводить те неосновные переменные, которые в уравнении системы (2.16) с отрицательным свободным членом имеют положительные коэффициенты.

Здесь может быть три исхода:

  1. в i-м уравнении системы (2.16) нет основных переменных с положительными коэффициентами, т. е. все коэффициенты bi, m+j (как и свободный член ki) отрицательны. В этом случае система ограничений несовместна, она не имеет ни одного допустимого решения, а следовательно, и оптимального;
  2. в i-м уравнения имеется одна переменная xm+j , коэффициент b при которой положителен. В этом случае именно эта переменная переводится в основные;
  3. в i-м уравнении имеется несколько переменных с положительными коэффициентами bi, m+j . В этом случае в основные можно перевести любую из них.

Далее необходимо установить, какая основная переменная должна быть переведена в число неосновных на место переводимой в основные. В неосновные переводится та основная переменная, которая первой обратится в нуль при возрастании от нуля неосновной переменной, переводимой в основные. Иными словами, пользуемся тем же правилом, которое было установлено ранее. Находятся отношения свободных членов к коэффициентам при переменной, переводимой в основные, из всех уравнений, где знаки свободных членов и указанных коэффициентов противоположны, берется абсолютная величина этих отношений и из них выбирается наименьшая (если в некоторых уравнениях знаки свободных членов и указанных коэффициентов совпадают или в каких-то уравнениях переменная, переводимая в основные, отсутствует, то указанное отношение считается равным ).
Уравнение, из которого получено наименьшее отношение, выделяется. Выделенное уравнение и покажет, какая из основных переменных должна быть переведена в неосновные. Выразив новые основные переменные через неосновные, перейдем к следующему базисному решению.
Если выделенным окажется уравнение с отрицательным свободным членом, то в новом базисном решении число отрицательных компонент будет на единицу меньше, чем в исходном. Если же выделенным окажется уравнение с положительным (или равным нулю) свободным членом, то в новом базисном решении число отрицательных компонент сохранится таким же, каким оно было в исходном базисном решении.
Таким образом, при переходе к новому базисному решению выгодно, чтобы выделенным оказалось уравнение с отрицательным свободным членом, и если есть возможность выбора, то предпочтение следует отдать такому обмену переменных, при котором выделенным оказывается уравнение с отрицательным свободным членом.
Итак, мы получим новое, улучшенное базисное решение, которое ближе к области допустимых решений системы ограничений. Если оно недопустимое, то к нему следует применить ту же схему еще раз. В результате через конечное число шагов мы получим допустимое базисное решение. Как только будет найдено допустимое базисное решение, переходят ко второму этапу симплексного метода, сущность которого рассмотрена при решении задачи примера 2.4.1.
После овладения способом нахождения первого допустимого базисного решения любая задача линейного программирования может иметь трудности лишь вычислительного характера.