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

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

2. Постановка задачи

3. Математическая модель задачи

4. Решение задачи в Excel с помощью надстройки Поиск решения

Заключение

Список использованных источников

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

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

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

Целью данной курсовой работы является:

— изучение методов решения экономических задач с помощью линейного программирования;

получение навыков решения задач линейного программирования;

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

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

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

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

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

количественное выражение выбранного критерия оптимальности в форме целевой функции;

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

Таким образом, математическая модель задачи формулируется следующим образом: найти такие значения переменных х1, х2, х3, удовлетворяющих линейным ограничениям, при которых линейная функция обращалась бы в минимум (или максимум).

В общем виде математическая формулировка задачи линейного программирования (ЗЛП) следующая: найти значения переменных хi (i 1, …, n), при которых достигается максимум (минимум) целевой функции:

F c1x1 + c2x2 + … + сnхn max (min)

и выполняются ограничения:

где аij, bi, cj — заданные постоянные величины;

m — число уравнений;

n — число переменных.

Запись {,, } в ограничениях означает, что возможен один из знаков (, или).

Решение Х (х1, х2, …, хn), при котором выполняются все ограничения, называется допустимым. Допустимое решение, при котором функция F принимает оптимальное значение (максимум или минимум), называется оптимальным.

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

Постановка задачи. Для производства продукции n типов требуются ресурсы m видов. Нормы расхода ресурсов на производство одной единицы продукции каждого типа заданы матрицей {aij}, где aij — количество ресурса i-го вида, необходимое для производства одной единицы продукции j-го типа. Известно количество ресурсов (bi, где i = 1, …, m) каждого вида, которое имеется в наличии у предприятия. Известны также величины прибыли (Сj), которую получит предприятие при реализации одной единицы продукции j-го типа. Требуется найти оптимальный план производства продукции, т. е. количество продукции каждого типа, которое нужно произвести, чтобы получить наибольшую прибыль.

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

Целевая функция задачи представляет собой общую прибыль от производства всей продукции. Ограничения выражают условие, при котором потребление ресурса i-го вида не должно превышать запаса этого ресурса (bi). Условия неотрицательности переменных вытекают из смысла переменной xj: количество продукции не может быть отрицательным.

Канонической называется следующая форма записи ЗЛП:

Чтобы привести к виду равенства ограничение вида

в левую часть неравенства прибавляют дополнительную переменную:

.

Аналогично, чтобы привести к каноническому виду ограничение вида

из левой части неравенства вычитают дополнительную переменную:

.

Дополнительные переменные вводятся в целевую функцию с коэффициентами, равными 0:

.

Таким образом, задача может быть записана в следующем каноническом виде:

Экономический смысл переменных yi (i = 1, …, m) следующий: это остатки ресурсов каждого вида. Если при оптимальном решении какой-либо ресурс будет использован полностью, то ограничение исходной задачи (13) будет выполнено в виде равенства, а yi = 0. Такое ограничение в отчетах Exсel называется связанным.

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

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

оптимальный математический модель еxcel

Таблица 1. Математические модели исходной и двойственной задач

Эта задача составляется по следующим правилам:

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

В исходной задаче ограничения имеют знаки неравенств ««, а в двойственной — ««.

Каждому ограничению исходной задачи соответствует переменная двойственной задачи, а каждой переменной исходной задачи — ограничение двойственной задачи.

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

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

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

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

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

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

В отчетах Excel, получаемых с помощью надстройки Поиск решения, оптимальное значение двойственной переменной zi* называется теневой ценой, или множителем Лагранжа. Отметим, что теневая цена не есть некоторая реальная цена на рынке. Это лишь оценка значимости ресурса, вытекающая из конкретных условий задачи.

1-я теорема двойственности. Если существует единственное решение исходной задачи, то существует и единственное решение двойственной задачи, причем значения целевых функций на оптимальных решениях совпадают:

max F = min FД.

Эту теорему можно интерпретировать так: предприятию безразлично, производить ли продукцию по оптимальному плану X* и получить максимальную прибыль либо продать ресурсы по оптимальным ценам Z* и получить такую же сумму. Для всех других (неоптимальных) планов X и Z прибыль от выпуска продукции всегда меньше внутренней стоимости затраченных ресурсов. Таким образом, F < FД, а величина FД — F характеризует производственные потери.

Следствие (теорема об оценках). Двойственная оценка zi* (теневая цена) показывает, как изменится целевая функция исходной задачи при изменении ресурса bi на одну единицу:

F = bizi*.

