Определение производственного плана предприятия при наличии различных критериев

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

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

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

Построить ЭММ однокритериальных и многокритериальных задач

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

Решить две однокритериальные задачи с параметром в целевой функции и в правой части ограничений.

Решить многокритериальные задачи (МКЗ) заданными методами.

Анализ решения МКЗ с указанием и обоснованием приоритетов, расчет рентабельности.

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

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

Методы решения задач параметрической оптимизации

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

Параметры м и л могут изменяться в интервале (-?, ?), однако из содержательной постановки задачи обычно следует их принадлежность более узкому интервалу.

Методы решения многокритериальных задач (МКЗ).

Многокритериальная задача линейной оптимизации (МКЗ ЛО) записывается в следующем виде:

Здесь - вектор переменных.

- матрица системы ограничений.

- вектор правых частей ограничений

- k-й критерий (целевая функция).

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

Метод сверстки критериев. Суть метода - сведение имеющего множества критериев к одному скалярному критерию, отражающую комбинированную (общую) цель системы критериев.

Каждому из критериев приписываются весовые коэффициенты ai , причем на эти коэффициенты накладывается требование:

Сверстка критериев представляет собой функцию следующего вида:

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

,

Где

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

Замечание 1. Если все критерии однородны, т.е. выражены в одинаковых единицах измерения, то можно не нормировать целевые функции, а в задачи применять свертку.

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

Замечание 3. Весовые коэффициенты , лицо принимающее решение (ЛРП) может изменять по своему усмотрению с целью получения наиболее приемлемого плана.

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

Предположим, что - главный (наиболее важный для ЛРП) критерий. Пусть - нижняя граница j-го критерия, устанавливаемая ЛРП. При этом .

Тогда решение будет:

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

Чтобы нелинейный критерий привести к линейному виду, введем новую переменную . Таким образом, в данном методе решение МКЗ ЛО определяется в результате нахождения оптимального плана следующей задачи ЛО:

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

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

Пусть . Сначала решает задача ЛО:

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

Для оптимального плана задачи анализируется значение критериев . Если значение устраивает ЛРП, то план принимается за лучшее решение. В противном случае вводится следующая уступка , по второму критерию и решается задача, и так далее пока решение не будет удовлетворять ЛРП.

Экономико-математическая модель.

Переменные:

х1 - количество изделий вида А, шт.

х2 - количество изделий вида В, шт.

х3 - количество изделий вида С, шт.

Целевая функция:

Минимум себестоимости изготовления изделий, тыс. рублей

L(х) = 10х1 + 17х2 + 18х3 > min

Максимум получения прибыли, тыс. рублей

C(х) = 4х1 + 2х2 + 4х3 > max

Максимум получаемой выручки, тыс. рублей

M(х) = 14х1 + 19х2 + 22х3 > max

Ограничения:

По ресурсу R1 2х1 + х2 + 3х3 ? 27

По ресурсу R2 2х1 + х2 + 4х3 ? 35

По ресурсу R3 3х1 + 2х2 + 6х3 = 44

Не отрицательность переменных х1, х2, х3 ? 0

Целочисленности х1, х2, х3 - целые

Канонический вид.

L(х) = - 10х1 - 17х2 - 18х3 > max

C(х) = 4х1 + 2х2 + 4х3 > max

M(х) = 14х1 + 19х2 + 22х3 > max

2х1 + х2 + 3х3 + х4 = 27

2х1 + х2 + 4х3 х5 = 35

3х1 + 2х2 + 6х3 = 44

х1, х2, х3 х4 х5 ? 0

х1, х2, х3 - целые

Решение однокритериальной задачи симплекс - методом. Послеоптимизационный анализ. Целочисленное решение.

Задание: решить однокритериальную задачу ЛП с целевой функцией «выручка» симплекс-методом. Выполнить послеоптимизационный анализ. Целочисленное решение получить методом Гомори и методом ветвей и границ.

С(х) = 14Х1 + 19Х2 + 22Х3 max - выручка

Ограничения по запасам:

Х1+Х2+3Х3 <= 27

2X1+3X2+4X3 <= 35

3X1+2X2+4X3 = 44

Х1,Х2,Х3 >= 0

Решаем задачу при условии максимизации выручки симплекс методом

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

С(х) = 14Х1 + 19Х2 + 22Х3 max

Ограничения по запасам:

Х1+Х2+3Х3 + Х4 = 27

2X1+3X2+4X3 + Х5 = 35

3X1+2X2+4X3 = 44

Х1, Х2, Х3, Х4, Х5 >= 0

Вводим искусственный базис.

Х1+Х2+3Х3 + Х4 = 27

2X1+3X2+4X3 + Х5 = 35

3X1+2X2+4X3 + Х6 = 44

Х1, Х2, Х3, Х4, Х5, Х6 >= 0

Вводим новую целевую функцию(с искусственным базисом).

С(х) = -Х6 max

Ответ: С(х) = 418; Х*=(0; 22; 0)

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

Отчет по устойчивости

Для того, чтобы получить максимальную выручку от реализации произведенной продукции, равную 418 тыс. руб., нужно изготавливать 0 шт. изделия А, 22 шт. изделия В и 0 шт. изделия С.

