Определение целевой функции симплекс-методом

Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.
Краткое сожержание материала:

Размещено на

Введение

Курсовое проектирование по дисциплине «Математические методы» является неотъемлемой частью подготовки специалистов в среднем профессиональным образованием.

Курсовое проектирование является завершающим этапом в изучении дисциплины «Математические методы», в ходе, которого осуществляется обучение применению полученных знаний и умений при решении комплексных задач, связанных со сферой профессиональной деятельности

Цель курсовой работы:

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

Задачи курсовой работы:

закрепить, углубить и обобщить теоретические знания, полученные по изучаемым дисциплинам, и применить эти знаний к комплексному решению конкретной информационной задачи;

изучить особенности конкретной предметной области, относящиеся к теме курсового проекта (работы);

проанализировать возможные подходы и методы решения с обоснованием выбранного метода;

развить навыки работы со справочной литературой, материалами ГОСТов;

научиться применять современные технические средства для разработки программного продукта;

разработка программной и эксплуатационной документации;

проанализировать полученные результаты работы;



1. Оптимизация целевой функции симплекс-методом

1.1 Симплекс-метод

Симплекс-метод - алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан советским математиком Канторовичем Л.В. в 1937 году.

Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях. Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение

W(x) = c,

где W(x) - максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку - требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

нахождение исходной вершины множества допустимых решений,

последовательный переход от одной вершины к другой, ведущий к оптимизации значения целевой функции.

При этом в некоторых случаях исходное решение очевидно или его определение не требует сложных вычислений, например, когда все ограничения представлены неравенствами вида «меньше или равно» (тогда нулевой вектор совершенно точно является допустимым решением, хотя и, скорее всего, далеко не самым оптимальным). В таких задачах первую фазу симплекс-метода можно вообще не проводить. Симплекс-метод, соответственно, делится на однофазный и двухфазный.

1.2 Алгоритм симплекс-метода

Усиленная постановка задачи

Рассмотрим следующую задачу линейного программирования:

Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z:

(1)

Где, x - переменные из исходного линейного функционала,

xs - новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство,

c - коэффициенты исходного линейного функционала,

Z - переменная, которую необходимо максимизировать.

Полупространства и в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений даёт нам число степеней свободы. Проще говоря, если мы рассматриваем вершину многогранника, то это число рёбер, по которым мы можем продолжать движение. Тогда мы можем присвоить этому числу переменных значение 0 и назвать их «непростыми». Остальные переменные при этом будут вычисляться однозначно и называться «простыми». Полученная точка будет вершиной в пересечении соответствующих непростым переменным гиперплоскостей. Для того, чтобы найти т. н. начальное допустимое решение (вершину, из которой мы начнём движение), присвоим всем изначальным переменным x значение 0 и будем их считать непростыми, а все новые будем считать простыми. При этом начальное допустимое решение вычисляется однозначно:.

Алгоритм

Теперь приведём шаги алгоритма. На каждом шаге мы будем менять множества простых и непростых векторов (двигаться по рёбрам), и матрица будет иметь следующий вид:

(2)

где cB - коэффициенты вектора c соответствующие простым переменным (переменным xs соответствуют 0), B - столбцы АЕ, соответствующие простым переменным. Матрицу, образованную оставшимися столбцами обозначим D. Почему матрица будет иметь такой вид поясним в описании шагов алгоритма.

Первый шаг

Выбираем начальное допустимое значение, как указано выше. На первом шаге B - единичная матрица, так как простыми переменными являются xs. cB - нулевой вектор по тем же причинам.

Второй шаг

Покажем, что в выражении только непростые переменные имеют ненулевой коэффициент. Заметим, что из выражения Ax+xs=b простые переменные однозначно выражаются через непростые, так как число простых переменных равно числу уравнений. Пусть x ' - простые, а x ' ' - непростые переменные на данной итерации. Уравнение Ax+xs=b можно переписать, как Bx '+Dx ' '=b. Умножим его на слева:. +=

Таким образом мы выразили простые переменные через непростые, и в выражении, эквивалентному левой части равенства, все простые переменные имеют единичные коэффициенты. Поэтому, если прибавить к равенству равенство , то в полученном равенстве все простые переменные будут иметь нулевой коэффициент - все простые переменные вида x сократятся, а простые переменные вида xs не войдут в выражение.

Выберем ребро, по которому мы будем перемещаться. Поскольку мы хотим максимизировать Z, то необходимо выбрать переменную, которая будет более всех уменьшать выражение

Для этого выберем переменную, которая имеет наибольший по модулю отрицательный коэффициент. Если таких переменных нет, то есть все коэффициенты этого выражения неотрицательны, то мы пришли в искомую вершину и нашли оптимальное решение. В противном случае начнём увеличивать эту непростую переменную, то есть перемещаться по соответствующему ей ребру. Эту переменную назовём входящей.

Третий шаг

Теперь необходимо понять, какая простая переменная первой обратится в ноль по мере увеличения входящей переменной. Для этого достаточно рассмотреть систему:

При фиксированных значениях непростых переменных система однозначно разрешима относительно простых, поэтому мы можем определить, какая из простых переменных первой достигнет нуля при увеличении входящей. Эту переменную назовем выходящей. Это будет означать, что мы натолкнулись на новую вершину. Теперь входящую и выходящую переменную поменяем местами - входящая «войдёт» в простую, а выходящая из них «выйдет» в непростые. Теперь перепишем матрицу B и вектор cB в соответствии с новыми наборами простых и непростых переменных, после чего вернёмся ко второму шагу.

Поскольку число вершин конечно, то алгоритм однажды закончится. Найденная вершина будет являться оптимальным решением.



2. Использование симплексного метода

Предприятие выпускает скоропортящуюся продукцию, которую сразу можно доставить потребителю (А1 стратегия).

Отправить на склад для хранения (А2 стратегия) или подвергнуть обработке для длит. Хранения (А3 стратегия). Потребитель может приобрести немедленно (В1 стратегия) ,через некоторое время (В2 стратегия) или после длительного периода (В3 стратегия). В случае стратегий А2 и А3 предприятие несет дополнительные затраты на хранение и обработку продукции. Однако, при А2 следует вычесть убытки, если потребитель выберет стратегию В2 или В3 . Определить оптимальные пропорции для применения стратегий А1,А2,А3. Руководствуясь минимаксным критерием, гарантирует средний уровень убытка. Пользуясь минимальным критерием из таблицы.

Таблица 1...