Графический метод решения задач линейного программирования

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Аннотация

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

Традиционно в математическом программировании выделяют следующие основные разделы: Линейное программирование, Нелинейное программирование, Выпуклое программирование, Квадратичное программирование. Мне же интересно линейное программирование. И в моей курсовой я постараюсь рассказать об этом разделе математического программирования, а точнее о графическом методе решения задач линейного программирования.

Содержание

ВВЕДЕНИЕ

1. ПОСТАНОВКА ЗАДАЧИ

1.1 Кратко о линейном программировании

1.2 Основная задача линейного программирования

2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

2.1 Теоретическое введение

2.2 Методика решения задач ЛП графическим методом

3. ПРИМЕНЕНИЕ ГРАФИЧЕСКОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ПРАКТИКЕ

3.1 Экономическая постановка задачи линейного программирования

3.2 Построение математической модели

3.3 Нахождение оптимального решения задачи с помощью линейного метода

ЗАКЛЮЧЕНИЕ

Список литературы

ВВЕДЕНИЕ

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

Термин "Исследование операций" ("Operation Research") заимствован из западной литературы. Сейчас, пожалуй, нельзя точно назвать, ни дату его возникновения, ни автора, да и вряд ли найдется исчерпывающее определение этого понятия.

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

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

В настоящее время в рамках исследования операций сформированы отдельные самостоятельные направления - линейное программирование, выпуклое программирование, теория игр, теория массового обслуживания, и др.

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

Традиционно в математическом программировании выделяют следующие основные разделы: Линейное программирование, Нелинейное программирование, Выпуклое программирование, Квадратичное программирование.

Целью нашего курсового проекта является решение задачи линейного программирования графическим методом.

линейный программирование графический

1. ПОСТАНОВКА ЗАДАЧИ

1.1 Кратко о линейном программировании

Нелинейное программирование [nonlinear programming] -- раздел математического программирования, изучающий методы решения экстремальных задач с нелинейной целевой функцией и (или) областью допустимых решений, определенной нелинейными ограничениями. В экономике это соответствует тому, что результаты (эффективность) возрастают или убывают непропорционально изменению масштабов использования ресурсов (или, что то же самое, масштабов производства): напр., из-за деления издержек производства на предприятиях на переменные и условно-постоянные; из-за насыщения спроса на товары, когда каждую следующую единицу продать труднее, чем предыдущую; из-за влияния экстерналий (см. Внешняя экономия, внешние издержки) и т. д.

В краткой форме задачу Н. п. можно записать так:

F (x) > max при условиях g (x) ? b, x ? 0,

где x -- вектор искомых переменных; F (x) -- целевая функция; g (x) -- функция ограничений (непрерывно дифференцируемая); b -- вектор констант ограничений (выбор знака ? в первом условии здесь произволен, его всегда можно изменить на обратный).

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

Иначе говоря, задача состоит в выборе таких неотрицательных значений переменных, подчиненных системе ограничений в форме неравенств, при которых достигается максимум (или минимум) данной функции. При этом не оговариваются формы ни целевой функции, ни неравенств. Могут быть разные случаи: целевая функция нелинейна, а ограничения линейны; целевая функция линейна, а ограничения (хотя бы одно из них) нелинейны; и целевая функция, и ограничения нелинейны.

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

Напр., задачу для двух переменных (выпуск продукта x и выпуск продукта y) и вогнутой целевой функции (прибыль Р) можно геометрически представить на чертеже (рис. H.4; заштрихована область допустимых решений).

Эта задача реалистично отражает распространенное в экономике явление: рост прибыли с ростом производства до определенного (оптимального) уровня в точке B?, а затем ее снижение (напр., вследствие затоваривания продукцией или исчерпания наиболее эффективных ресурсов).

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

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

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

1.2 Основная задача линейного программирования

Основная задача линейного программирования (ОЗЛП) ставится следующим образом: Имеется ряд переменных x1, x2...xn. Требуется найти такие их неотрицательные значения, которые удовлетворяли бы системе линейных уравнений:

(1)

