Основные шаги вычислительного процесса симплекс-метода

Одесская государственная академия строительства и архитектуры

Кафедра процессов и аппаратов технологии строительных материалов

Расчетно графическая работа

По основам системного анализа

Выполнил(а) ст. гр. ПСК-357

Расчет проверил

Доцент каф. ПАТСМ

ОГАРКОВ Б.Л.

Одесса - 2012

I. Решение задачи линейного программирования

Задача ЛП в стандартной форме с т ограничениями и п пере­менными имеет следующий вид: максимизировать или минимизировать Z = c₁x₁ + с₂х₂+ -... + c_nx_n

при ограничениях

Задачи ЛП в стандартной форме можно записать в компактных мат­ричных обозначениях следующим образом:

максимизировать или минимизировать Z = cx при ограничениях Ах = b, х> =0, b> =0,

где А — матрица размерности т Х п, х —вектор-столбец размер­ности их 1, b— вектор-столбец размерности т Х 1, с — вектор-строка размерности 1 Х п.

Обычно А называется матрицей коэффициентов, х — вектором переменных, b — вектором ресурсов, с — вектором оценок задачи ЛП.

Основные шаги вычислительного процесса симплекс-метода

Основными шагами процесса вычислений в соответствии с сим­плекс-методом в табличной форме применительно к задаче макси­мизации являются следующие:

Шаг 1. Записать задачу в стандартной форме.

Ш а г 2. Заполнить первоначальную таблицу с использованием начального допустимого базисного решения. (Процедура отыскания такого решения описываются ниже.)

Шаг 3. Вычислить вектор относительных оценок (строки с) при помощи правила скалярного произведения.

Ш а г 4. Если все оценки c _j неположительные, текущее допу­стимое базисное решение оптимальное. В противном случае не­обходимо ввести в базис небазисную переменную с наибольшим значением c _j.

Шаг 5. Определить при помощи правила минимального от­ношения переменную, выводимую из базиса.

Ш а г 6. Применить элементарное преобразование для получе­ния нового допустимого базисного решения и новой таблицы.

Шаг 7. Вычислить новые относительные оценки с использо­ванием элементарного преобразования или правила скалярного произведения. Перейти к шагу 4.

Итерацией симплекс-метода называется выполнение шагов 4—7 описанного процесса. На каждой итерации получаются новая таб­лица и улучшенное допустимое базисное решение. Число допусти­мых базисных решений, просматриваемых при использовании сим­плекс-метода, представляет собой важную характеристику эффек­тивности этого метода.

Условия задачи

Fmax=3x1+3x2

1x1-1x2< =4

3x1+2x2< =6

-1x1+1x2< =1

1x1+2x2> =2