Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
2. Составление первого опорного плана.
Система ограничений задачи, решаемой симплексным методом, задана в виде системы неравенств. Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных переменных. Векторы-столбцы при этих переменных представляют собой единичные векторы и образуют базис, а соответствующие им переменные называются базисными:
где базисные переменные.
свободные переменные.
Решим эту систему относительно базисных переменных:
а функцию цели перепишем в таком виде:
Полагая, что основные переменные
.получим первый опорный план ,(заносим его в симплексную таблицу 3, которая состоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной. Она заполняется коэффициентами функции цели, взятыми с противоположным знаком.
3. Проверка плана на оптимальность.
Если все коэффициенты индексной строки симплексной таблицы при решении задачи на максимум неотрицательны ( 0), то
план табл.3 задачи табл. 2 является оптимальным. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный и его можно улучшить. Тогда переходим к следующему этапу алгоритма.
4. Определение ведущих столбца и строки.
Из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине, что и определяет ведущий столбец, который показывает, какая переменная на следующей итерации перейдет из свободных в базисные.
Затем элементы столбца свободных членов симплексной таблицы делим на соответствующие только положительные элементы ведущего столбца. Результаты заносим в отдельный столбец . Строка симплексной таблицы, соответствующая минимальному значению , является ведущей. Она определяет переменную которая на следующей итерации выйдет из базиса и станет свободной.
Дата публикования: 2015-04-06; Прочитано: 265 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!