Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Каждая итерация состоит из двух этапов.

I этап: проверка исследуемого опорного плана на оптимальность.

Просматривается (m+1)-я строка таблицы ?. Если все [pic], то опорный план, полученный после ?-й итерации, является оптимальным (случай 1), завершаем решение задачи. Пусть теперь имеются отрицательные оценки.
Проверяем знаки элементов [pic] столбцов [pic] с [pic]. Наличие по крайней мере одного столбца [pic], для которого [pic] и все [pic], свидетельствует о неразрешимости задачи (случай 2). Установив это, прекращаем вычисления.

Если в каждом столбце [pic], для которого [pic], содержится хотя бы один положительный коэффициент [pic], то опорный план является неоптимальным (случай 3). Переходим ко II этапу.

II этап: построение нового опорного плана с большим значением линейной формы.

Определяется вектор Ak, который должен быть введен в базис, из следующего условия

[pic].

После этого заполняется последний столбец таблицы ? – столбец t. В него записываются отношения базисных переменных [pic] (элементы столбца В) к соответствующим составляющим [pic] (элементы столбца Ak). Т.о. заполняются только те позиции, для которых [pic]. Если [pic], то в позиции i столбца t записывается [pic]. Вектор базиса [pic], на котором достигается t0,

[pic], подлежит исключению из базиса (если t0 достигается на нескольких векторах, то из базиса исключается любой из них).

Столбец Ak , отвечающий вектору, вводимому в базис, и l-я строка, соответствующая вектору [pic], исключаемому из базиса, называется соответственно разрешающим столбцом и разрешающей строкой. Элемент [pic], расположенный на пересечении разрешающего столбца и разрешающей строки, называется разрешающим элементом.

После выделения разрешающего элемента заполняется (?+1)-я таблица. В l- е позиции столбцов Бх, Сх вносятся соответственно Ак, Ск, которые в (?+1)-й таблице обозначаются как [pic], [pic]. В остальные позиции столбцов Бх, Сх вносятся те же параметры, что и в таблице ?.

Далее заполняется главная часть (?+1)-й таблицы. Прежде всего происходит заполнение ее l-й строки в соответствии с рекуррентной формулой

[pic].

Рекуррентная формула для заполнения i-й строки (?+1)-й таблицы имеет вид

[pic].
Здесь

[pic].

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

Решение исходной задачи

Весь процесс решения исходной задачи (2.12) - (2.13) приведен в табл. 4.2.

Заполнение таблицы, отвечающей 0-й итерации, происходит на основе табл. 3.2.1 (см. итерацию 1) следующим образом. Главная часть таблицы 0-й итерации исходной задачи (за исключением (m+1)-й строки) полностью повторяет главную часть таблицы заключительной итерации L-задачи без столбца А9. Также без изменений остается столбец базисных векторов Бх.
Строка С коэффициентов линейной формы исходной задачи и столбец Сх коэффициентов при базисных переменных заполняются исходя из (2.12). С учетом новых коэффициентов С пересчитываются значение линейной формы F и оценки [pic].

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

Таблица 4.2

[pic]

Решение исходной задачи (2.12) - (2.13) получено за 3 итерации.
Оптимальный план ее равен [pic] и [pic].

Найденное решение [pic] задачи в канонической форме (2.12) - (2.13) соответствует решению [pic] (4.1) общей задачи линейного программирования
(2.9) - (2.11), записанной для новых переменных [pic]. Для общей задачи из
(2.9) следует, что [pic] (4.2).

Рекомендуем скачать другие рефераты по теме: доклад, курсовая работа на тему предприятие.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата