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

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ МОСКОВСКОЙ ОБЛАСТИ

Государственное образовательное учреждение высшего профессионального образования

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОБЛАСТНОЙ УНИВЕРСИТЕТ (МГОУ)

Кафедра «Прикладная математика и информатика»

Курсовая работа по основам математического моделирования социально-экономических процессов

Тема: «Разработка модели и решение задачи линейного программирования (на примере задачи планирования производства)»

Выполнила студентка:

26-2 группы 2 курса

очной формы обучения

экономического факультета

Андреева Екатерина Алексеевна

Научный руководитель:

Кандидат технических наук, доцент Юров В.М.

Москва 2014



Содержание

Введение

1. Теоретические основы линейного программирования

1.1 Теория линейного программирования

1.2 История создания линейного программирования

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

1.4 Двойственная задача линейного программирования

2. Практическая часть

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

2.2 Упрощение условий исходной задачи

2.3 Построение экономико-математической модели задачи линейного программирования

2.4 Решение задачи «вручную» симплексным методом

2.5 Двойственная задача

2.6 Решение задачи в Excel

2.7 Интерпретация результатов расчетов и выработка управленческого решения

Заключение

Список литературы



Введение

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

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

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

В курсовой работе я раскрываю:

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

2) различные методы решения задач линейного программирования;

3) вербальная постановка задачи линейного программирования;

4) разработка экономико-математической модели задачи линейного программирования;

5) решение задачи линейного программирования «вручную» при помощи симплексного метода;

6) Построение компьютерной модели задачи линейного программирования и решение задачи на компьютере.

Итогом данной курсовой работы будет являться решение задачи линейного программирования на планирование производства «вручную» при помощи симплексного метода и решения задачи на компьютере при помощи средств Excel,что позволит выработать управленческое решение на основе отчетов Excel и найти оптимальное решение задачи.



1. Теоретические основы линейного программирования

1.1 Теория линейного программирования

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования, посвящённый теории и методам решения экстремальных задач на множества n - мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. программирование симплексный еxcel

Сущность линейного программирования состоит в нахождении точек максимума или минимума некоторой функции при определенном наборе ограничений, которые наложены на аргументы. Функция F, максимум или минимум которой необходимо определить, называется целевой функцией задачи линейного программирования. Ограничения, наложенные на аргументы, образуют систему ограничений, которая может иметь, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым решением задачи линейного программирования. Допустимое решение, при котором достигается максимум или минимум целевой функции F, является оптимальным решением задачи линейного программирования.

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

F = c₁x₁ + c₂x₂ + … + c_j x _j + … +c_nx_n > max (min),

где система ограничений имеет вид:

,

x_j 0; i = 1,2,…,m; j = 1,2,…, n

где х_j - неизвестные; a_ij, b_i, c_j - заданные постоянные величины.

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

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

· транспортные задачи;

· задачи о составлении плана;

· задачи на смеси.

1.2 История создания линейного программирования

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

В 1924 - 1925 годах советским экономистом и статистиком Василием Васильевичем Леонтьевым была разработана межотраслевая модель производства и распределения продукции.

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

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

Термин «программирование» был предложен в середине 1940-х годов одним из основателей линейного программирования Джорджем Данцигом ещё до того, как линейные задачи решались при помощи использования компьютера, поэтому данный термин понимается под смыслом «планирования».

В 1949 году Джорджем Бернардом Данцигом - американским математиком - был разработан эффективный метод решения задач линейного программирования - симплекс-метод.

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

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

Решение задачи линейного программирования симплексным методом начинается с изначальной записать исходных данных задачи. Затем необходимо определить, сколько в задаче будет переменных, и в качестве чего они будут выступать (х₁, х₂, … , х_n). В качестве базисных (основных) переменных выбираются такие переменные, каждая из которых входит, только в одно уравнение системы ограничений, и нет таких уравнений, в которые не входит ни одна из этих переменных. Решение будет допустимо, если знаки базисных переменных имеют те же знаки, что и свободные члены в правой части уравнений.

Определив переменные, записываем целевую функцию (F) и определяем, на что она направлена (прибыль, выгода) и к чему стремится(max, min). Дальше составляем систему ограничений, исходя из условий задачи.

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

1. Приводим задачу линейного программирования к каноническому виду.

2. Определяем количество основных и неосновных переменных.

3. Выражаем основные переменные через неосновные переменные.

