Задачи линейного программирования

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

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

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования

«Финансовый университет при Правительстве Российской Федерации»

Кафедра «Прикладная математика»

Курсовая работа

По дисциплине «Исследование операций»

Задачи линейного программирования

Выполнил:

Студент гр. ПМ 1-1

Москва 2013



Оглавление

Введение

1. История

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

3. Стандартная форма записи задачи ЛП

4. Каноническая форма ЗЛП

5. Свойства задач линейного программирования

6. Графический способ

7. Двойственные задачи

8. Особенности двойственных задач

9. Объективно обусловленные оценки и их смысл

10. Экономическая интерпретация переменных двойственной задачи

11. Экономическая интерпретация ограничений двойственной задачи

12. Классическая задача потребления

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

14. Задача о раскрое материалов

Заключение

Список используемой литературы

Введение

Главной задачей экономики является «рациональное ведение хозяйства, рациональная деятельность (economizing)» М. Интрилигатор. Математические методы оптимизации и экономическая теория., т.е. использование минимального количества ресурсов для достижения определенных целей. Вследствие ограниченности ресурсов необходимо выбирать один из возможных вариантов их использования.

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

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

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

Цель курсовой - определить смысл линейного программирования и возможности применения в экономике.



1. История

двойственный линейный программирование экономика

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

Первым толчком в создании и исследовании математических моделей послужило создание в 1920 годы межотраслевого баланса.

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

А в 1949 году математик Джордж Бернард разработал довольно-таки эффективный способ решения задач ЛП - симплекс-метод.

Кстати, термин «программирование» в данном случае нужно понимать как «планирование» (от английского слова «programming»).

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

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

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

Задача ЛП включает три основных элемента:

Переменные, которые следует определить;

Целевая функция, подлежащая оптимизации;

Ограничения, которым должны удовлетворять переменные.

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

3. Стандартная форма записи задачи ЛП

F() = >max

при условии, что

A,

0,

где

- есть вектор-столбец переменных (х₁, x₂, …, x_n)^T;

- вектор-строка постоянных коэффициентов целевой функции;

- скалярное произведение векторов;

A - матрица констант (mn);

- вектор-столбец свободных членов с размерностью (m1).

В развернутом виде задачи имеют вид:

F(x₁,x₂,…,x_n) = c₁x₁+c₂x₂+…+c_nx_n

при ограничениях

В общем случае вместо знака «» могут быть другие знаки ограничений: «» или «». Но умножая неравенство на (-1) и представляя равенство двумя неравенствами «» и «», можно получить стандартную форму записи. Если взять функцию F() с противоположным знаком, то можно получить задачу на минимум.

В процессе решения необходимо найти такой вектор *, чтобы:

Удовлетворял ограничениям (принадлежал множеству допустимых значений);

В точке * целевая функция принимала свое наибольшее (наименьшее) значение.

4. Каноническая форма ЗЛП

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

Задачу, приведенную выше, можно привезти к канонической форме (при условии, что ), прибавив к правой части неравенств вектор-столбец балансовых переменных =(y₁,y₂,…,y_m)^T ?0:

a₁₁x₁+a₁₂x₂+…+a_1nx_n+y₁ b₁,

a₂₁x₁+a₂₂x₂+…+a_2nx_n+y₂ b₂,

a_m1x₁+a_m2x₂+…+a_mnx_n+y_m b_m.

Если в неравенстве стоит знак ?, то следует вычитать из правой части i-ого неравенства i-ый компонент вектора :

a_i1x₁+a_i2x₂+…+a_inx_n-y_i b_i

Если какой-либо элемент вектора отрицателен, то можно это неравенство умножить на (-1) и прибавить/вычесть соответствующий элемент из вектора .

Замечание.

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

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

Если какая-либо независимая переменная может принимать только целочисленное значение, то эта задача целочисленного линейного программирования.



5. Свойства задач линейного программирования

