Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Опорным решением задачи называется допустимое неотрицательное решение. Идея симплексного метода заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному решению.
3.2. Алгоритм симплексного метода
1. Математическая модель должна быть канонической. Если она неканоническая, то её надо привести к каноническому виду.
2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу. Все строки таблицы 1-го шага, за исключением строки ∆j заполняем по данным системы ограничений и целевой функции:
Таблица 3.1
сi | БП | с1 | с2 | … | cm | cm+1 | … | cn | |
x1 | x2 | … | xm | xm+1 | … | xn | bi | ||
c1 | x1 | 1 | 0 | … | 0 | h1,m+1 | … | h1n | f1 |
c2 | x2 | 0 | 1 | … | 0 | h2.m+1 | … | h2n | f2 |
… | … | … | … | … | … | … | … | … | … |
cm | xm | 0 | 0 | … | 1 | hm,m+1 | … | hmn | fm |
∆j | 0 | 0 | … | 0 | ∆m+1 | … | ∆n |
Индексная строка для переменных находится по формуле
и по формуле для свободного члена.
Возможны следующие случаи при решении задачи на максимум:
- если все оценки , то найденное решение оптимальное;
- если хотя бы одна оценка , но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращаем, так как , т. е. целевая функция неограниченна в области допустимых решений;
- если хотя бы одна оценка отрицательна, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению;
- если отрицательных оценок в индексной строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка.
Если хотя бы одна оценка , то к -й столбец принимаем за ключевой. За ключевую строку принимаем ту, которой соответствует минимальное отношение свободных членов (fi) к положительным коэффициентам к -го столбца. Элемент, находящийся на пересечении ключевой строки и ключевого столбца, называется ключевым элементом.
3. Заполняем симплексную таблицу 2-го шага:
- переписываем ключевую строку, разделив её на ключевой элемент;
- заполняем базисные столбцы;
- остальные коэффициенты таблицы находим по правилу «прямоугольника». Оценки можно считать по приведённым выше формулам или по правилу «прямоугольника». Получаем новое опорное решение, которое проверяем на оптимальность, и т. д.
Правило «прямоугольника» заключается в следующем. Пусть ключевым элементом 1-го шага является элемент 1-й строки (m+1)-го столбца h1,m+1. Тогда элемент i -й строки (m+2)-го столбца 2-го шага – обозначим его согласно правилу «прямоугольника» выражается формулой
,
где hi,m+2, hi,m+1, h1,m+1 – элементы 1-го шага.
Примечание 1. Если целевая функция требует нахождения минимального значения, то критерием оптимальности задачи является следующее условие:
Примечание 2. Если в правой части какого-нибудь неравенства из системы ограничений стоит отрицательное число, то обе части этого неравенства нужно разделить на (-1), а потом приводить это неравенство к каноническому виду.
Примечание 3. Пусть модель каноническая, но нет переменных, которые можно использовать в качестве базисных (т. е. таких, которые в одном уравнении стоят с коэффициентом 1, а в других вообще отсутствуют). Тогда нужно по своему усмотрению выбирать базисные переменные, определять ключевой столбец и строку, пересчитывать элементы таблицы по правилу «прямоугольника», не заполняя оценочной строки. Это нужно проделывать до тех пор, пока не будут найдены все базисные переменные. Затем заполнить оценочную строку и определить, является ли найденное решение оптимальным. Если нет, то пересчитать таблицу.
Дата публикования: 2015-03-26; Прочитано: 240 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!