и, кроме того, обращали бы в минимум линейную целевую функцию (ЦФ)

L=c1x1+c2x2+...+cnxn

Очевидно, случай, когда ЦФ нужно обратить не в минимум, а в максимум, легко сводится к предыдущему, если изменить знак функции и рассмотреть вместо нее функцию

L'=-L=-c1x1-c2x2-...-cnxn

Допустимым решением ОЗЛП называют любую совокупность переменных x₁?0,x₂?0,..,x_n?0, удовлетворяющую уравнениям (1).

Оптимальным решением называют то из допустимых решений, при котором ЦФ обращается в минимум.

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

Рассмотрим задачу линейного программирования с ограничениями-неравенствами, которые имеют вид

(2)

и являются линейно-независимыми. Последнее означает, никакое из них нельзя представить в виде линейной комбинации других. Требуется найти x_i?0, которые удовлетворяют неравенствам и обращают в минимум

Введём уравнения: (3) где y₁,y₂,..,y_m- добавочные переменные, которые также как и x₁,x₂,..,x_n являются неотрицательными.

Таким образом, имеем общую задачу линейного программирования - найти неотрицательные x₁,x₂,..,x_n, y₁,y₂,..,y_m чтобы они удовлетворяли системе уравнений (3) и обращали в минимум

Коэффициенты в формуле (3) перед y_j равны нулю.

2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

2.1 Теоретическое введение

Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Каждое из неравенств задачи линейного программирования (2) определяет на координатной плоскости (x₁0x₂) некоторую полуплоскость (рис.4), а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи (2) ОДР является пустым множеством.

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

a_i1x₁+a_i2x₂=b

можно представить в виде системы двух неравенств (см. рис.4)

ЦФ L(x)=c₁x₁+ c₂x₂ при фиксированном значении L(x)=L определяет на плоскости прямую линию c₁x₁+ c₂x₂=L. Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси 0x₂ (начальная ордината), а угловой коэффициент прямой останется постоянным (см.рис.4). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

Вектор с координатами из коэффициентов ЦФ при x₁ и x₂ перпендикулярен к каждой из линий уровня (см. рис.4). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора .

Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки x*=(x₁*,x₂*). Оптимальной считается точка, через которую проходит линия уровня L_max(L_min), соответствующая наибольшему (наименьшему) значению функции L(x). Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений- единственная точка; задача не имеет решений.



Рисунок 4 Геометрическая интерпретация ограничений и ЦФ задачи.

2.2 Методика решения задач ЛП графическим методом

I В ограничениях задачи (2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

II Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (2). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.

Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

Поскольку x₁ и x₂ должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси 0x₁ и правее оси 0x₁, т.е. в I-м квадранте.

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

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

IV Если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня c₁x₁+ c₂x₂=L (где L - произвольное число, например, кратное c₁ и c₂, т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

V Построить вектор , который начинается в точке (0;0) и заканчивается в точке (c₁, c₂). Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

VI При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ- против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).

VII Определить координаты точки max (min) ЦФ x*=(x₁*,x₂*) и вычислить значение ЦФ L(x*). Для вычисления координат оптимальной точки x* необходимо решить систему уравнений прямых, на пересечении которых находится x*.

3. ПРИМЕНЕНИЕ ГРАФИЧЕСКОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ПРАКТИКЕ.

3.1 Экономическая постановка задачи линейного программирования

Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии - 60 изделий, второй линии - 80 изделий. На радиоприемник первой модели расходуется 15 однотипных элементов электронных схем, на радиоприемник второй модели - 10 таких же элементов. Максимальный суточный запас используемых элементов равен 950 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны 40$ и 20$ соответственно. Определите оптимальные суточные объемы производства первой и второй моделей на основе графического решения задачи.

3.2 Построение математической модели

Переменные задачи

В задаче требуется установить, сколько радиоприемников первой и второй модели надо производить. Поэтому искомыми величинами, а значит, и переменными задачи являются суточные объемы производства каждого типа радиоприемников:

x₁ - суточный объем производства радиоприемников первой модели, [шт/сутки];

x₂ - суточный объем производства радиоприемников второй модели, [шт/сутки];

Целевая функция

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

? их объемы производства, т.е. x₁ и x₂ радиоприемников в сутки;

? прибыль от их реализации- согласно условию, соответственно 40 и 20$.

Таким образом, доход от продажи суточного объема производства радиоприемников первой модели равен 40x₁$ в сутки, а от продажи радиоприемников второй модели- 20x₂$ в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи радиоприемников первой и второй модели:

L(x)=40x₁+20x₂>max [$/сутки]

Ограничения

Возможные объемы производства радиоприемников x₁ и x₂ ограничиваются следующими условиями:

? количество элементов электронных схем, израсходованное в течении суток на производство радиоприемников обоих моделей, не может превышать суточного запаса этих элементов на складе;

? суточный объем первой технологической линии (производство радиоприемников первой модели) не может превышать 60 шт в сутки, второй (производство радиоприемников второй модели) - 80 шт;

? объемы производства радиоприемников не могут быть отрицательными.

Таким образом, все ограничения задачи делятся на 3 группы, обусловленные:

1) расходом элементов электронных схем;