4. Неосновные переменные приравниваем к нулю, находим первоначальное базисное решение и проверяем его на допустимость. (Решение допустимо, если все базисные переменные положительны).

5. Находим целевую функцию и проверяем ее на оптимальность. (Если задача решается на max, то оптимальным решением будет такое, где в целевой функции, выраженной через неосновные переменные, отсутствуют коэффициенты со знаком «+»; если задача решается на min, то оптимальным решением будет такое, где в целевой функции, выраженной через неосновные переменные, отсутствуют коэффициенты со знаком «-»). Если решение оптимально, то решение задачи закончено.

6. Если решение задачи не оптимально необходимо улучшать решение, для этого переводим любую неосновную переменную со знаком «+» (при решении задачи на max), или со знаком «-» (при решении задачи на min) в состав основных переменных. При этом одна из основных переменных переходит в состав неосновных.

7. Находим максимально возможное значение новой основной переменной, при этом одна из основных переменных станет равна нулю.

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

9. Определяем новый состав переменных.

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

1.4 Двойственная задача линейного программирования

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

Если в исходной задаче целевая функция задается на максимум, то в двойственной задаче, целевая функция задается на минимум. И на оборот, Если в исходной задаче целевая функция задается на минимум, то в двойственной задаче, целевая функция задается на максимум.

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

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

,

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

Соответствие между переменными взаимно двойственных задач.

Первоначальные переменные:

,

,

,

Дополнительные переменные:

,

,

,

Для оптимальности X и Y , необходимо выполнение неравенства:

,

Из этой системы следует:

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

Для первого равенства.

1) Если >0, то для выполнения равенства необходимо, чтобы выражение в скобках было равно нулю.

,

2) Из этого следует, что ограничение для i-того ресурса выполняется в виде равенства. Это означает, что ресурс полностью выполняется, и излишек нет, они равны нулю.

,

3) Если выражение в скобках не равно нулю, то

4) Если выражение в скобках не равняется нулю, то

5) Теневая цена на ресурс будет равна нулю, если есть избыток ресурса; теневая цена на ресурс не будет равна нулю, если избыток ресурса равен нулю.

Для второго равенства.

1) Если , то выражение в скобках должно равняться нулю.

,

2) Получаем, что j - тое ограничение выполняется в виде равенства.

3) Если выражение в скобках не равно нулю, то для выполнения второго равенство необходимо, чтобы



2. Практическая часть

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

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

Таблица 1 Исходные данные

Исходный продукт	Затраты ресурса на единицу товара	Суточный запас
	стол	стул	шкаф	лавочка
Деревянная доска (шт.)	10	4	15	8	168 шт.
Гвозди (шт.)	5	10	30	10	500 шт.
Металлические заготовки (шт.)	6	4	2	12	144 шт.
Чел/часов (часы)	2	1	4	3	120 часов
Прибыль, денежн. ед.	14	7	22	18	-

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

2.2 Упрощение условий исходной задачи

Для решения задачи линейного программирования «вручную», упрощаем условия исходной задачи.

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

Таблица 2 Исходные данные

Исходный продукт	Затраты ресурса на единицу товара	Суточный запас (шт.)
	стол	лавочка
Деревянная доска (шт.)	10	8	168
Гвозди (шт.)	5	10	180
Металлические заготовки (шт.)	6	12	144
Прибыль, денежн. ед.	14	18	-

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

2.3 Построение экономико-математической модели задачи линейного программирования

1) Определяем, что будет выступать в качестве переменных:

x₁ - количество столов, необходимых для выпуска

x₂ - количество лавочек, необходимых для выпуска

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

F(x) = 14 x₁ + 18 x₂ max

3) Записываем систему ограничений:

,

4) Записываем граничные условия:

x₁ 0, x₂ 0

2.4 Решение задачи «вручную» симплексным методом

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

,

Число уравнений (m) равно 3, а число переменных (n) равно 5. Из этого следует, что основных переменных будет 3, а свободных переменных - 5.

I этап:

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

Состав переменных:

x₃, x₄,x₅ - основные переменные

x₁, x₂ - неосновные переменные

х₁=0, х₂=0

II этап: Шаг 1.

а),

Неосновные переменные приравниваем к нулю и находим начальное допустимое решение.

б) = - решение допустимо, так как все переменные неотрицательные.