Допустимое решение задач ЛП является выпуклым многогранником в Rⁿ (размерность пространства определяется количеством переменных (компонентов) в ) или пустым множеством. Многогранник образуется вследствие пересечений полупространств, описываемых ограничениями-неравенствами. Он замкнут, но может быть либо ограничен, либо нет.

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

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

Пример Пример взят из книги Таха Х.М. Введение в исследование операций..

Некоторая компания Remmy Milks выпускает краску для внутренних и наружных работ из сырья двух типов: A1, A2. В таблице ниже представлены основные данные задачи.

	Расход сырья (в тоннах) на тонну краски	Максимально возможный ежедневный расход сырья
	для внутренних работ	для наружных работ
Сырье А1	4	6	24
Сырье А2	2	1	6
Доход (в $1000) на тонну краски	4	5



Директор, в связи с финансовыми проблемами, поставил два условия:

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

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

Компания хочет определить оптимальное соотношение между типами выпускаемой продукции для максимизации прибыли.

Первый шаг - определение переменных. Затем построение ограничений и целевой функции.

В нашей рассматриваемой задаче нужно определить ежедневные объемы производства краски для двух видов работ: наружной и внутренней.

Пусть

х₁ - ежедневный объем производства краски для наружных работ;

х₂ - ежедневный объем производства краски для внутренних работ.

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

F(x₁;x₂) = 5x₁ + 4x₂

Из таблицы найдем ограничения:

6х₁+4х₂?24

х₁+2х₂?6

Условия директора:

-х₁+х₂?1

х₂?2



Конечно, краска в минусе не существует:

х₁?0

х₂?0

По условию задачи нам нужно максимизировать функцию. Найти максимум можно несколькими методами:

Графическим способом;

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

Разновидностями симплекс-метода.

Вспомним один из них.

Графический способ

Решение ЗЛП графическим способом является наиболее наглядным примером при решении задач линейного программирования.

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

Графический способ решения задачи линейного программирования содержит следующие этапы:

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

Найти оптимальное решение (комбинацию оптимальных решений) среди всех точек пространства.

Так как вектор состоит из двух компонентов (х₁ и х₂), следовательно, будем рассматривать многогранник в двумерном пространстве.

Удобней всего неравенства ограничений рассматривать в отрезках:



6. Графический способ

Рисунок 1



Как видно, каждое неравенство делит плоскость на два полупространства. Точки, расположенные по одну сторону от прямой удовлетворяют неравенству, а точки другой стороны - нет. Проверить, принадлежит ли та или иная область допустимому полупространству можно, подставляя «тестовую» точку 0(0;0). Таким образом, был построен многогранник ADBCO.

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

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

На рисунке видно, что максимум достигается в точке В, на пересечении двух прямых:

Решая данную систему, находим:



7. Двойственные задачи

Исходная задача линейного программирования называется прямой. Каждой задаче линейного программирования можно составить двойственную к ней. Если исходная задача является задачей на минимум:

при ограничениях

,

то двойственная к ней будет

при ограничениях

,

где вектор-строка .

Запишем задачу в развернутом виде:



Общее между прямой задачи ЛП и её двойственной является:

поиск экстремума функции

искомые переменные неотрицательны и удовлетворяют системе ограничений

используются одни и те же параметры: матрица А, вектор-столбец , вектор-строка .

Хотя с другой стороны, в исходной задаче искомых n переменных - компоненты вектор-столбца , а в двойственной задаче искомых m переменных, которые являются компонентами вектора-строки прямой задаче ищется минимум функции, а в двойственной - максимум; знаки в системе ограничений различны; коэффициенты целевой функции одной задачи являются константами ограничений другой.

Оговорим некоторые правила для преобразования исходной задачи к двойственной:

Нужно привезти прямую задачу к стандартной форме;

Матрица для двойственной задачи является транспонированная матрица исходной;

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

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

Новые переменные должны быть неотрицательными

Пример Пример взят из книги Кремера Н.Ш. Исследование операций в экономике..

Получить двойственную задачу к исходной задаче:

Запишем в векторном виде:

Тогда двойственная к ней задача будет

А в векторном виде:

8. Особенности двойственных задач

Первая теорема двойственности:

Если какая-либо из задач (исходная или двойственная) имеет оптимальное решение, то и другая тоже, причем

Если линейная функция одной из задач неограничена, то ограничения другой задачи несовместны

Вторая теорема двойственности:

Чтобы допустимые решения и являются оптимальными решениями для соответствующих задач необходимо и достаточно

Третья теорема двойственности Теорема из книги Кремера Н.Ш. Исследование операций в экономике.

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

Если исходная задача моделирует максимизацию дохода при ограниченных ресурсах, то двойственная к ней при тех же предпосылках моделирует минимизацию затрат при фиксированном уровне дохода

Двойственная задача к двойственной будет исходная задача.

Экономическая интерпретация: предприятию безразлично, выпускать ли продукцию по оптимальному плану и получить максимальную выручку или продавать ресурсы по оптимальным ценам и возместить ей минимальные затраты на ресурсы.

9. Объективно обусловленные оценки и их смысл

Теорема. Теорема из книги Кремера Н.Ш. Исследование операций в экономике.

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

То есть для любых и , если , то ; если , то ; если , то , и аналогично, если , то .

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

Для того, чтобы понять смысл этих оценок просмотрим две задачи:

I при ограничениях	при ограничениях



Задача I об использовании ресурсов, то есть о том, как надо распределить имеющиеся у нас в распоряжении четыре вида ограниченных ресурса S₁, S₂, S₃, S₄, максимально рационально использовать, чтобы минимизировать расходы при производстве двух изделий P₁, P₂ и максимизировать продажи этих изделий.

Введем переменные b₁, b₂, b₃, b₄, которые означают количество ресурсов каждого вида соответственно, и переменные c₁, c₂, равные ценам, по которым реализуют товары P₁, P_2.

В данной задаче переменные равны:

Для решения задач необходимо привести к канонической форме. Прибавим балансовые переменные x₃, x_4, x₅, x₆ в исходную задачу и переменные y₅, y₆. Из полученных уравнений выразим балансовые, тогда в прямой задаче балансовые переменные равны разности между запасами b_i ресурсов S₁, S₂, S₃, S₄ и их потреблением, имеют смысл остатков ресурсов, аналогично в двойственной задаче II балансовые переменные равны разности между затратами на ресурсы для производства из них единицы продукции и ценами c_j продукции P_1, P₂, имеют смысл превышения затрат над ценой.



Насколько видно из таблицы, ресурсы S₁, S₂ полностью использованы и соответствующие им двойственные переменные (оптимальные оценки) ненулевые . Ресурсы S₃, S₄ не полностью израсходованы и оптимальные оценки соответственно равны .

Таким образом, объективно обусловленные оценки ресурсов (оптимальные оценки) определяют степень дефицитности ресурсов: по оптимальному плану производства дефицитны (то есть полностью используемые) ресурсы получают ненулевые оценки, а недефицитные - нулевые оценки. Определение из книги Кремера Н. Ш. Исследование операций в экономике.

Согласно оптимальному решению прямой задачи, следует выпускать продукцию соответственно . Превышение затрат над ценой реализации равны нулю. Если предположить, что, например, при изготовлении продукции P₂ затраты на ресурсы были бы больше нуля (затраты не могут быть отрицательными, иначе они бы выступали как источник дохода), т.е. , то на основании теоремы, приведенной выше, переменная , что значит по оптимальному плану продукцию P₂ производить не следует.

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

Из третьей теоремы двойственных задач следует, что объективно обусловленные оценки ресурсов (оптимальные оценки) показывают, на сколько денежных единиц изменится максимальная прибыль (выручка) от реализации продукции при изменении запаса соответствующего ресурса на одну единицу. Определение из книги Кремера Н. Ш. Исследование операций в экономике



10. Экономическая интерпретация переменных двойственной задачи

Пока оптимальное решение не достигнуто, целевые функции не будут равны между собой. В общем виде можно записать так:

Или

Строгое равенство достигается тогда, когда достигнуто оптимальное решение.

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

Доход (у.е.)=.