Таким образом, по теневым ценам можно судить о том, насколько целесообразно изыскивать резервы для увеличения количества i-го ресурса: если соответствующая теневая цена равна нулю, то увеличение количества этого ресурса никак не повлияет на рост прибыли. С другой стороны, чем больше теневая цена ресурса, тем больше увеличится прибыль при увеличении количества этого ресурса на одну единицу. Поэтому тот ресурс, который имеет большую теневую цену, считается более дефицитным.

Однако эта теорема справедлива только тогда, когда при изменении количества ресурса bi значения переменных zi* в оптимальном плане двойственной задачи остаются неизменными. В отчете Excel по устойчивости можно получить границы изменения bi (bи b+), в пределах которых теневая цена есть коэффициент увеличения (уменьшения) целевой функции исходной задачи при изменении доступного количества ресурсов.

Понятие нормированной стоимости. Ограничения двойственной задачи так же, как и исходной, можно привести к виду равенства:

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

Если это ограничение выполняется в виде равенства, то оценка затраченных ресурсов равна прибыли и потерь нет. В этом случае vj = 0.

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

.

В отчетах Excel оптимальное значение дополнительной двойственной переменной vj* называется нормированной, или редуцированной, стоимостью.

2-я теорема двойственности (теорема о дополняющей нежесткости). Оптимальные решения исходной и двойственной задач связаны соотношениями

zi* yi* = 0;

vj* xj* = 0.

Эта теорема означает, что между переменными исходной и двойственной задач существует взаимосвязь.

Рассмотрим связь yi* (остаток ресурса i-го вида) и zi*(теневую цену ресурса i-го вида).

Если yi* = 0, то i-й ресурс использован полностью. Следовательно, он ограничивает дальнейшее увеличение целевой функции, является дефицитным. При увеличении количества этого ресурса может быть произведено больше продукции, следовательно, возрастет прибыль. Соответствующая теневая цена zi* > 0.

Если же yi* > 0, то имеется остаток ресурса i-го вида, т. е. ресурс не дефицитен. Увеличение количества этого ресурса не вызовет увеличение прибыли. Соответствующая теневая цена zi* = 0.

Рассмотрим связь xj* (оптимальный объем производства изделий j-го типа) и vj* (производственные потери на одну единицу изделия j-го типа).

Если xj* > 0, т. е. j-е изделие вошло в оптимальный план производства, то соответствующие потери для этого изделия составляют0: vj* = 0.

Если же xj* = 0, т. е. изделие не вошло в оптимальный план производства, то это произошло потому, что данный вид продукции убыточен, т. е. соответствующие потери vj* > 0.

Свойство нормированной стоимости. Нормированная стоимость vj* показывает, насколько уменьшится целевая функция при принудительном выпуске одной единицы продукции j-го типа.

Пусть, например, продукция k-го вида не вошла в оптимальный план производства, т. е. xk* = 0. Однако существует некоторое плановое задание, предписывающее выпуск этого вида продукции в количестве Tk единиц. Тогда при производстве этого невыгодного вида продукции на него будут оттянуты ресурсы, и выгодной продукции будет выпущено меньше. Целевая функция (общая прибыль) уменьшится, причем это уменьшение можно количественно измерить:

F = Tk vk*.

Следует отметить, что равенство справедливо только в том случае, когда плановое задание Tk не нарушает номенклатуру остальных выпускаемых изделий, т. е., кроме «принудительно производимого» k-го изделия, ассортимент остальных выпускаемых «выгодных» изделий не изменится, а изменится только их количество. Определить предельную величину Tk, при которой равенство (22) справедливо, можно экспериментально.

Анализ устойчивости оптимального решения. Основные исходные данные рассматриваемой задачи — это запасы ресурсов (bi, где i = 1, …, m) и величина прибыли на одну единицу выпускаемой продукции (Cj, где j = 1, …, n). Исследовать устойчивость — значит определить пределы изменения исходных данных, при которых не изменяется решение или же его структура. Отчет Excel по устойчивости дает допустимое увеличение и допустимое уменьшение по целевому коэффициенту Cj, при которых решение задачи остается прежним. Кроме того, в отчете по устойчивости приведены пределы увеличения и уменьшения правых частей ограничений bi, при которых прежней остается структура решения. Под неизменностью структуры решения понимается следующее: те ресурсы, которые были дефицитными в исходном решении, остаются дефицитными и в новом оптимальном решении, хотя само решение (количество выпускаемых изделий) и значение целевой функции могут изменяться.

