Реферат: Задача линейного программирования
ФЕДЕРАЛЬНОЕАГЕНТСТВО ПО ОБРАЗОВАНИЮ
ФГОУ ПО“ПСКОВСКИЙ КОЛЛЕДЖ СТРОИТЕЛЬСТВА И ЭКОНОМИКИ”
Предмет“Математические методы”
Задачалинейного программирования
Курсовая работа
Студента группы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 max1. Выбираютпеременные задачи.
Пусть/> количествопроизводимых станков 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 -38/>
/>
/>
/>
/>
/>
/>
/>
13 -2,2 1 -0,5/>
8 11,8 1 2/>
274 2,4 1 1/>
452 123,2 38/>
/>
т. к все /> > 0 решениеоптимальное
Ответ: maxZ(X)= 452 при X = (0; 8; 13)
§6 Вывод
Максимальная прибыль вразмере 425 тыс. руб. может быть достигнута, если производить 8 станков ІΙвида, 13 станков ІΙІ вида и не производить станки Ι вида.
При этом расходуется 146ед. сырья, 120 ед. трудовых ресурсов и 250 ед. накладных расходов.
Заключение
Данная курсовая работапосвящена вопросу о решении задачи линейного программирования методом последовательногоулучшения плана, иначе симплекс – метод. Состоит из введения, двух глав,заключения и списка литературы.
В первой главерассказывается о линейном программировании в частности, и о том, что такоеобщая постановка задачи линейного программирования, как составитьматематическую модель, а также рассказано о канонической форме задач линейногопрограммирования.
Вторая глава работыпосвящена практической части решения задачи. Строится математическая модель,решается задача симплексным методом, а также методом Гаусса.