в) F= 14x₁+18x₂ - решение не оптимально, так как переменные х₁ и х₂ положительные, значит целевую функцию F можно увеличить.

г) Так как решение задачи не оптимально, необходимо продолжать улучшать решение задачи. Для этого переводим одну из неосновных переменных в основные переменные.

Так как в целевой функции коэффициент при х₂ больше, переводим ее в ранг основных переменных.

,

,

,

max возможное x₂ = min

Получаем, что х₂ =12, а х₅=0

Разрешающим будет третье уравнение.

х₂ переводим в состав основных переменных, следовательно х₅ - в неосновные; х₅= 0.

д) Новый состав переменных:

х₂, х₃, х₄ - основные переменные;

х₁, х₅ - неосновные переменные.

Шаг 2.

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

а) ,

б) - решение допустимо

в) Находим целевую функцию:

F=216+5х₁-1,5х₅ - решение не оптимально

Переводим х₁ в состав основных переменных.

г)

,

,

max возможное x₁ = min

Значит, что х₁ =12, а х₃ =0

Разрешающим будет второе уравнение.

х₁ переводим в состав основных переменных, следовательно х₃- в неосновные; х₅ = 0.

д) Новый состав переменных:

х₁, х₂, х₄ - основные переменные;

х₃, х₅ - неосновные переменные.

Шаг 3.

а)

б) - решение допустимо

в) Находим целевую функцию:

F = 276 - решение оптимально, так как коэффициенты при x₃ и x₅ отрицательные, значит целевую функцию больше увеличить нельзя.

Оптимальное решение задачи:

F = 276

,

,

1) Максимальный доход предприятия составит 276 денежных единиц.

2) Необходимо производить 12 столов, и 10 лавочек.

3) Деревянные доски и металлические заготовки используются полностью, а гвозди остаются в избытке 60 шт.

2.5 Двойственная задача

1) Записываем данные исходной задачи.

F(x) = 14 x₁ + 18 x₂ max

,

2) Записываем данные, которые получили на последнем шаге решения задачи симплексным методом.

F = 276

,

Соответствие между переменными двойственных задач:

,

,

Y* = ()

Так как второй ресурс в избытке, теневая цена на него будет равна нулю.

y₂ =0

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

Так как x₁ и x₂ , то цены на продукцию повышать нет необходимости, поэтому нормировочная стоимость будет равна нулю.

y₄ = 0

y₅ =0

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

F = 276

y₁ =

y_{3 =}

Проверка:

= 140 + 136=276

Z = F

Y* =

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

2.6 Решение задачи в Excel

Для решения задач линейного программирования в Excel построим шаблон и вводим исходные данные (рис. 2.1).

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

Рис. 2.1. - Экранный вид рабочего листа

Для нахождения оптимального решения задачи, необходимо использовать функцию «Поиск решения». Вводим все необходимые данные в окно «Параметры поиска решения» (рис. 2.2).

Рис. 2.2. - Настройка окна «Поиск решения».

В итоге получаем результаты решения задачи (рис. 2.3).

Рис. 2.3. - Результаты решения задачи.

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

1) мебельной фабрике за сутки необходимо производить: 5 столов, 18 стульев, 1 шкаф, 3 лавочки.

2) Максимальная прибыль предприятия за сутки составит 283,27 денежных единиц.

3) Такие ресурсы, как деревянная доска и металлическая заготовка будут использованы полностью, а гвозди и человеческие часы остаются в избытке.

2.7 Интерпретация результатов расчетов и выработка управленческого решения

Рис. 2.4. - Отчет о результатах.

В первой таблице отчета указан номер и название ячейки, в которой находится целевая функция, а также указано исходное (начальное) и окончательное (оптимальное) значение.

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

В третей таблице отчета указаны номера и названия ячеек, в которых находятся левые части ограничений и их результирующие значения. В столбце «Формула» ограничения записаны через номера ячеек. В столбце «Состояние» «Привязка» означает, что оптимальное решение получается при выполнении равенства в соответствующем ограничении. «Состояние» «Без привязки» означает, что оптимальное решение выполняется при выполнении строгого неравенства на соответствующем ограничении. В столбце «Разница» указано количество неиспользованного ресурса. В данной задаче видно, что гвозди и человеческие ресурсы использованы не полностью.

Рис.2.5. - Отчет об устойчивости.

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

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

«Тень цена» - характеризует ценность ресурсов для производства и показывает, на сколько, увеличится целевая функция (доход фабрики), при увеличении данного ресурса на 1 единицу.

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