2. Постановка задачи Производственно-коммерческая фирма «Альтаир» осуществляет сборку трех видов изделий, располагая при этом комплектующими 4 типов А, Б, В и Г, соответственно в количествах 18, 16, 8 и 6 тыс. шт. Нормы затрат каждого вида комплектующих на 1 ед. изделия первого вида составляет соответственно 1, 2, 1, 0 тыс. шт.; второго вида — 2, 1, 1, 1 и третьего вида — 1, 1, 0, 1 тыс. шт. Прибыль от реализации 1 ед. изделия первого вида равно 3 тыс. у.е., второго — 4 тыс. у.е., третьего — 2 тыс. у.е.

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

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

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

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

3) Решить исходную задачу с помощью надстройки MS Excel «Поиск решения» и получить отчеты по устойчивости и по результатам.

4) На основе анализа этих отчетов выписать оптимальные значения основных и дополнительных переменных исходной и двойственной задач и ответить на вопросы:

1. Какие виды изделий и в каком количестве необходимо собирать фирме? Какой величины прибыль будет иметь ПКФ «Альтаир» при таком плане производства?

2. Определите дефицитность комплектующих изделий.

3. Какой из вариантов окажет большее влияние на изменение размера максимальной прибыли: а) закупить дополнительно 6 тыс.шт. комплектующих типа А; б) закупить дополнительно 3 тыс. шт. комплектующих типа Б; в) закупить дополнительно 2 тыс. ед. комплектующих типа В; или г) закупить дополнительно 2 тыс. ед. комплектующих типа Г?

4. Фирме предлагают начать сборку нового (четвертого) вида изделия, нормы затрат на 1 ед. которого равны соответственно 1, 2, 2, 0 тыс. шт. комплектующих типа А, Б, В и Г, а прибыль составляет 15 тыс. у.е. за единицу. Целесообразно ли введение в план производства фирмы этого изделия?

5. Цены на изделия фирмы могут колебаться в течение отчетного периода в связи с изменением спроса на рынке. Как повлияет на прибыль снижение цены на изделие первого вида на 0,5 тыс. у.е.?

3. Математическая модель задачи Составим математическую модель задачи.

Количество изделия I обозначим х1, II — х2, III — х3.

Доход от реализации изделия I составляет 3×1 тыс. усл. ед., изделия II 4×2 тыс. усл. ед., товара III — 2×3 тыс. усл. ед., общий доход — соответственно:

F 3×1 + 4×2+ 2×3.

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

F 3×1 + 4×2+ 2×3 max.

Количество комплектующего ограничено 18 тыс.шт., при этом их расходуется на производство изделия I —1×1, на производство изделия II — 2×2, на производство изделия III — 1×3. Поскольку количество израсходованного комплектующего не должно превышать его запаса, можно записать следующее ограничение:

1x1 + 2×2+ 1×3 18.

Аналогично записываются ограничения для других ресурсов:

2x1 + 1×2 + 1×3 16

11 + 1×2 8

1x2 + 1×3 6

Таким образом, математическая модель задачи выглядит следующим образом:

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

Приведем исходную задачу к каноническому виду:

Дополнительные переменные (yi) есть остатки ресурсов каждого вида.

Составим двойственную задачу к математической модели Двойственные переменные — это оценки ресурсов задачи (теневые цены).

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

4. Решение задачи в Excel с помощью надстройки Поиск решения Для решения задачи в Excel с помощью надстройки Поиск решения сформируем экран так, как показано на рисунке:

Рисунок 1. Таблица данных для поиска решения

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

Рисунок 2. Диалоговое окно надстройки «Поиск решения» с реализацией задачи

Затем активизируем процесс поиска и после его окончания в окне Результаты поиска решения выделим все три типа отчетов. Нажатие кнопки OK приведет к созданию новых листов рабочей книги: «Отчет по результатам», «Отчет по устойчивости» и «Отчет по пределам». Результаты решения на исходном рабочем листе будут сохранены.

Оптимальные значения всех переменных исходной и двойственной задач с пояснением этих значений в терминах постановки задачи.

Максимальная прибыль в 33 тыс. усл. ед., достигается при сборке изделий:

Изделие I в количестве 5 шт.,

Изделие II в количестве 3 шт.,

Изделие III в количестве 3шт.,

При этом затрачено комплектующего:

Комплектующее А: 14 тыс.шт.;

Комплектующее Б: 16 тыс.шт.;

Комплектующее В: 8 тыс.шт.;

Комплектующее Г: 6 тыс.шт.;

Не использовано комплектующего (оптимальные значения дополнительных двойственных переменных yi):

Комплектующее А: 4 тыс.шт.;

