ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ФГОУ ПО “ПСКОВСКИЙ КОЛЛЕДЖ СТРОИТЕЛЬСТВА И ЭКОНОМИКИ”
Предмет “Математические методы”
Задача линейного программирования
Курсовая работа
Студента группы 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 вида станков Ι, ІΙ, ІΙІ. При этом расходуется сырьё, трудовые ресурсы, и учитываются накладные расходы.
Известно, что для изготовления станка Ι – ого вида требуется 4 ед. сырья, 2 ед. трудовых ресурсов и 10 ед. накладных расходов; станка ΙІ – ого вида 6 ед. сырья, 2 ед. трудовых ресурсов и 8 ед. накладных расходов; для станка ΙΙІ – ого вида требуется 4 ед. сырья, 2 ед. трудовых ресурсов и 18 ед. накладных расходов; Предприятие имеет в наличии 420 ед. сырья, 120 ед. трудовых ресурсов и 250 ед. накладных ресурсов.
Прибыль от реализации станка І вида - 28 тыс. руб., ІΙ вида - 24 тыс. руб., ΙІΙ вида - 20 тыс. руб. Условия производства требует, чтобы трудовые ресурсы были использованы полностью, а накладные расходы были бы не менее имеющихся в наличии.
Составить план производства станков, обеспечивающих максимальную прибыль.
§ 2 Составление математической модели задачи
Записываем условие задачи в виде таблицы.
Таблица
| Вид ресурса |
Расход рес. на производство ед. продукции |
Запас ресурса |
||
| Ι |
ІΙ |
ІΙІ |
||
| сырьё |
4 |
2 |
10 |
420 |
| трудовые ресурсы |
6 |
2 |
8 |
120 |
| накладные расходы |
4 |
2 |
18 |
250 |
| Прибыль |
28 |
24 |
20 |
max |
1. Выбирают переменные задачи.
Пусть количество производимых станков 1-ого, 2-ого и 3-его вида,
2. Составляем систему ограничения задачи
по условию задачи требуется, чтобы
трудов
3. Задаём целевую функцию
Z(X) =
Математическая модель имеет вид: найти план выпуска станков
X = (),
удовлетворяющий системе ограничений задачи
и условию неотрицательности ), при котором прибыль будет максимальной
Z(X) =
§ 3 Алгоритмы решения задачи симплексным методом
Общая идея симплексного метода (метода последовательного улучшения плана) для решения задачи линейного программирования состоит
1) умение находить начальный опорный план;
2) наличие признака оптимальности опорного плана;
3) умение переходит к нехудшему опорному плану.
Алгоритм:
1) Математическая модель задачи должна иметь каноническую форму. В противном случаи её приводят к каноническому виду.
2) Находят начальное опорное решение задачи. Им является вектор, состоящий из тех переменных, которые входят только в одно уравнение в системе ограничений. Если начальное решение сразу не найти то используют метод Гаусса.
Количество переменных решения равно количеству уравнений системы. Заполняют симплексную таблицу по системе ограничений и целевой функции.
Макет симплексной таблицы:
| Б |
|
|
|
|
|
|
… |
|
|
|
|
|
|
|
|
… |
|
|||
| … |
|||||||||
| … |
|||||||||
| … |
… |
… |
… |
… |
… |
… |
… |
… |
… |
|
|
|||||||||
Первый столбец – коэффициенты в целевой функции при базисных переменных.
Второй столбец – базисные переменные.
Третий столбец – свободные члены.
Самая верхняя строка – коэффициенты при целевой функции.
Вторая верхняя строка – сами переменные, входящие в целевую функцию и в систему ограничений.
Основное поле симплекс метода – система коэффициентов из уравнения.
Последняя строка – служит для того, чтобы ответить на вопрос: “оптимален план или нет ”.
Индексная строка позволяет нам судить об оптимальности плана.
3) Проверяют опорное решение, на оптимальность, вычисляя коэффициенты индексной строки по форме:
При решении задачи возможны два случая:
- При решении задачи на максимум:
а) все оценки следует, что решение оптимальное
б) хотя бы одна оценка и при соответствующей переменной нет положительных коэффициентов, то задача не имеет оптимального решения m, k, целевая функция неограниченна в О.Д.Р.
в) хотя бы одна оценка и при соответствующей переменной есть положительный коэффициент то данное решение можно улучшить, построив новое опорное решение на котором целевая функция будет больше.
- При решении задачи на минимум:
а) все оценки следует, что решение оптимальное
б) хотя бы одна оценка и при соответствующей переменной нет положительных коэффициентов, то задача не имеет оптимального решения m, k, целевая функция неограниченна в О.Д.Р.
в) хотя бы одна оценка и при соответствующей переменной есть положительный коэффициент то данное решение можно улучшить, построив новое опорное решение.
4) Новое опорное решение находится с помощью ключевого столбца, ключевой строки и ключевого элемента.
Ключевой столбец указывает на переменную, которую надо вывести из числа базисных для улучшения решения.
Ключевая строка указывает на переменную, которую надо вывести из числа базисных для улучшения решения.
Ключевой элемент нужен для элементов нового опорного решения (для новой симплексной таблицы).
Их нахождения зависит от цели задачи.
- При решении задачи на максимум:
а) ключевой столбец – это столбец с отрицательной наименьшей оценкой в индексной строке.
б) ключевая строка – это строка с наименьшим отношением свободных членов к положительным коэффициентам ключевого столбца:
min =
в) ключевой элемент – это число расположенное на пересечении ключевых столбца и строки(не может быть равен нулю).
- При решении задач на минимум:
а) ключевой столбец – это столбец с положительной наименьшей оценкой в индексной строке.
б) ключевая строка – это строка с наибольшим отношением свободных членов к положительным коэффициентам ключевого столбца:
mах =
в) ключевой элемент – это число расположено на пересечении ключевых столбца и строки.
5) Заполняют первую симплексную таблицу следующим образом:
а) ключевую строку делят на ключевой элемент и записывают на том же месте в новой таблице.
б) заполняют базисные столбцы.
в) остальные элементы пересчитывают по правилу “прямоугольника”:
НЭ = СТЭ –
где НЭ – новый элемент
СТЭ – элемент старого плана
РЭ – разрешающей элемент
А и Б – элементы старого плана
6) Возвращаются ко второму этапу алгоритма – проверка плана на оптимальность.
§ 4 Построение начального опорного решения методом Гаусса
Приводим задачу к каноническому виду.
Z(X) =
)
Z(X) =
)
4 2 10 1 0 420
6 2 8 0 0 120 * (-1)
4 2 18 0 -1 250
28 24 20 0 0 0
4 2 10 1 0 420
-6 -2 -8 0 0 -120 + +
4 2 18 0 -1 250
28 24 20 0 0 0
-2 0 2 1 0 420
6 2 8 0 0 120 *12
-2 0 10 0 -1 130
28 24 20 0 0 0
-2 0 2 1 0 300
72 24 96 0 0 1440 -
-2 0 10 0 -1 130
28 24 20 0 0 0
-2 0 2 1 0 300
72 24 96 0 0 1440
-2 0 10 0 -1 130
-44 0 -76 0 0 -1440
-2 0 2 1 0 300 *5
3 1 4 0 0 60
-2 0 10 0 -1 130 * (-1)
-44 0 -76 0 0 -1440
-10 0 10 5 0 1500
3 1 4 0 0 60
2 0 -10 0 1 -130 +
-44 0 -76 0 0 -1440
-10 0 10 5 0 1500
3 1 4 0 0 60
12 0 0 5 1 1370
-44 0 -76 0 0 -1440
-2 0 2 1 0 300 -
3 1 4 0 0 60
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440
-4,4 0 2 0 -1 26 *2
3 1 4 0 0 60
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440
-8,8 0 4 0 -2 52
3 1 4 0 0 60 -
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440
-8,8 0 4 0 -2 52 *19
11,8 1 0 0 2 8
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440
-167,2 0 76 0 -38 988
11,8 1 0 0 2 8
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440 +
-167,2 0 76 0 -38 988
11,8 1 0 0 2 8
2,4 0 0 1 1 274
-123,2 0 0 0 -38 -452
-2,2 0 1 0 -0,5 13
11,8 1 0 0 2 8
2,4 0 0 1 1 274
-123,2 0 0 0 -38 -452
§ 5 Решение задачи
Составляем симплексную таблицу
Симплексная таблица 1
| Б |
|
-452 |
-123,2 |
0 |
0 |
0 |
-38 |
|
|
|
|
|
|
|
|
|||
|
|
0 |
13 |
-2,2 |
1 |
0 |
0 |
-0,5 |
|
|
|
0 |
8 |
11,8 |
1 |
0 |
0 |
2 |
|
|
|
0 |
274 |
2,4 |
0 |
0 |
1 |
1 |
|
|
|
452 |
123,2 |
0 |
0 |
0 |
38 |
||
т. к все > 0 решение оптимальное
Ответ: max Z(X) = 452 при X = (0; 8; 13)
§ 6 Вывод
Максимальная прибыль в размере 425 тыс. руб. может быть достигнута, если производить 8 станков ІΙ вида, 13 станков ІΙІ вида и не производить станки Ι вида.
При этом расходуется 146 ед. сырья, 120 ед. трудовых ресурсов и 250 ед. накладных расходов.
Заключение
Данная курсовая работа посвящена вопросу о решении задачи линейного программирования методом последовательного улучшения плана, иначе симплекс – метод. Состоит из введения, двух глав, заключения и списка литературы.
В первой главе рассказывается о линейном программировании в частности, и о том, что такое общая постановка задачи линейного программирования, как составить математическую модель, а также рассказано о канонической форме задач линейного программирования.
Вторая глава работы посвящена практической части решения задачи. Строится математическая модель, решается задача симплексным методом, а также методом Гаусса.