Методы линейного программирования

ВЕДЕНИЕ

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

Родоначальником экономико-математического моделирования  считается лейб-медик короля Людовика XIV Ф. Кене. В 1758 г. он опубликовал свой труд «Экономические таблицы». В нем Ф.Кене сделал попытку описать процесс общественного воспроизводства с применением математических методов исследования. Свой вклад в развитие экономико-математическое моделирование внесли такие известные учение, как О. Курно, В.Парето, Л.Вальрас, В.Леонтьев, Д. Хикс, Р. Слоу, Е.Е. Слуцкий, Л.В. Кантрович и другие.

Линейное программирование — область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. Начало линейной оптимизации было положено в  1983 г., когда вышла в свет работа профессора Ленинградского университета Л.В. Канторовича «Математические методы организации и планирования производства».

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

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

Объект исследования курсовой работы – цех мебельного комбината. Предмет исследования - планирование производства продукции при наличии ограниченных ресурсов.

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

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

Задачи курсовой работы:

1) раскрыть теоретическое содержание данной темы.

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

3) сформулировать и найти оптимальное решение задачи с помощью средств MS Excel.

4) провести анализ отчетов и ответить на вопросы задания.

Курсовая работа состоит из четырех глав.

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

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

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

В четвертой главе даны ответы на вопросы с подробным  пояснением на основании отчетов MS Excel.

Курсовая работа состоит из 3 таблиц, 9 рисунков и 5 литературных источников.

 

1 ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ ПО ЗАДАЧАМ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ТЕОРИИ ДВОЙСТВЕННОСТИ

1.1 Задачи математического программирования

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

В общем виде постановка задачи математического  программирования состоит в определении  значений переменных х₁, х₂, …, х_n, при которых достигается максимум или минимум функции

 

                                                                         (1.1)

 

при условиях:

 

 

                                                                                                                (1.2)

 

 

где n – количество переменных;

      m – количество ограничений.  

Функция (1.1) называется целевой функцией, а условия (1.2) – ограничениями данной задачи. Запись в ограничениях означает, что возможен один из знаков , = или _{[1, c5].}

Переменные задачи х₁, х₂, …, х_n могут иметь различный экономический смысл. Например, если предприятие выпускает три вида продукции, и нужно найти оптимальный план производства, то х₁, х₂, х₃ – количество продукции каждого вида, которое необходимо производить. Если в задаче необходимо найти наилучший состав рациона, в которую могут входить несколько составных компонентов (например, сено и силос в рационе коров), то х₁ и х₂ – количество каждого продукта, которое нужно включить в рацион (в данном случае, сена и силоса) [2, c 8].

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

Система ограничений (1.2) вытекает из ограниченности материальных, трудовых ресурсов, технологических требований или же из здравого смысла. Например, в задаче планирования производства продукции ограничены материальные и трудовые ресурсы предприятия, а также сырье или материалы, используемые для производства этой продукции. Для задачи составления рациона ограничения заключаются в необходимости того, чтобы рацион был полноценным (содержал питательные вещества, витамины и микроэлементы, необходимые для жизнедеятельности коров) [1, c 11].

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

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

В общем виде задача линейного программирования заключается следующем: найти значения переменных х₁, х₂, …, х_n, доставляющие оптимальное значение целевой функции:

 

                                                                            (1.3)

при ограничениях

                                                                   (1.4)

и граничных  условиях

.                                                                   (1.5)

Часто граничные  условия сводятся к требованиям  неотрицательности переменных:

 

                                                                             (1.6)

Здесь параметры  задачи - это некоторые константы, известные для каждой конкретной задачи.

Ограничения (1.4) называют функциональными, а ограничения (1.5) – прямыми.

Условия неотрицательности  переменных (1.6) с математической точки зрения являются необязательными, но в моделях экономических задач они, как правило, всегда присутствуют. Это связано с экономическим смыслом переменных х₁, х₂, …, х_n. Например, если под x_j понимается количество продукции вида j, которое необходимо выпускать на предприятии, то очевидно, что оно не может быть отрицательным [3, c 14].