Комплектующее Б: 0 тыс.шт.;

Комплектующее В: 0 тыс.шт.;

Комплектующее Г: 0 тыс.шт.;

Теневая цена (оптимальные значения дополнительных двойственных переменных zi):

Комплектующее А: 0;

Комплектующее Б: 0,5;

Комплектующее В: 2;

Комплектующее Г: 1,5;

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

х1 = 5 (кол-во изделия А) х2 = 3 (кол-во изделия В) х3= 3 (кол-во изделия С).

Оптимальная прибыль от реализации (целевая функция) составит F = 33 у.е. (Приложение 2).

Теневая цена для количества используемого комплектующего: z1=0; z2=0,5; z3=2 (Приложение 3).

1. Какие виды изделий и в каком количестве необходимо собирать фирме? Какой величины прибыль будет иметь ПКФ «Альтаир» при таком плане производства?

Изделие I в количестве 5 шт.,

Изделие II в количестве 3 шт.,

Изделие III в количестве 3шт.,

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

2. Определите дефицитность комплектующих изделий.

В данном случае дефицитными изделиями являются:

Комплектующее Б, комплектующее В, комплектующее Г, так как эти виды комплектующих израсходованы полностью.

3. Какой из вариантов окажет большее влияние на изменение размера максимальной прибыли: а) закупить дополнительно 6 тыс.шт. комплектующих типа А; б) закупить дополнительно 3 тыс. шт. комплектующих типа Б; в) закупить дополнительно 2 тыс. ед. комплектующих типа В; или г) закупить дополнительно 2 тыс. ед. комплектующих типа Г?

При вариантах прибыль составит:

А) 33 тыс. усл. ед.

Б) 34,5 тыс. усл. ед.

В) 37 тыс. усл. ед.

Г) 36 тыс. усл. ед.

Правильным ответом будет вариант В, так как в этом случае мы получим максимальную прибыль.

4. Фирме предлагают начать сборку нового (четвертого) вида изделия, нормы затрат на 1 ед. которого равны соответственно 1, 2, 2, 0 тыс. шт. комплектующих типа А, Б, В и Г, а прибыль составляет 15 тыс. у.е. за единицу. Целесообразно ли введение в план производства фирмы этого изделия?

1 * 0 + 2 * 0,5 + 2 * 2 + 0 * 1,5 = 5

Поскольку оценка ресурсов меньше прибыли (5 < 15), то данный вид изделия будет выгоден.

Рисунок 3. План производства фирмы

Введение

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

5. Цены на изделия фирмы могут колебаться в течение отчетного периода в связи с изменением спроса на рынке. Как повлияет на прибыль снижение цены на изделие первого вида на 0,5 тыс. у.е.?

При снижении цены па первую продукцию, на 0,5 у.е. мы получим итоговую прибыль в 30,5 тыс. у.е.

2,5 * 5 + 3 * 4 + 3 * 2 = 30,5

При этом план производства не меняется.

Рисунок 4. План производства при другом коэффициенте

Заключение

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

1. Изучена теория двойственности;

2. Составлена математическая модель задачи;

3. Решены задачи с помощью надстройки «Поиск решения» и получены отчеты;

4. Произведен анализ отчетов.

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

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

Список использованных источников

Автоматизация решения задач линейного программирования. Пособие для студентов дневной формы обучения экономических специальностей.- В. В. Бондарева, О. И. Еськова — Гомель, БТЭУ, 2003 г.

Еськова О.И. Экономико-математические методы и модели: курс лекций для студентов дневной формы обучения экономических специальностей — Гомель, БТЭУ, 2006 г.

Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. — М: Вузовский учебник, 2007 г.

Экономико-математические методы и модели. Компьютерные технологии решения: Учеб. Пособие.- И. Л. Акулич, Е. И. Велесько и др. — Мн.: БГЭУ, 2003.

Экономико-математические методы и модели: Учеб. Пособие.- под ред.С. Ф. Миксюк, В. Н. Комкова.- Мн.:БГЭУ, 2006.

Зайцев, М. Г. Методы оптимизации управления для менеджеров. Компьютерно-ориентированный подход: учеб. пособие для вузов / М. Г. Зайцев. — М. :Дело, 2002.

Костевич Л. С. Математическое программирование: Учеб.- практ. Пособие. — Мн.: БГЭУ, 2003.

Методические требования к содержанию и оформлению курсовых работ — Л. П. Харлап, Е. М. Сибагатова — Гомель, БТЭУ, 2004

http://journal.vlsu.ru/index.php?id=1542