Допустимое увеличение, допустимое уменьшение таблицы «изменяемые ячейки» - показывает границы изменений коэффициентов целевой функции, при которых сохраняется набор переменных, входящих в оптимальное решение. Например, если стоимость изделия А увеличится(из-за каких-либо изменений на рынке) на 14,5 и более единиц, то изменится набор переменных, входящих в оптимальное решение. Уменьшаться цена этого изделия может до нуля, без изменения структуры плана. Цена изделия В может уменьшаться на 9,6667 ед. и неограниченно увеличиваться без изменения структуры плана. Цена на продукт С может изменяться в диапазоне от 0 до 35 без изменения структуры плана.

Результирующее значение таблицы ограничений - значение левой части ограничения при оптимальном плане. Т.е. сколько фактически использовано ресурса. Например, ресурса R1 - 22 ед., ресурса R2 - 22, а ресурса R3 - 44.

Теневая цена - изменение целевой функции при изменении ресурса на 1 единицу. Теневая цена недефицитного ресурса будет равна 0. Например, изменения количества ресурса R1 или ресурса R2 не повлияет на значение целевой функции (= 0), а увеличение запаса ресурса R3 приведет к увеличению выручки на 9,5 единиц. Допустимое увеличение, допустимое уменьшение таблицы ограничений - показывает, насколько можно изменить правую часть ограничения до того момента пока это будет влиять на структуру целевой функции. Например, увеличение ресурсов R1 и R2 никак не повлияет на целевую функцию. Уменьшение же ресурса R1 более чем на 5 единиц или ресурса R2 более чем на 13 единиц приведет к изменению структуры плана. Ресурс R3 может изменяться в диапазоне от 10 до 44 единиц без изменения структуры плана.

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

Решить две однокритериальные задачи при следующих условиях.

Параметр в целевой функции

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

Таблица№1

Ввод данных

Таблица№2

Таблица№3

Интервалы

С этой таблицей я и буду работать, в ней мне необходимо пересчитать значения. Моя целевая функция имеет вид C(X) = 14X1+19X2+22X3 стремится к max. Добавив параметр, я получаю:

(14-Л)X1+(19+Л)X2+(22+2Л)X3, (Л - параметр лямбда).

Л максимальное = 14

Л минимальное = -11

Произвожу пересчет верхней и нижней границ моего интервала, подставив, вместо Х1, Х2, Х3 - 0, 22, 0, соответственно, поскольку X*(0,22,0). В итоге я получаю, что М=726, а -М=176.

Вывод: Если цена на первый товар колеблется в интервале [0;14], то вторая цена - [19;33], третья - [22;50], то целевая функция изменяется в этом же интервале. При изменении цен (первая уменьшится на единицу, вторая увеличится на единицу, а третья увеличится на 2 единицы), целевая функция увеличится на 22.

График

Таблица№4

Данные для графика

Параметр в правой части ограничений

Задание: предприятие может использовать не более чем 3(x+y+z)+2? единицы ресурса R1 и не более чем 4x+3y+4z-? единицы ресурса R2, где ? - некоторый параметр. Для каждого возможного значения ? определить план производства изделий, при котором выручка от реализации является максимальной.

С(х) = 14Х1 + 19Х2 + 22Х3 max

3х1 + х2 + 3х3 ? 27+2t

2х1 + 3х2 + 4х3 ? 35-t

х1, х2, х3 ? 0

Выводы

В случае, если м будет находиться в интервале -? ? м ? -13,5, то задача не будет иметь решения.

Если м будет находиться в интервале -13,5 ? м ? -2,5, то выручка будет изменяться от 418 тыс. руб. до 0 тыс. руб., при этом запас ресурса R1 будет изменяться от 0 кг до 22 кг, а запас ресурса R2 будет изменяться от 37,5 кг до 48,5 кг.

Если м будет находиться в интервале -2,5 ? м ? 0, то выручка будет 418 тыс. руб., при этом запас ресурса R1 будет изменяться от 22 кг до 27 кг, а запас ресурса R2 будет изменяться от 37,5 кг до 35 кг

Если м будет находиться в интервале 0 ? м ? 13, то выручка будет 418 тыс. руб., при этом запас ресурса R1 будет изменяться от 27 кг до 53 кг, а запас ресурса R2 будет изменяться от 35 кг до 22 кг.

Если м будет находиться в интервале 13 ? м ? 35, то выручка будет изменяться от 418 тыс. руб. до 0 тыс. руб., при этом запас ресурса R1 будет изменяться от 53 кг до 97 кг, а запас ресурса R2 будет изменяться от 22 кг до 0 кг.

В случае если м будет находиться в интервале 35 ? м ? ?, то задача не будет иметь решения.

Решение многокритериальной задачи

параметрическая оптимизация критерий

Решение многокритериальной задачи осуществлялось относительно следующей целевой функции:

Выручка (тыс. руб.):

f1(x) = 14x1 + 19x2 + 22x3 > max

2x1 + x2 + 3x3 ? 27

