Задача линейного программирования (стр. 1 из 3)
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ФГОУ ПО “ПСКОВСКИЙ КОЛЛЕДЖ СТРОИТЕЛЬСТВА И ЭКОНОМИКИ”
Предмет “Математические методы”
Задача линейного программирования
Курсовая работа
Студента группы 315-ПО
Андреева Дмитрия Александровича
Руководитель курсовой работы
Васильева Наталья Анатольевна
Псков 2009 г.
Содержание
Введение
Глава Ι Линейное программирование
§ 1 Общая постановка задачи линейного программирования
§ 2 Математическая модель задачи линейного программирования
§ 3 Каноническая форма задачи линейного программирования
Глава ΙΙ Решение задачи симплексным методом
§ 1 Постановка задачи
§ 2 Составление математической модели задачи
§ 3 Алгоритмы решения задачи симплексным методом
§ 4 Построение начального опорного решения методом Гаусса
§ 5 Решение задачи
§ 6 Вывод
Заключение
Литература
Введение
В настоящее время множество задач планирования и управления в отраслях народного хозяйства, а также большой объём частных прикладных задач решаются методами математического программирования. Наиболее развитыми в области решения оптимизационных задач являются методы линейного программирования. Эти методы позволяют описать с достаточной точностью широкого круга задач коммерческой деятельности, таких, как планирование товарооборота; размещение розничной торговой сети города; планирование товароснабжения города, района; прикрепление торговых предприятий к поставщикам; организация рациональных перевозок товаров; распределение работников торговли должностям; организация рациональных закупок продуктов питания; распределение ресурсов; планирование капиталовложений; оптимизация межотраслевых связей; замена торгового оборудования; определение оптимального ассортимента товаров в условиях ограниченной площади; установление рационального режима работы.
В задачах линейного программирования критерий эффективности и функции в системе ограничений линейны.
Если содержательный смысл требует получения решения в целых числах, то такая задача является задачей целочисленного программирования.
Если в задаче математического программирования имеется переменная времени, а критерий эффективности выражается через уравнения, описывающие течение операций во времени, то такая задача является задачей динамического программирования.
Во многих экономических моделях зависимости между постоянными и переменными факторами можно считать линейными.
Использование методов математического программирования в коммерческой деятельности связано со сбором необходимой информации коммерсантом, экономистом, финансистом, затем постановкой задачи вместе с математикой. Поскольку методы математического программирования уже реализованы на компьютере в виде пакета стандартных программ, то доступ к ним обычно прост, автоматизирован и не составляет особых трудностей.
Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.
Глава Ι Линейное программирование
§ 1 Общая постановка задачи линейного программирования
Линейное программирование – это направление математического программирование изучающая методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейной целевой функцией. Для решения задач линейного программирования составляется математическая модель задачи и выбирается метод решения.
Постановка задачи коммерческой деятельности может быть представлена в виде математической модели линейного программирования, если целевая функция может быть представлена в виде линейной формы, а связь с ограниченными ресурсами описать посредством линейных уравнений или неравенств. Кроме того, вводится дополнительное ограничение – значения переменных должны быть неотрицательны, поскольку они представляют такие величины, как товарооборот, время работы, затраты и другие экономические показатели.
Геометрическая интерпретация экономических задач даёт возможность наглядно представить, их структуру, выявить особенности и открывает пути исследования более сложных свойств. Задача линейного программирования с двумя переменными всегда можно решить графически. Однако уже в трёхмерном пространстве такое решение усложняется, а в пространствах, размерность которых более трёх, графическое решение, вообще говоря, невозможно. Случай двух переменных не имеет особого практического значения, однако его рассмотрение проясняет свойства задач линейного программирования, приводит к идее её решения, делает геометрически наглядными способы решения и пути их практической реализации.
§ 2 Математическая модель задачи линейного программирования
Перед решением задачи составляем её математическую модель.
Математическая модель – это совокупность соотношений состоящие из линейной целевой функции и линейных ограничений на переменную.
Принцип составления математической модели.
1. Выбирают переменные задачи.
Переменными задачи называются величины
которые полностью характеризуют экономический процесс, описанный в задачи. Обычно записываются в виде вектора X = ( 
) Причём 
)2. Составляют систему ограничения задачи.
Система ограничений – это совокупность уравнений и неравенств, которым удовлетворяют переменные задачи и которая следует из ограниченности экономических условий задачи.
В общем виде система записывается в виде
3. Задают целевую функцию.
Целевая функция – это функция Z(X) которая характеризует качество выполнения задачи, экстремум которой надо найти. В общем виде целевая функция записывается Z(X) =
(max, min)т.о. математическая модель имеет вид найти переменные задачи
удовлетворяющие системе ограничений:
и условию неотрицательности
0 (j = 
), которая обеспечивает экстремум целевой функции Z(Y) = 
Допустимым решением задачи линейного программирования называется любой набор значений переменных удовлетворяющий системе ограничений и условной неотрицательности.
Множество допустимых решений образует область допустимых решений задачи (ОДР).
Оптимальным решением называется допустимое решение задачи, при котором целевая функция достигает экстремума.
§ 3 Каноническая форма задачи линейного программирования
Математическая модель задачи должна иметь каноническую форму.
Если система ограничения состоит только из уравнения и все переменные удовлетворяют условию неотрицательности, то задача имеет каноническую форму.
Если в системе есть хотя бы одно неравенства или какая–либо переменная неограниченна условию неотрицательности, то задача имеет стандартную форму. Чтобы привести задачу к каноническому виду надо:
перейти от неравенств к уравнению следующим образом: в левую часть неравенств вводим дополнительную переменную с коэффициентом (+1) для неравенства (
) и (-1) для неравенства ( ) дополнительные переменные не наложены целевые неотрицательности, то её заменяют разностью двух неотрицательных переменных, то есть: 
= 
– 
( 
Общий вид канонической формы:
Глава ΙΙ Решение задачи симплексным методом
Симплексный метод – это метод последовательного улучшения плана (решения), наиболее эффективный и применяется для решения любой задачи линейного программирования.
Название метода от латинского simplecx – простой т.к. из начального область допустимых решений задачи имела простейший вид. Идеи метода предложил российский математик Контарович Л.В. в 1939 году и затем эту идею развил и разработал Дж. Данциг в 1949 году.
Симплексный метод позволяет за конечное число шагов либо найти оптимальное решение либо доказать что его нет.
§ 1 Постановка задачи
На предприятии в процессе производства используется 3 вида станков Ι, ІΙ, ІΙІ. При этом расходуется сырьё, трудовые ресурсы, и учитываются накладные расходы.