2) суточным объемом технологических линий;

3) неотрицательностью объемов производства.

Запишем эти ограничения в математической форме:

1)Т.к. из условия на радиоприемники первой и второй модели необходимо 15 и 20 элементов соответственно, то данное ограничение имеет вид:

15x₁+10x₂?950 [шт/сутки]

2) Ограничения по суточному объему первой и второй технологических линий имеют вид:

x₁?60,

x₂?80 [шт/сутки]

3)Неотрицательность объемов производства задается как

x₁?0,

x2?0.

Таким образом, математическая модель этой задачи имеет вид

L(x)=40x₁+20x₂>max

3.3 Нахождение оптимального решения задачи с помощью линейного метода

Математическую модель задачи о радиоприёмниках мы нашли на предыдущем шаге:

L(x)=40x₁+20x₂>max

Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис.5).

прямая (1) - точки (0;95) и (63,(3);0), прямая (2) проходит через точку x₁=60 параллельно оси 0x₁, прямая (3) проходит через точку x₂=80 параллельно оси 0x_2.

Рис.5 Графическое решение задачи о производстве радиоприемников.

Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (1), получим 0?950, что является истинным неравенством, поэтому стрелкой обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (1). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис.5). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDE.

Целевую прямую можно построить по уравнению

40x₁+20x₂=1500

Точки пересечения с осями - (0;75) и (37,5;0)

Строим вектор из точки (0;0) в точку (40;20). Точка D- это последняя вершина многоугольника допустимых решений ABCDE, через которую проходит целевая прямая, двигаясь по направлению вектора . Поэтому D- это точка максимума ЦФ. Определим координаты точки D из системы уравнений прямых ограничений (1) и (2)

Получили точку D(60;5) [шт/сутки].

Максимальное значение ЦФ равно L(D)=40*60+20*5=2500[$/сутки].

Таким образом, наилучшим режимом работы предприятия является ежесуточное производство радиоприемников первой модели в количестве 60 штук и радиоприемников второй модели в количестве 5 штук. Доход от продажи составит 2500$ в сутки.

ЗАКЛЮЧЕНИЕ

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

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

Оптимальная прибыль от реализации продукции достигается при следующем суточном производстве радиоприемников: 60 шт радиоприемников первой модели и 5 шт радиоприемников второй модели. При этом прибыль от реализации составит 2500$ в сутки.

СПИСОК ЛИТЕРАТУРЫ

1. АстафуровВ.Г., Колодникова Н. - Компьютерное учебное пособие, раздел “Анализ на чувствительность с помощью двойственной задачи”, Томск-2002.

2. Алесинская Т.В. - Задачи по исследованию операций с решениями.

3. Смородинский С.С., Батин Н.В. - Оптимизация решений на основе методов и моделей математического программирования: Учебное пособие.

4. Кононов В.А. - Исследование операций. Для продвинутых математиков.

Размещено на Allbest.ru