«Значение целевой функции» - это суммарная выручка фабрики.

«Значение переменных» - это оптимальный план задачи.

«Нижний предел» - это наименьшее значения, которое может принять неизвестное (в нашем случае количество продукции).

«Результат целевой функции» (по нижнему пределу) - это значение, которое будет в целевой ячейке, если неизвестное будет равно «Нижнему пределу».

«Верхний предел» - это наибольшее значение, которое может содержать неизвестное, чтобы получить максимальное значение целевой функции.

«Результат целевой функции» (по верхнему пределу) - это значение, которое будет в целевой ячейке, если неизвестные будут равны «Верхнему пределу».

Рис.2.6. - Отчет о пределах.

Управленческое решение:

При принятии управленческого решения обращаем внимание на отчет об устойчивости. Так как «Теневая цена» на такие ресурсы как гвозди и человеческие часы равны нулю, можно сделать вывод, что увеличение этих ресурсов никак не изменит прибыль предприятия. Нужно отметить, что данные ресурсы находятся в избытке и их следует сократить. Обращаем внимание на столбец «Допустимое уменьшение» и сокращаем количество гвоздей на 220 штук и уменьшаем число человеческих часов на 78.

Следует отметить, что «Теневая цена» на столы для благотворительности отрицательная. Это означает, что производить данную продукцию не выгодно. Но так как данный вид продукции полностью идет на благотворительность отказаться от его производства нет возможности.

Результаты задачи после улучшения (Рис.2.7).

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

Рис. 2.7. - Результаты задачи после улучшения.

По результатам улучшенного решения задачи делаем вывод:

1) мебельной фабрике за сутки необходимо производить: 5 столов, 19 стульев, 1 шкаф, 2 лавочки.

2) Максимальная прибыль предприятия за сутки составит 279 денежных единиц.

3) Такие ресурсы, гвозди, металлические заготовки и человеческие часы будут использованы полностью. В избытке останется 2 шт. деревянной доски.



Заключение

Линейное программирование - это один из самых разработанных и часто применяемых разделов математического программирования. Линейное программирование решает задачи на экстремумы с множеством переменных.

Развитие экономики, да и науки в целом, требовало все больше количественных показателей, что и послужило к началу развития линейного программирования. Так, в 1920 году появились первые предпосылки к появлению линейного программирования. А в 1934 году Л.В. Канторович сформулировал в своей работе новый класс экстремальных задач, за что впоследствии был удостоен Нобелевской премии. И уже в 1949 году американским математиком Дж. Данцигом был разработан метод решения задач линейного программирования - симплекс-метод.

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

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

Задача на планирование производства относится к классу задач линейного программирования. Если такая задача имеет 2 переменные, то ее можно решить графическим способом или симплекс-методом. Если же задача имеет больше 3-х переменных, то для решения такой задачи необходимо использовать средства MS Excel.

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



Список литературы

1. Акулич И. Л. Математическое программирование в примерах и задачах: Учебное пособие для студентов эконом вузов.- М.: Высш. шк., 2008.- 319 с.

2. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения. Учебное пособие. - М.: ИНФРА-М, 2006.

3. Грызина Н.Ю., Мастяева И.Н., Семенихина О.Н. Математические методы исследования операций в экономике: Учебно-методический комплекс - М.: Изд-во ЕАОИ, 2008. - 204 с.

4. Даугавет О. К., Романовский И. В. О деятельности и работах Л. В. Канторовича в области программирования. Журнал Новой экономической ассоциации : журнал. -- М., 2012. -- № 1 (13). -- С. 185--190.

5. Калашникова Т.В. Исследование операций в экономике: учебное пособие. - Томск: Изд-во Томского политехнического университета, 2007. - 92 с.

6. Кремер Н.Ш. Исследование операций в экономике. - М.: ЮНИТИ, 2010.

7. Орлова И.В. Экономико-математическое моделирование: практическое пособие по решению задач. - М.: ИНФРА-М, 2010.

8. Полтерович В. М. Теория оптимального распределения ресурсов Л. В. Канторовича в истории экономической мысли. Журнал Новой экономической ассоциации : журнал. -- М., 2012. -- № 1 (13). -- С. 176--180.

9. ru.wikipedia.org - Свободная Энциклопедия.

Размещено на Allbest.ru

...