Рефетека.ру / Информатика и програм-ие

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

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

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


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


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


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

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

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

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

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


Псков 2009 г.


Содержание


Введение

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

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

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

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

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

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

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

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

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

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

§ 6 Вывод

Заключение

Литература


Введение


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

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

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

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

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

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

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


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


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


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

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

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


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


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

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

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

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

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

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

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

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


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


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

Целевая функция – это функция 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-ого, 2-ого и 3-его вида, Задача линейного программирования

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


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


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

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

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


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


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


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

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


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


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


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


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


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

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

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

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

Алгоритм:

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

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

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


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

Б

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

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

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

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

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

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

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

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



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

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

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

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

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

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




















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










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

Второй столбец – базисные переменные.

Третий столбец – свободные члены.

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

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

Основное поле симплекс метода – система коэффициентов из уравнения.

Последняя строка – служит для того, чтобы ответить на вопрос: “оптимален план или нет ”.

Индексная строка позволяет нам судить об оптимальности плана.

Проверяют опорное решение, на оптимальность, вычисляя коэффициенты индексной строки по форме:


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


При решении задачи возможны два случая:

- При решении задачи на максимум:

а) все оценки Задача линейного программированияследует, что решение оптимальное

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

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

- При решении задачи на минимум:

а) все оценки Задача линейного программированияследует, что решение оптимальное

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

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

Новое опорное решение находится с помощью ключевого столбца, ключевой строки и ключевого элемента.

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

Ключевая строка указывает на переменную, которую надо вывести из числа базисных для улучшения решения.

Ключевой элемент нужен для элементов нового опорного решения (для новой симплексной таблицы).

Их нахождения зависит от цели задачи.

- При решении задачи на максимум:

а) ключевой столбец – это столбец с отрицательной наименьшей оценкой Задача линейного программирования в индексной строке.

б) ключевая строка – это строка с наименьшим отношением свободных членов к положительным коэффициентам ключевого столбца:


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


в) ключевой элемент – это число расположенное на пересечении ключевых столбца и строки(не может быть равен нулю).

- При решении задач на минимум:

а) ключевой столбец – это столбец с положительной наименьшей оценкой Задача линейного программирования в индексной строке.

б) ключевая строка – это строка с наибольшим отношением свободных членов к положительным коэффициентам ключевого столбца:


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


в) ключевой элемент – это число расположено на пересечении ключевых столбца и строки.

Заполняют первую симплексную таблицу следующим образом:

а) ключевую строку делят на ключевой элемент и записывают на том же месте в новой таблице.

б) заполняют базисные столбцы.

в) остальные элементы пересчитывают по правилу “прямоугольника”:


НЭ = СТЭ – Задача линейного программирования


где НЭ – новый элемент

СТЭ – элемент старого плана

РЭ – разрешающей элемент

А и Б – элементы старого плана

Возвращаются ко второму этапу алгоритма – проверка плана на оптимальность.


§ 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 ед. накладных расходов.


Заключение


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

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

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

Похожие работы:

  1. Решение транспортной задачи линейного ...
  2. • Решение задачи линейного программирования графическим ...
  3. • Решение задачи линейного программирования симплекс-методом
  4. • Линейное программирование как метод оптимизации
  5. • Решение задач линейного программирования
  6. • Линейное программирование: решение задач графическим способом
  7. • Использование линейного программирования для решения ...
  8. • Решения задач линейного программирования ...
  9. • Линейное программирование: постановка задач и графическое ...
  10. • Линейное программирование
  11. • Применение линейного программирования для решения ...
  12. • Решение оптимизационной задачи линейного программирования
  13. • Решение задач линейного программирования симплекс ...
  14. • Решение задач линейного программирования симплекс ...
  15. • Решение задач линейного программирования
  16. • Задача линейного программирования
  17. • Задачи линейного программирования. Алгоритм Флойда
  18. • Билеты математические методы исследования экономики
  19. • Решения задачи планирования производства симплекс ...
Рефетека ру refoteka@gmail.com