2x1 + x2 + 4x3 ? 35

3x1 + 2x2 + 6x3 = 44

x1, x2, x3 ? 0

С помощью надстройки MS Excel «Поиск решения» был получен оптимальный план указанной задачи: Х1* = (0; 22; 0), f1(Х1*) = 418.

После этого была решена однокритериальная задача на функцию себестоимости с добавлением дополнительного ограничения на предшествующий критерий - функцию выручки f1(x):

Cебестоимость (тыс. руб.):

f2(x) = 10x1 + 17x2 + 18x3 > min

2x1 + x2 + 3x3 ? 27

2x1 + x2 + 4x3 ? 35

3x1 + 2x2 + 6x3 = 44

14x1 + 19x2 + 22x3 ? 14•0+19•22+22•0

x1, x2, x3 ? 0

При решении данной задачи с помощью надстройки MS Excel «Поиск решения» был получен оптимальный план указанной задачи: Х1* = (0; 22; 0),

f2(Х1*) = 374.

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

Пусть h1 = 68 (максимум выручки составит 350 тыс. руб.), тогда:

f2(x) = 10x1 + 17x2 + 18x3 > min

2x1 + x2 + 3x3 ? 27

2x1 + x2 + 4x3 ? 35

3x1 + 2x2 + 4x3 = 44

14x1 + 19x2 + 22x3 ? 350

x1, x2, x3 ? 0

При решении данной задачи с помощью надстройки MS Excel «Поиск решения» был получен оптимальный план указанной задачи: Х1* = (4,69; 14,97; 0),

f2(Х1*) = 301,31.

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

Пусть h2 = 88 (максимум выручки составит 330 тыс. руб.), тогда:

f2(x) = 10x1 + 17x2 + 18x3 > min

2x1 + x2 + 3x3 ? 27

2x1 + x2 + 4x3 ? 35

3x1 + 2x2 + 4x3 = 44

14x1 + 19x2 + 22x3 ? 330

x1, x2, x3 ? 0

При решении данной задачи с помощью надстройки MS Excel «Поиск решения» был получен оптимальный план указанной задачи: Х3* = (6,07; 12,9; 0),

f2(Х3*) = 279,9.

Пусть h3 = 108 (максимум выручки составит 310 тыс. руб.), тогда:

f2(x) = 6x1 + 10x2 + 12x3 > min

2x1 + x2 + 3x3 ? 24

2x1 + 2x2 + 4x3 ? 30

3x1 + 2x2 + 4x3 = 34

10x1 + 13x2 + 14x3 ? 120

x1, x2, x3 ? 0

При решении данной задачи с помощью надстройки MS Excel «Поиск решения» был получен оптимальный план указанной задачи: Х4* = (6,9; 11,6; 0),

f2(Х4*) = 267,1.

Вывод: при увеличении уступки для критерия выручки, значение критерия себестоимости уменьшается. При увеличении уступки объем выпуска изделий вида А увеличивается, а изделий вида В - снижается, изделия вида С не производятся.

Задание 6.4. Решение многокритериальной задачи модифицированным методом идеальной точки

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

Выручка (тыс. руб.):

f1(x) = 14x1 + 19x2 + 22x3 > max

Cебестоимость (тыс. руб.):

f2(x) = 10x1 + 17x2 + 18x3 > min

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

F1* = 418

F2* = 132

С(х) = x4 > min

2x1 + x2 + 3x3 ? 27

2x1 + x2 + 4x3 ? 35

3x1 + 2x2 + 6x3 = 44

-418 +14x1 + 19x2 + 22x3 ? x4

132 - 10x1 - 17x2 - 18x3 ? x4

x1, x2, x3, x4 ? 0

2x1 + x2 + 3x3 ? 24

2x1 + x2 + 4x3 ? 30

3x1 + 2x2 + 6x3 = 34

14x1 + 19x2 + 22x3 - x4 ? -418

-10x1 - 17x2 - 18x3 - x4 ? -132

x1, x2, x3, x4 ? 0

При решении данной задачи с помощью надстройки MS Excel «Поиск решения» был получен следующий оптимальный план, при котором значение каждого критерия не может быть улучшено без ухудшения значения другого критерия: Х* = (0; 0; 7,33; 579,33), при этом f1(Х*) = 161,33, f2(Х*) = 132.

Задание 7.

Сведение результатов МКЗ в таблицу

Выводы по работе

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

Для производства трех видов изделий А, В и С, используя при этом три основных вида ресурсов R1, R2 и R3 наилучший вариант для предприятия это производить продукцию А в размере 10 шт, продукцию В в размере 7 шт,а С - 0 шт., при этом себестоимость изделий будет составлять 219 тыс. рублей, прибыль - 54 тыс. рублей, а выручка - 273 тыс. рублей.

Список использованной литературы:

1. Кузменков В.А. Математические методы и модели исследования операций. Параметрическая, многокритериальная и целочисленное оптимизация: учеб. Пособие / В.А. Кузменков, В.Н. Юрьев. - 2-е изд., перераб. И доп. - СПб.: Изд-во Политехн. Ун-та, 2011. - 120 с.

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