Общий алгоритм решения задач линейного программирования
Без ограничения общности имеем следующую задачу линейного программирования:
, (4.1) .
Найти среди допустимых , j = 1, 2, ..., n, такие, что: .
Основные шаги решения сформулированной задачи следующие. 1. Находится хотя бы одно из неотрицательных решений . 2. Подставляем в систему полученное решение, в результате чего получаем новую систему, эквивалентную исходной:
.
3. Подставляем выражения основных переменных в L:
.
4. Применяем последовательность тождественных преобразований к полученной системе и линейной форме до тех пор, пока не исчезнут положительные коэффициенты при переменных в линейной форме, т.е. нарушатся условия ее существования. После конечного числа указанных шагов (если нет зацикливания) находится оптимальное решение поставленной задачи. В этом заключается суть симплекс-метода. Возникает вопрос. Как найти хотя бы одно неотрицательное решение системы (4.1)? Сводим исходную систему (4.1) к виду: , i = 1, 2, ..., m. (4.2)
Если в этой системе имеется переменная, входящая только в одно уравнение, и коэффициент при ней имеет знак «+», то уравнение можно разрешить относительно этой переменной. Считаем, что в (4.2) уравнения разрешены относительно всех таких переменных, тогда, сделав перенумерацию, имеем:
(4.3) l = 1, 2, ..., l0; = 1, 2, ..., 0; l0 + 0 = m; l0 + k = n; .
Любое уравнение в (4.3), неразрешенное относительно какой-либо переменной, будем называть 0-уравнением. Для системы (4.3) неотрицательное решение отыскивается последовательными тождественными преобразованиями, удовлетворяющими следующим условиям: 1. Отыскиваем 0-уравнение, у которого свободный член (если такого свободного члена нет, то значения переменных xl = bl, , l = 1, 2, ..., l0; j = 1, 2, ..., k образуют неотрицательное решение системы (4.3)). Пусть это будет i-ое уравнение. 2. Отмечаем в i-ом уравнении положительный коэффициент . 3. Находим разрешающий элемент и производим торжественное преобразование (4.3). 4. i-ое 0-уравнение используется до тех пор, пока либо разрешим его, либо придем к несовместимости системы (4.3). 5. После разрешения i-го уравнения отыскиваем следующее 0-уравнение с положительным свободным членом и производим с ним аналогичные действия. 6. Процесс продолжается до тех пор, пока не освободимся от всех 0-уравнений. В результате можем получить: а) после конечного числа тождественных преобразований система освободится от 0-уравнений. Тогда система будет совместимой. Совокупность значений переменных, получаемых приравниванием неосновных переменных нулю, а основных - свободным членам в системе, не содержащей 0-уравнений, является неотрицательным решением исходной системы; б) После конечного числа тождественных преобразований обнаружится, что используемое 0-уравнение превращается в уравнение вида:
,
где , т.е. для всех j - система несовместна; в) система не освобождается полностью от 0-уравнений, а условия тождественных преобразований не нарушаются. Число 0-уравнений не увеличивается, а некоторые из них имеют по крайней мере один положительный коэффициент в правой части, но разрешающий элемент ему не принадлежит.
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Почему стероиды повышают давление?: Основных причин три... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (185)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |