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

Вид материала

Курсовая

Содержание Хочу подчеркнуть, что выделяют особые случаи применения симплекс-метода. Теоретические основы Если задана общая задача ЛП Методы решения задач линейного программирования Направленный перебор

Подобный материал:

• План чтения лекции по учебной дисциплине «Математические методы» Раздел, 120.82kb.
• Темы курсовых работ «Методы оптимизации» Графический метод решения задачи линейного, 11.12kb.
• Рабочая программа по дисциплине Численные методы оптимизации для специальности 220400, 70kb.
• Кафедра «Прикладная математика» Экономические приложения линейного программирования, 27.15kb.
• Рабочая программа По дисциплине «Организация управления международной деятельностью, 223.24kb.
• Ф-рабочая программа по дисциплине утверждено ученый совет факультета математики и информационных, 193.23kb.
• Задачи математического и линейного программирования. Математическая модель задачи использования, 25.82kb.
• Задачи линейного программирования Геометрическая интерпретация задач линейного программирования, 132.4kb.
• Рабочая программа дисциплины математическое моделирование (Математические методы оптимизации), 521.88kb.
• Курс Методы визуального программирования при разработке системного программного обеспечения., 30.14kb.

^

Хочу подчеркнуть, что выделяют особые случаи применения симплекс-метода.

1) Когда прямая (если рассматривается двухмерная задача линейного программирования, а в общем случае гиперплоскость), представляющая целевую функцию параллельна прямой (гиперплоскости), соответствующей одному из неравенств-ограничений (которое в точке оптимума выполняется, как точное равенство) целевая функция принимает одно и тоже оптимальное значение на некотором множестве точек границы области допустимых решений. Эти решения называются альтернативными оптимальными решениями. Наличие альтернативных решений можно определить по оптимальной симплекс-таблице. Если в z-строке оптимальной таблицы есть нулевые коэффициенты небазисных переменных, то есть альтернативные решения.

2) Если в разрешающем столбце симплекс-таблицы все коэффициенты меньше или равны нуль, то нельзя выбрать разрешающую строку, в этом случае решение неограниченно.

3) Если ограничения задачи линейного программирования несовместны (т.е. они не могут выполняться одновременно), то задача не имеет допустимых решений. Такая ситуация не может возникнуть, если все неравенства, составляющие систему ограничений, имеют тип " ≤ " с неотрицательными правыми частями, т.к. в этом случае дополнительные переменные могут составить допустимое решение. Для других типов ограничений используются искусственные переменные. Если задача имеет решение, то в оптимальной таблице в базисе нет искусственных переменных (R_i). Если они там есть, то задача не имеет решений.

Объектами и предметом исследования это курсовой работы являются:

1) Общая формулировка задачи линейного программирования

2) Линейное программирование

3) Методы решения задач линейного программирования

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

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


В качестве метода исследования я выбрал примерное решение задач различными способами линейного программирования. Также это необходимо для того, чтобы показать различия между симплекс-методом и методами простого и направленного перебора.

1. ^ Теоретические основы
   

Общая формулировка задачи линейного программирования


Ряд практических задач сводится к смешанным условиям: часть ограничений - линейные уравнения, другие - линейные неравенства. Такое разнообразие форм записи условий задач затрудняет создание и использование общих методов и вычислительных алгоритмов их решения. Поэтому естественно рассмотреть метод и алгоритм решения основной (стандартной) задачи линейного программирования и способы сведения любой задачи линейного программирования к основной форме, которая состоит в следующем. Задана система m линейных алгебраических уравнений с n неизвестными:


(3.7)


и линейная функция относительно переменных х1, х2, ¼, хn:


(3.8)


Требуется найти такие неотрицательные значения переменных х1, х2, ¼, хn, которые бы удовлетворяли системе линейных уравнений (3.7) и, кроме того, обращали в максимум линейную функцию (3.8).


Заметим, что если по условиям задачи требуется отыскать минимум функции L, записанной в виде (3.8), то задачу можно свести к задаче максимизации функции L¢, связанной с функцией L так:


L¢ = - L = -c1x1 - c2x2 - ¼ - cnxn. (3.9)


Максимум функции (3.9) и минимум функции (3.8) будут достигаться при одном и том же наборе переменных (х1, х2, ¼, хn), удовлетворяющих условиям неотрицательности переменных и уравнениям (3.7), областью определения задачи.


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


х1 ³ 0, х2 ³ 0, ¼ , хn ³ 0, (3.10)


удовлетворяющих уравнениям (3.7).


Оптимальным решением будем называть то из допустимых решений, для которого линейная форма L обращается в максимум (минимум).


Линейное программирование

Двойственная задача

Понятие двойственной задачи ЛП.

Пусть задана каноническая задача ЛП

    (5.1)

Если целевая функция f(x) = cx достигает максимального значения на множестве D, то обоснованным представ­ляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некото­рый m-мерный вектор, то

cx = cx+u(-Ax+b) = (c-uA)x+bu

Предположим, что и можно выбрать таким образом, чтобы иА ≥ с. Тогда при любых х≥0 справедливо неравенство

сх≤bи                          (5.2)

Стремясь получить наилучшую оценку (5.2), мы приходим к формулировке некоторой новой экстремальной задачи, кото­рая в некотором смысле логически сопряжена с задачей (5.1) и называется двойственной. Оговоримся, что приведенные рас­суждения не носят строгого характера и предназначены только для того, чтобы подготовить читателя к приводимому ниже фор­мальному определению двойственной задачи линейного про­граммирования.

Если задана каноническая задача ЛП

    (5.3)

то задача ЛП

       (5.4)

называется двойственной по отношению к ней. Соответственно, задача (D, f) no отношению к  (D*, f*)  назы­вается прямой (или исходной).


Общая схема построения двойственной задачи.

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

^ Если задана общая задача ЛП

    (5.5)50

где D определяется системой уравнений и неравенств



то двойственной по отношению к ней называется общая задача ЛП

  (5.6)

где D* определяется системой уравнений и неравенств



Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

1.  Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.

2.  Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами.

3.  Матрица ограничений задачи А транспонируется.

4.  Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, х_j≥0 или u_i≥0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (а^jи≥с_j или a_ix≤b_i).

5.  Множество номеров ограничений, имеющих форму неравенств в прямой задаче (например, a_ix≤b_i или а^jи≥с_j), определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче (u_i≥0 или х_j≥0).

Из приведенного определения вытекает важное свойство — симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, со­впадает с прямой (исходной) задачей:

((D*)*, (f*)*)≡(D, f),

Тем самым имеет смысл говорить о паре взаимно двой­ственных задач.

В матричной форме пара двойственных общих задач линей­ного программирования может быть кратко записана как:

    (5.3)

и

      (5.7)


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


45Х1+80Х2 → max, 400W1+450W2 → min ,


5Х1+20Х2≤400, 5W1+10W2≥45,


10Х1+15Х2≤450, 20W1+15W2≥80,


Х1≥0, W1≥0,


Х2≥0. W2≥0.


Почему двойственная задача столь важна? Можно доказать, что оптимальные значения целевых функций в исходной и двойственной задачах совпадают (т.е. максимум в исходной задаче совпадает с минимумом в двойственной). При этом оптимальные значения W1 и W2 показывают стоимость материала и труда соответственно, если их оценивать по вкладу в целевую функцию. Чтобы не путать с рыночными ценами этих факторов производства, W1 и W2 называют "объективно обусловленными оценками" сырья и рабочей силы.


^ Методы решения задач линейного программирования

Простой перебор

Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа 2Х1+5Х2≤10, то, очевидно, 0≤Х1≤10/2=5 и 0≤Х2≤10/2 = 5. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.Проведем перебор точек параллелепипеда с шагом 1/10n последовательно при n=2,3,…, вычисляя значения целевой функции и проверяя наличие ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено! (Более строго выражаясь, найдено с точностью до 1/10n .)

^ Направленный перебор

Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - т.н. метод случайного поиска) менять ее координаты на определенную величину ∆, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ∆ ; если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ∆/2 , ∆/4 и т.д.)

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

Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Он был предложен американцем Г. Данцигом в 1951 г.

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