Это означает, что переменная y_j представляет собой стоимость единицы ресурса j. Такие переменные были упомянуты ранее как объективно обусловленные оценки.

Равенство можно интерпретировать следующим образом:

Доход < Общая стоимость ресурсов



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

Если рассматривать данную модель более обще, то на «вход» этой системы поступают потребляемые ресурсы, а на «выход» - получаемый доход. Система находится в нестабильном состоянии, пока «вход» превышает «выход». Устойчивое состояние системы характеризуется равенством «входа» и «выхода». Система приведена из книги Таха Х.М. Введение в исследование операций.

11. Экономическая интерпретация ограничений двойственной задачи

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

Данное условие утверждает, что решение задачи, например, с 50-ю переменными и с 100 ограничений, то предпочтительнее решать двойственную ей задачу с 100 переменных и с 50 ограничениями.

Согласно этому утверждению на любом шаге решения задачи справедливо равенство:



Коэффициент при x_j в z-строке =

Для того, чтобы нагляднее продемонстрировать экономический смысл, воспользуемся методом размерности для всех входящих величин. Коэффициент c_j - доход (в у.е.) на единицу «выхода» j-ого вида экономической деятельности. Для согласования размерности величина также должна иметь размерность у.е./единица. Так как c_j представляет доход, то сумма соответствует затратам (или издержкам). Коэффициент равен количеству ресурса i, используемого на поддержание j-ого вида деятельности. Переменная y_i называется вменяемые издержки (вменяемая стоимость) единицы ресурса i. То есть величина соответствует суммарной стоимости всех ресурсов, необходимых для производства единицы продукции j-ого вида деятельности.

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

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

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

12. Классическая задача потребления Пример взят из книги Кремера Н.Ш. Исследование операций в экономике..

Пусть есть n видов товаров и услуг (благ), количества которых (в натуральных единицах) x₁, x₂, …, x_n по ценам p₁,p₂, …, p_n за единицу соответственно. Общая стоимость этих товаров и услуг

Уровень потребления Z выражается некоторой функцией

Z = F() = F(x₁, x₂, …, x_n)

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



Z = F(x₁, x₂, …, x_n) > max

x_i?0 (i =

Решения, зависящие от бюджета M и цен p₁,p₂, …, p_n, называются функциями спроса.

13. Задача об использовании мощностей (задача о загрузке оборудования) Пример взят из книги Кремера Н.Ш. Исследование операций в экономике.

Мануфактура создала план для производства продукции по времени и номенклатуре: необходимо за время T выпустить n₁, n₂, … n_k единиц продукции P₁, P₂ и P_k. Продукция производится на станках S₁, S₂, … S_m. Для каждого станка известны производительность (то есть число единиц продукции P_j, которое можно произвести на станке S_j) и затраты b_ij на изготовление продукции P_j на станке S_j за единицу времени.

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

Составим математическую модель.

Обозначим x_ij - время, в течение которого станок S_i будет занят изготовлением продукции P_j .

Так как время работы каждого станка ограничено и не превышает T, то справедливы неравенства:



Для выполнения плана выпуска по номенклатуре необходимо, чтобы выполнялись следующие равенства:

Кроме того, время не может быть отрицательным:

Затраты на производство всей продукции выразятся функцией

14. Задача о раскрое материалов Пример взят из книги Кремера Н.Ш. Исследование операций в экономике.

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

Нужно найти план раскроя, обеспечивающий максимальное число комплектов.

Обозначим x_i - число единиц материала, раскраиваемых i-м способом, и x - число изготавливаемых комплектов изделий.

Так как общее количество материала равно сумме его единиц, раскраиваемых различными способами, то

Требование комплектности выразится уравнениями

Последнее ограничение:

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



Заключение

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

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

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

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

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



Список используемой литературы

1. Интрилигатор М. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002. Гл. 5.

2. Таха Х.М. Введение в исследование операций. М.: Вильямс, 2005. Гл. 2-4.

3. Исследование операций в экономике: Учебное пособие для вузов Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2004. Гл. 1-6.

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

...