Набор значений переменных х_1, х_2,…,х_n, при котором выполняются все ограничения, называется допустимым решением или планом. Совокупность всех допустимых решений составляет область допустимых решений.

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

Существует  универсальный метод решения задач линейного программирования – симплекс-метод. Автоматизировать решение этим методом можно с помощью надстройки Поиск решения пакета MS Excel.

1.3 Постановка задачи планирования производства продукции

Рассмотрим  задачу планирования производства продукции в общем виде.

 Для производства  продукции n типов требуются ресурсы m видов. Нормы расхода ресурсов на производство единицы продукции каждого типа заданы матрицей , где – количество ресурса i–го вида, необходимое для производства единицы продукции j-го типа. Известно количество ресурсов  ( ) каждого вида, которое имеется в наличии у предприятия. Известны также величины прибыли С_j ( ), которую получит предприятие при реализации единицы продукции j-го типа. Требуется найти оптимальный план производства продукции, т.е. количество продукции каждого типа, которое нужно произвести, чтобы получить наибольшую прибыль. Условие задачи представлено в виде  таблицы 1.

 

Таблица 1- Исходные данные для задачи планирования выпуска продукции

Ресурсы	Расход ресурсов на единицу продукции				Наличие ресурсов
	Тип 1	Тип 2	…	Тип n
Ресурс 1	a11	a12	…	a1n	b1
Ресурс 2	a21	a22	…	a2n	b2
…	…	…	…	…	…
Ресурс m	am1	am2	…	amn	bm
Прибыль	C1	C2	…	Cn

 

Обозначим через x_j – количество продукции j-го типа, которое планируется выпустить ( ). Тогда математическая модель задачи будет выглядеть следующим образом:

                                                                (1.7)

                                                                   (1.8)

                                                                    (1.9)

 

Целевая функция (1.7) этой задачи представляет собой общую прибыль от производства всей продукции. Ограничения (1.8) выражают условие того, что потребление ресурса i-го вида не должно превышать запаса этого ресурса. Условия неотрицательности переменных (1.9) вытекают из смысла переменной x_j ( ): количество продукции не может быть отрицательным [4, c 16].

1.4  Каноническая форма записи ЗЛП

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

Чтобы привести к каноническому виду задачу с  ограничениями-неравенствами, вводят дополнительные переменные. Причем если неравенство имеет вид “меньше  или равно”( ), то дополнительную переменную прибавляют к левой части ограничения, а если вид “больше или равно”( ), то дополнительную переменную вычитают  из его левой части. В целевую функцию дополнительные переменные вводят с коэффициентами, равными 0.

Таким образом, задача (1.7) – (1.9) может быть записана в следующей канонической форме:

 

                                                                               (1.10)

 

Дополнительные переменные y_i ( ) представляют собой остатки ресурсов каждого вида. Если в оптимальном решении какой-либо ресурс будет использован полностью, то ограничение исходной задачи (1.8) будет выполнено в виде равенства и y_i=0. Такое ограничение в отчетах Exсel называется связанным. Ресурс, который использован полностью, считается дефицитным [4, c 18] .

1.5  Двойственность в линейном программировании

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

1. Она имеет столько переменных, сколько ограничений в исходной задаче;
2. Правые части ограничений исходной задачи становятся коэффициентами целевой функции в двойственной задаче;
3. Если исходная задача на максимум, то двойственная задача – на минимум, и наоборот;
4. Матрица коэффициентов при переменных в ограничениях транспонируется;
5. Коэффициенты целевой функции исходной задачи становятся правыми частями ограничений в двойственной задаче;
6. Если ограничения исходной задачи имеют вид , то двойственной - и наоборот;
7. На переменные двойственной задачи наложено условие неотрицательности.