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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ФГОУ ПО “ПСКОВСКИЙ КОЛЛЕДЖ СТРОИТЕЛЬСТВА И ЭКОНОМИКИ”

Предмет “Математические методы”

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

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

Студента группы 315-ПО

Андреева Дмитрия Александровича

Руководитель курсовой работы

Васильева Наталья Анатольевна

Псков 2009 г.

Содержание

Введение

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

§ 1 Общая постановка задачи линейного программирования

§ 2 Математическая модель задачи линейного программирования

§ 3 Каноническая форма задачи линейного программирования

Глава ΙΙ Решение задачи симплексным методом

§ 1 Постановка задачи

§ 2 Составление математической модели задачи

§ 3 Алгоритмы решения задачи симплексным методом

§ 4 Построение начального опорного решения методом Гаусса

§ 5 Решение задачи

§ 6 Вывод

Заключение

Литература

Введение

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

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

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

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

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

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

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

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

§ 1 Общая постановка задачи линейного программирования

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

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

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

§ 2 Математическая модель задачи линейного программирования

Перед решением задачи составляем её математическую модель.

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

Принцип составления математической модели.

1. Выбирают переменные задачи.

Переменными задачи называются величины которые полностью характеризуют экономический процесс, описанный в задачи. Обычно записываются в виде вектора X = ( ) Причём )

1. Составляют систему ограничения задачи.

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

В общем виде система записывается в виде

1. Задают целевую функцию.

Целевая функция – это функция Z(X) которая характеризует качество выполнения задачи, экстремум которой надо найти. В общем виде целевая функция записывается Z(X) = (max, min)

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

и условию неотрицательности 0 (j = ), которая обеспечивает экстремум целевой функции Z(Y) =

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

Множество допустимых решений образует область допустимых решений задачи (ОДР).

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

§ 3 Каноническая форма задачи линейного программирования

Математическая модель задачи должна иметь каноническую форму.

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

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

перейти от неравенств к уравнению следующим образом: в левую часть неравенств вводим дополнительную переменную с коэффициентом (+1) для неравенства ( ) и (-1) для неравенства ( ) дополнительные переменные не наложены целевые неотрицательности, то её заменяют разностью двух неотрицательных переменных, то есть:

= – (

Общий вид канонической формы:

Глава ΙΙ Решение задачи симплексным методом

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

Название метода от латинского simplecx – простой т.к. из начального область допустимых решений задачи имела простейший вид. Идеи метода предложил российский математик Контарович Л.В. в 1939 году и затем эту идею развил и разработал Дж. Данциг в 1949 году.

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

§ 1 Постановка задачи

На предприятии в процессе производства используется 3 вида станков Ι, ІΙ, ІΙІ. При этом расходуется сырьё, трудовые ресурсы, и учитываются накладные расходы.

Известно, что для изготовления станка Ι – ого вида требуется 4 ед. сырья, 2 ед. трудовых ресурсов и 10 ед. накладных расходов; станка ΙІ – ого вида 6 ед. сырья, 2 ед. трудовых ресурсов и 8 ед. накладных расходов; для станка ΙΙІ – ого вида требуется 4 ед. сырья, 2 ед. трудовых ресурсов и 18 ед. накладных расходов; Предприятие имеет в наличии 420 ед. сырья, 120 ед. трудовых ресурсов и 250 ед. накладных ресурсов.

Прибыль от реализации станка І вида - 28 тыс. руб., ІΙ вида - 24 тыс. руб., ΙІΙ вида - 20 тыс. руб. Условия производства требует, чтобы трудовые ресурсы были использованы полностью, а накладные расходы были бы не менее имеющихся в наличии.

Составить план производства станков, обеспечивающих максимальную прибыль.

§ 2 Составление математической модели задачи

Записываем условие задачи в виде таблицы.

Таблица

1. Выбирают переменные задачи.

Пусть количество производимых станков 1-ого, 2-ого и 3-его вида,

1. Составляем систему ограничения задачи

по условию задачи требуется, чтобы

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

1. Задаём целевую функцию

Z(X) =

Математическая модель имеет вид: найти план выпуска станков

X = ( ),

удовлетворяющий системе ограничений задачи

и условию неотрицательности ), при котором прибыль будет максимальной

Z(X) =

§ 3 Алгоритмы решения задачи симплексным методом

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

1. умение находить начальный опорный план;

2. наличие признака оптимальности опорного плана;

3. умение переходит к нехудшему опорному плану.

Алгоритм:

1. Математическая модель задачи должна иметь каноническую форму. В противном случаи её приводят к каноническому виду.

2. Находят начальное опорное решение задачи. Им является вектор, состоящий из тех переменных, которые входят только в одно уравнение в системе ограничений. Если начальное решение сразу не найти то используют метод Гаусса.

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

Макет симплексной таблицы:

Первый столбец – коэффициенты в целевой функции при базисных переменных.