![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Основные шаги вычислительного процесса симплекс-методаСтр 1 из 2Следующая ⇒
Одесская государственная академия строительства и архитектуры Кафедра процессов и аппаратов технологии строительных материалов Расчетно графическая работа По основам системного анализа Выполнил(а) ст. гр. ПСК-357
Расчет проверил Доцент каф. ПАТСМ ОГАРКОВ Б.Л. Одесса - 2012 I. Решение задачи линейного программирования Задача ЛП в стандартной форме с т ограничениями и п переменными имеет следующий вид: максимизировать или минимизировать Z = c1x1 + с2х2+ -... + cnxn при ограничениях Задачи ЛП в стандартной форме можно записать в компактных матричных обозначениях следующим образом: максимизировать или минимизировать 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
|