Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритм табличного симплекс-метода
Алгоритм симплекс-метода сводится к следующему: 1. Выбираются k=n-m свободных переменных. 2. Базисные переменные и целевая функция выражаются через свободные в виде (3.18) и (3.19). 3. определяется опорное решение задачи ЛП, для чего все свободные переменные полагаются равными нулю. Если все свободные члены b k +i положительны, то полученное решение будет допустимым. 4. Допустимое решение проверяется на оптимальность. Если все коэффициенты r j в (3.19) отрицательны, то полученное допустимое решение является оптимальным. 5. Пусть коэффициент rj (3.19) имеет положительное значение. Среди коэффициентов n k+i,j (i =1, m; j =1, k) ищутся такие, которые имеют одинаковый знак со свободными членами b k +i. Для всех таких коэффициентов находятся отношения и определяется минимальное из них, т.е.
Переменная x=k+i, для которой выполняется условие (3.20) переводится в состав свободных, а переменная xj, у которой коэффициент r j в (3.19) положителен - в состав базисных. Далее выполняются п.п.2-5 до тех пор, пока не будет найдено оптимальное решение. Таким образом, признак допустимости решения один (все b k +i положительны), а признаков оптимальности решения два: - все b k+i положительны, i = i,m; - все r j отрицательны, j = i,k. Далее, для того, чтобы L (x) достигала максимума необходимо, чтобы в (3.19) значения всех коэффициентов при переменных были отрицательными. В том случае, если хотя бы один из коэффициентов, например, r j, положителен, то эта переменная (т.е. xj) должна быть переведена из свободных в базисные, а одна из базисных должна быть переведена в свободные. Исходными данными при заполнении первой симплекс-таблицы служат свободные члены и коэффициенты при переменных в выражениях (3.18) и (3.19). Симплекс-таблица содержит m +1 строк и k +1 столбцов. В первой строке записываются коэффициенты, содержащиеся в выражении (3.19) для целевой функции L (x). Остальные строки служат для записи соответствующих коэффициентов в выражениях для базисных переменных (3.18). Первый столбец симплекс-таблицы содержит свободные члены выражений (3.18) и (3.19), а остальные столбцы - коэффициенты при свободных переменных. На основании (3.18) и (3.19) заполним первую (исходную) симплекс-таблицу. Таблица 3.2
В соответствии с рассмотренным выше алгоритмом симплекс-метода для получения первого решения все свободные переменные необходимо положить равными нулю. Тогда пересечение первого столбца и первой строки даст значение целевой функции, а остальные элементы первого столбца - значения базисных переменных. Если все значения базисных переменных неотрицательны, то полученное решение является допустимым.
Для проверки этого решения на оптимальность обратимся к элементам первой строки симплекс-таблицы. Если все элементы этой строки (за исключением свободного члена g0) отрицательны, то полученное решение оптимально. В том случае, когда один или несколько элементов в первой строке положительны, решение не оптимально и его можно улучшить. Для этого необходимо произвести обмен между свободными и базисными переменными в соответствии с правилами симплекс-преобразования. 1. Среди положительных элементов первой строки симплекс-таблицы выбирается тот, который имеет наибольшее значение. Пусть это будет r1 при x 1. Это значит, что переменная x1 должна быть переведена из свободных в базисные. Столбец, в котором находится наибольший положительный коэффициент, назовем разрешающим столбцом. 2. В разрешающем столбце определяются те элементы, которые имеют одинаковый знак с соответствующими свободными членами. Пусть это будут коэффициенты n k +1,1 и n k +2,1. 3. Рассчитываются отношения соответствующих свободных членов к коэффициентам n k +1,1 и n k +2,1. Пусть выполняется следующее неравенство:
Тогда строку, соответствующую переменной xk +1, для которой выполняется неравенство (8), назовем разрешающей строкой. Элемент n k +1,1 лежащий на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом. Базисная переменная xk +1 должна быть переведена в состав свободных переменных. 4. Строится новая симплекс-таблица для новой системы свободных (xk +1, x 2,..., xk) и базисных (x 1, xk +2,..., xk+m) переменных.
Элементы новой симплекс-таблицы заполняются следующим образом. 5. Вычисляется обратная величина 1/ν k +1,1 разрешающего элемента исходной таблицы и это значение записывается в соответствующей клетке новой симплекс-таблицы. 6. Все элементы разрешающего столбца исходной симплекс-таблицы делятся на разрешающий элемент. Полученные значения с обратным знаком записываются в соответствующих клетках новой симплекс-таблицы. 7. Все элементы разрешающей строки исходной симплекс-таблицы делятся на разрешающий элемент. Полученные значения записываются в соответствующих клетках новой симплекс-таблицы. 8. Остальные элементы новой симплекс-таблицы рассчитываются в соответствии с правилом прямоугольника, которое состоит в следующем. Пусть необходимо рассчитать значение элемента новой симплекс-таблицы стоящего на пересечении i строки и j -го столбца, т.е. n’ ij. Составим из элементов исходной симплекс-таблицы прямоугольную матрицу 2x2. где n lk - разрешающий элемент. l – разрешающая строка, k – разрешающий столбец. Тогда
В общем виде новая симплекс-таблица представлена таблицей 3.3. Полагая значения свободных переменных равными нулю, из первого столбца находим значение целевой функции и базисных переменных. По элементам первой строки проверяем полученное решение на оптимальность. Если решение неоптимальное, переходим к следующей симплекс-таблице по п.п.1-8 табличного алгоритма.
Таблица 3.3
Перечислим без доказательства некоторые правила анализа симплекс-таблиц: 1. Если в конечной симплекс-таблице элементы первого столбца положительны, а элементы первой строки (кроме свободного члена g0) - отрицательны, задача линейного программирования имеет единственное оптимальное решение. 2. Если в конечной симплекс-таблице элементы первого столбца положительны, а среди элементов первой строки имеются один или несколько нулевых элементов, задача линейного программирования имеет бесчисленное множество оптимальных решений. 3. Если в конечной симплекс-таблице элементы первого столбца положительны, среди элементов первой строки имеется хотя бы один положительный элемент, а в столбце, соответствующем этому положительному элементу, остальные элементы отрицательны, задача линейного программирования не имеет оптимального решения. Разработанный симплекс-метод имеет достаточно много лишних вычислений, не несущих информации. С целью сокращения машинного времени решения задачи был разработан модифицированный метод (Данцин, 1953 г.). По идее он близок к табличному симплекс-методу, но обладает тем преимуществом, что вычисляет действительно нужные величины. При этом количество вычислений напрямую связано с количеством ограничений, а не с количеством переменных, которых значительно больше. Недостатком МСМ следует считать большую потребность в машинной памяти.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-02-08; просмотров: 490; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.230.35.103 (0.015 с.) |