Задачи линейного программирования - Курсовая работа

Главной задачей экономики является «рациональное ведение хозяйства, рациональная деятельность (economizing)», т.е. использование минимального количества ресурсов для достижения определенных целей. Проблема рационального ведения хозяйства может быть рассмотрена с точки зрения метода математической оптимизации.Моделирование экономических ситуаций, математическая интерпретация экономических ситуаций, математический подход к решению тех или иных проблем проводились еще в XIX веке. Математический анализ давал возможность получить общее представление о сложившейся экономической ситуации. В 1939 году Леонид Витальевич Канторович представил публике работу «Математические методы организации и планирования производства», в которой выделил новый класс задач с ограничениями и создал эффективный метод их решения.Линейное программирование (ЛП) - это метод математического моделирования, характеризующийся линейной зависимостью между переменными и целевой функцией. Данный метод реализован высокоэффективными компьютерными алгоритмами, на которых основываются другие алгоритмы для более сложных типов моделей и задач исследования операций, включая целочисленное, нелинейное, стохастическое программирование. Задача линейного программирования - задача выбора таких неотрицательных значений переменных, удовлетворяющих ряду ограничений в форме линейных неравенств, при которых возможен максимум или минимум целевой функции.вектор-строка постоянных коэффициентов целевой функции; В развернутом виде задачи имеют вид: F(x1,x2,…,xn) = c1x1 c2x2 … cnxn при ограничениях Но умножая неравенство на (-1) и представляя равенство двумя неравенствами «» и «», можно получить стандартную форму записи.Если все ограничения задачи линейного программирования (кроме условий неотрицательности переменных вектора ) представлены в виде строгих равенств и столбец свободных членов () неотрицательны, тогда имеем задачу в канонической форме. Задачу, приведенную выше, можно привезти к канонической форме (при условии, что ), прибавив к правой части неравенств вектор-столбец балансовых переменных =(y1,y2,…,ym)T ?0: a11x1 a12x2 … a1nxn y1 b1, a21x1 a22x2 … a2nxn y2 b2, am1x1 am2x2 … amnxn ym bm.Допустимое решение задач ЛП является выпуклым многогранником в Rn (размерность пространства определяется количеством переменных (компонентов) в ) или пустым множеством. Если допустимое множество не является пустым множеством, и целевая функция ограничена сверху или снизу (для задач максимизации и минимизации соответственно), то говорят, что задача линейного программирования имеет оптимальное решение. Некоторая компания Remmy Milks выпускает краску для внутренних и наружных работ из сырья двух типов: A1, A2. Директор, в связи с финансовыми проблемами, поставил два условия: ограничить ежедневный выпуск краски для внутренних работ до 2 т; ежедневное производство краски для внутренних работ не должно превышать более чем на тонну аналогичный показатель производства краски для внешних работ.В общем случае, графическим способом можно решить задачу, в которой неизвестных переменных, ограничений-неравенств и соотношение . Графический способ решения задачи линейного программирования содержит следующие этапы: Построить пространство допустимых решенийТочки, расположенные по одну сторону от прямой удовлетворяют неравенству, а точки другой стороны - нет. Проверить, принадлежит ли та или иная область допустимому полупространству можно, подставляя «тестовую» точку 0(0;0). Все точки, принадлежащие области многогранника, удовлетворяют системе ограничений, и в каждой точке функция принимает какое-то определенное значение. Метод перебора здесь не подходит, так как таких точек фактически бесконечно много, поэтому нужен некий алгоритм, некая процедура нахождения оптимального решения.Исходная задача линейного программирования называется прямой. Если исходная задача является задачей на минимум: при ограничениях Запишем задачу в развернутом виде: Общее между прямой задачи ЛП и ее двойственной является: поиск экстремума функции искомые переменные неотрицательны и удовлетворяют системе ограничений используются одни и те же параметры: матрица А, вектор-столбец , вектор-строка . Хотя с другой стороны, в исходной задаче искомых n переменных - компоненты вектор-столбца , а в двойственной задаче искомых m переменных, которые являются компонентами вектора-строки прямой задаче ищется минимум функции, а в двойственной - максимум; знаки в системе ограничений различны; коэффициенты целевой функции одной задачи являются константами ограничений другой.

Оглавление

Введение

1. История

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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