Автор работы: Пользователь скрыл имя, 25 Сентября 2013 в 23:17, курсовая работа
На основе поставленной цели были определены задачи:
o изучить симплексный метод решения задач линейного программирования;
o рассмотреть решение симплексным методом в MS Excel;
o разработать свое приложение для решения задачи симплексным методом.
Переход к нехудшему опорному плану. Пусть решается ЗЛП с системой ограничений в предпочтительном виде
,
Ее начальный опорный план . Значение целевой функции .
Рассмотрим задачу на максимум. Если все , то опорный план оптимален. Пусть существует , для которого . Вектор-столбец , для которого , называется разрешающим, соответствующая переменная – перспективной. Попытаемся, не изменяя нулевых значений свободных переменных , кроме , увеличить значение целевой функции Z за счет увеличения переменной . Однако увеличивать следует осторожно, так как выбор влияет на значения , которые должны быть неотрицательными. Из системы ограничений (34) в силу того, что
имеем
При значительном увеличении может случаться, что для некоторого i соответствующее станет меньше , и, следовательно, получим , что недопустимо. В случае, если , такого нарушения не произойдет.
Итак, не ограничивая общности, будем считать, что, например, первые k коэффициентов . Тогда можно увеличить до тех пор, пока , откуда имеем:
Найдем среди отношений наименьшее. Назовем его наименьшим симплексным отношением и обозначим буквой , то есть
Если это условие выполняется при нескольких i, то в качестве можно выбрать любое. Строку называют разрешающей, элемент же – разрешающим (или ключевым). Переменная , присутствующая в базисе, является неперспективной, ее следует вывести из базиса.
Полагая из равенства (34) находим:
Новый базис будет состоять из переменных , а соответствующий ему опорный план примет вид
В результате преобразований получен новый опорный план х1, в котором переменная заменена на , причем . Но , следовательно, Новый план х1 не хуже начального х0.
Симплексные преобразования. Чтобы завершить шаг преобразований, ведущих к новому опорному плану в новом базисе, выразим новую базисную переменную из уравнения с номером системы (32) через свободные переменные :
. (35)
Подставим выражение (35) в остальные ограничения системы (32):
Аналогично, подставив выражение из равенства (35) в целевую функцию (31), получим
(37)
Преобразование ЗЛП к новому базису назовем симплексным преобразованием. Из равенств (35) – (37) вытекают правила для перехода к следующей симплексной таблице.
(38)
рис. 1
Для этого в исходной таблице выделяют прямоугольник, вершинами которого служат нужные для вычисления элементы (см. рис. 1). Диагональ, содержащую разрешающий и искомый элементы новой таблицы, называют главной, а другую побочной. Чтобы получить элемент новой симплексной таблицы, нужно из произведения угловых элементов главной диагонали вычесть произведение угловых элементов побочной диагонали и полученное число разделить на разрешающий элемент, выделенный рамкой. Это правило прямоугольника.
(39)
Шаг симплексного метода, позволяющий перейти от одного спорного плана к другому нехудшему, называется итерацией. Таким образом, симплексный метод является итеративным методом последовательного улучшения плана. Из второго соотношения (39) следует, что значения целевой функции на двух последовательных итерациях связаны равенством
то есть
где , – значения функции цели на k-й и (k + 1)-й итерациях; – оценка свободной переменной , вводимой в базис; – симплексное отношение k-й итерации.
В результате ввода свободной переменной в базис изменение целевой функции Z, как это следует из равенства (40), составит
В очередном опорном плане новая базисная переменная примет значение, равное . Ее прежнее значение (как свободной переменной) равно нулю. Поэтому изменение переменной в результате введения ее в новом базисе равно . В таком случае можно переписать в виде , откуда
Если, в частности, , то .
Таким образом, оценка свободной переменной характеризирует изменение целевой функции Z, приходящееся на каждую единицу изменения значения переменной . Этим и объясняется термин «оценка».
Альтернативный оптимум (признак бесконечности множества оптимальных планов). Как определить, решая ЗЛП симплексным методом, единственный ли она имеет оптимальный план или бесконечное множество? На этот вопрос отвечает следующая теорема.
Теорема 9. Если в индексной строке последней симплексной таблицы, содержащей оптимальный план, имеется хотя бы одна нулевая оценка, соответствующая свободной переменной, то ЗЛП имеет бесконечное множество оптимальных планов.
Следствие. Если в индексной строке симплексной таблицы, содержащей оптимальный план, все оценки свободных переменных положительны, то найденный оптимальный план единственный.
Признак неограниченности целевой функции.
Теорема 10. Если в индексной строке симплексной таблицы ЗЛП на максимум содержится отрицательная оценка , а в соответствующем столбце переменной нет ни одного положительного элемента, то целевая функция на множестве допустимых планов задачи не ограничена сверху.
Теорема 11. Если в индексной строке симплексной таблицы ЗЛП на минимум содержится положительная оценка , а в столбце переменной нет ни одного положительного элемента, то на множестве допустимых планов целевая функция не ограничена снизу.
С экономической точки зрения неограниченность целевой функции ЗЛП свидетельствует только об одном: разработанная модель недостаточно точна. Бессмысленно говорить, например, о бесконечной прибыли. Типичными ошибками, приводящими к построению моделей такого рода, являются: 1) неполный учет ограничений, которые являются существенными в данной задаче; 2) небрежные оценки параметров, фигурирующий в ограничениях.
Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание. Очевидно, базисный план ЗЛП, записанной в предпочтительном виде, невырожден, когда свободные члены всех уравнений положительны, и вырожден, если среди них имеются нули. Каноническую ЗЛП называют невырожденной, если все ее опорные планы невырождены. Если среди опорных планов есть хотя бы один вырожденный, то задачу называют вырожденной.
Пусть ЗЛП решается на максимум. На двух последовательных итерациях значения целевой функции связаны соотношением (40):
где ; ; .
Если задача невырожденная, то для любого шага , . Отсюда , то есть значение целевой функции будет не хуже прежнего (монотонно возрастает). Аналогично, если задача решается на минимум, то, поскольку , на любом шаге значения целевой функции на двух последовательных итерациях будут связаны неравенством , то есть целевая функция монотонно убывает. В этом и состоит монотонность симплексного метода.
Конечность алгоритма следует из конечного числа опорных планов ЗЛП (их не больше ).
Если ЗЛП вырожденная, то возможны случаи, когда . В этом случае значение целевой функции не улучшится. Предположим, что процесс продолжается без остановки, порождая бесконечную последовательность опорных планов. Вследствие конечности множества опорных планов в этой последовательности некоторые планы должны повторяться. В силу равенства для них целевой функции они должны лежать в одной гиперплоскости и быть вершинами выпуклого многогранника. Поэтому должна встретиться цепочка (цикл) , в которой начальный и конечный планы совпадают, причем в силу монотонности метода
Процесс продолжится неограниченно, если несколько последовательных вырождений приведут к образованию цикла. Такое явление называется зацикливание. Зацикливание возможно только для вырожденных задач. Теория и практика показывает, что зацикливание возникает при весьма маловероятным сочетанием условий. Известно лишь несколько специально разработанных (очень сложных) примеров, в процессе решения которых возникает зацикливание. Точный алгоритм вывода из цикла достаточно сложен. В простейшем случае при появлении цикла следует изменить последовательность вычислений путем изменения выбора разрешающего столбца. Другое правило рекомендует изменить выбор разрешающей строки. Если в процессе симплексных преобразований появляется несколько минимальных симплексных отношений, то в качестве разрешающей выбирают ту строку, для которой будет наименьшим отношение элементов первого столбца к разрешающему. Если при этом снова оказывается несколько минимальных отношений, то составляются отношения элементов второго столбца к разрешающему, и так до тех пор, пока разрешающая строка не определится однозначно.
Мощным средством анализа данных MS Excel является надстройка Solver (Поиск решения). С ее помощью можно определить, при каких значениях указанных влияющих ячеек формула в целевой ячейке принимает нужное значение (минимальное, максимальное или равное какой-либо величине). Для процедуры поиска решения можно задать ограничения, причем не обязательно, чтобы при этом использовались те же влияющие ячейки. Для расчета заданного значения применяются различные математические методы поиска. Вы можете установить режим, в котором полученные значения переменных автоматически заносятся в таблицу. Кроме того, результаты работы программы могут быть оформлены в виде отчета.
Описание. Программа «Поиск решений» (в оригинале Excel Solver) – дополнительная надстройка табличного процессора MS Excel, которая предназначена для решения определенных систем уравнений, линейных и нелинейных задач оптимизации, используется с 1991 года.
Размер задачи, которую можно решить с помощью базовой версии этой программы, ограничивается такими предельными показателями:
количество неизвестных (decision variable) – 200;
количество формульных ограничений (explicit constraint) на неизвестные – 100;
количество предельных условий (simple constraint) на неизвестные – 400.
Разработчик программы Solver, компания Frontline System, уже давно специализируется на разработке мощных и удобных способов оптимизации, встроенных в среду популярных табличных процессоров разнообразных фирм-производителей (MS Excel Solver, Adobe Quattro Pro, Lotus 1-2-3).
Высокая эффективность их применения объясняется интеграцией программы оптимизации и табличного бизнес-документа. Благодаря мировой популярности табличного процессора MS Excel встроенная в его среду программа Solver является наиболее распространенным инструментом для поиска оптимальных решений в сфере современного бизнеса.
Процедура поиска решения. В меню «Сервис» в разделе «Надстройки» необходимо активизировать функцию «Поиск решения».
Создайте таблицу с формулами, которые устанавливают связи между ячейками.
Выделите целевую ячейку, которая должна принять необходимое значение, и выберите команду «Поиск решения». Поле Set Target Cell (Установить целевую ячейку) открывшегося диалогового окна надстройки Solver (Поиск решения) будет содержать адрес целевой ячейки.
Установите переключатели Equal To (Равной), задающие значение целевой ячейки, —Мах (максимальному значению), Min (минимальному значению) или Value of (значению). В последнем случае введите значение в поле справа.
Укажите в поле By Changing Cells (Изменяя ячейки), в каких ячейках программа должна изменять значения в поисках оптимального результата.
Создайте ограничения в списке Subject to the Constraints (Ограничения). Для этого щелкните на кнопке Add (Добавить) и в диалоговом окне Add Constraint (Добавление ограничения) определите ограничение.
Рис.1 Диалоговое окно надстройки «Поиск решения»
Щелкните на кнопке на кнопке Options (Параметры), и в появившемся окне установите переключатель Неотрицательные значения (если переменные должны быть позитивными числами), Линейная модель (если задача, которую вы решаете, относится к линейным моделям).