Конструирование математической модели
Эвристическое решение
Тарную дощечку возьмем 17 м3. Расход сырья на производство 17 м3 тарной дощечки и 20 м3 техн щепы составит: технологических дров - 20x1+17х3,5 = 79,5 м3; отходов лесопиления - 20x0,5+17х0,5 = 18,5 м3. Остаток неиспользованного сырья составляет: по технологическим дровам 80 – 79,5 = 0,5 м3; По отходам лесопиления 30 – 18,5 = 11,5 м.
Доход от продажи 20 м технологической щепы (ограничение по спросу на этот объем выполняется) и 17 м тарной дощечки составит 20x5+17x10=270 рублей.
Геометрическое решение поставленной задачи
Конструирование математической модели
Построение (конструирование) математической модели производится в следующем порядке:
обозначение переменных: а) хш - сменный объем производства технологической щепы, м3; б) хд - сменный объем производства тарной дощечки, м3; в) у - функция цели;
целевая функция разрабатывается исходя из того, что сменный доход от реализации технологической щепы равняется 5хщ (5 рублей - цена реализации 1 м3 технологической щепы; хщ - объем ее производства в смену); аналогично - доход от реализации тарной дощечки 10хд; общий доход (целевая функция) равняется сумме двух доходов у = 5хщ + 10хд;
построение ограничений производится на основе содержательной сущности задачи, в которой отражены:
а) ограничения на расход сырья:
1хщ + 3,5хд<=80,
0,5хщ + 0,5хд <= 30;
б) ограничения на объем реализации (поставок):
хд <= 20;
в) ограничения на неотрицательность переменных управления хщ и хд, поскольку объемы производства не могут быть отрицательными:
хщ>=0; хщ >= 0.
Итак, на основании изложенного, математическая модель сформирована, и задача оптимизации ставится следующим образом:
определить сменные объемы производства технологической щепы хщ и тарной дощечки хд такие, при которых функция цели достигает максимума:
у = 5хщ + 10хд -> шах, (1)
и удовлетворяются ограничения
1хщ+3,5хд<=80; (2)
0,5хщ + 0,5хд <= 30; (3)
хщ>=хд (4)
хд<=20; (5)
хд>=0; (6)
хщ>=0. (7)
Графическое представление функции цели строится на основе выражения (1) и является плоскостью Р, уходящей в бесконечность при неограниченном возрастании хщ и хд (рис. 1). При наличии ограничений вида (2)-(7) возможные решения - значения функции цели и объемы производства продукции - могут принадлежать лишь тем точкам плоскости Р, в которых одновременно удовлетворяются все ограничения. Совокупность этих точек определяет область допустимых решений (ОДР).
Построение этой области проводится в системе координат хщ/хд (рис. 2), где ось у направлена от нас. Первоначально строятся линии уравнений, полученных из неравенств (2)—(7). Для этого используется прием замены знаков неравенств на знаки равенств, а затем посредством подстановки координат любых точек, лежащих по ту и иную сторону линий, определяется область, в которой все точки соответствуют тому или иному неравенству.
| Рис. 1. Графическая интерпретация функции цели (дохода) |
Например, для ограничения (2) определение области его действия производят следующим образом: выбирают координаты точки с любой стороны построенной линии ограничения (2), наиболее удобно использовать точку с координатами (0,0) -хщ= 0, 0, и, подставив эти координаты в левую часть неравенства (2), проверяют условие соблюдения неравенства 1*0 + 3,5*x0 < 80. Поскольку неравенство при данных координатах соблюдается, то область действия ограничения (2) находится с той же стороны линии, что и выбранная точка. В противном случае, то есть при невыполнении условия неравенства, область действия ограничения располагается с противоположной стороны линии от выбранной точки. Направление, в котором ограничения удовлетворяются, показывается стрелкой с номером данного ограничения (рис. 2).
| хд |
| хщ |
| ОДР |
| А |
| С |
| B |
| F |
| К |
| D |
Рис. 2 Графическая интерпретация области допустимых решений и процедуры поиска оптимального решения
Аналогичный прием графической интерпретации, но для иной задачи. Построенная область допустимых решений показана на рисунке. Здесь многоугольник ABCD является областью допустимых решений. Их количество бесконечно, но среди них находится одно, которое является наилучшим исходя из заданного дохода, то есть оптимальным. Поиск оптимального решения производится посредством определения направления, в котором возрастает функция цели у = 5хщ+10хд.
Направление возрастания функции цели находят посредством последовательного построения линий ее уравнения на рисунке для заданных конкретных значений у.
На рисунке показаны линии функции цели при= 8, 16, 32 тыс. рублей в смену, оценивая которые, определяют направление возрастания целевой функции (дохода) и производят перемещение прямой у в этом направлении до достижения ею границы перехода в область недопустимых решений. Этой границей на рисунке является точка пересечения прямых (2) и (3), - С Значения объемов хщ и хд в оптимальной точке С определяются решением системы уравнений, описывающих прямые (2) и (3):
1хщ + 3,5хд=80;
0,5хщ+ 0,5хд=30.
Результат решения системы уравнений : хд = 8 м3; хщ = 52 м3.
При таких значениях сменных объемов производства технологической
щепы и тарной дощечки доход от их реализации у = 5*52+10*8 =
= 340 рублей в смену.
По результатам эвристического решения доход составлял 270 рублей. Сопоставляя итоги эвристического и геометрического решения, отметим, что наш выбор в первом случае оказался неэффективным сравнительно с выбором, реализованным на основе геометрического решения. Величина потерь по доходу составила 70 рублей в смену. В год эта сумма при двухсменном режиме работы и количестве рабочих дней в году,
равном 250, составит 70x2x250=35000 рублей. Вывод очевиден.
Анализ на чувствительность
Первая задача анализа на чувствительность
Она подразделяется на две подзадачи.
В этой связи задача анализа на чувствительность может формулироваться следующим образом: а) определение предельно допустимого увеличения объема дефицитного ресурса при одновременном улучшении оптимального решения; б) определение предельно допустимого снижения объема недефицитного ресурса, не ухудшающего оптимального значения целевой функции.
Дефицитными являются ресурсы сменных объемов производства технологических дров и отходы лесопиления, поскольку линии их ограничений, описываемые выражениями (2) и (3), образуют оптимальную точку С. Недефицитными являются ресурсы сменных объемов (спроса) технологической щепы и тарной дощечки, описываемые ограничениями (4) и (5) и соответствующими линиями.
В соответствии с изложенным, поставленные ранее два вопроса формулируются следующим образом. Подзадача А: на сколько можно увеличить сменный объем производства технологических дров или их сменных запасов и отходов лесопиления для улучшения полученного оптимального значения y Подзадача В: на сколько можно снизить сменные объемы реализации (спрос) технологической щепы и тарной дощечки без ухудшения полученного оптимального решения в точке С?
Решение подзадачи А проводится в следующем порядке.
Определим первоначально объем допустимого увеличения ресурса технологических дров. Прямая (2) перемещается вверх параллельно самой себе до точки К(ограничение (3)). В точке К ограничение (2) становится связывающим (дефицитным), и оптимальному решению соответствует точка К, а многоугольник АКDF становится пространством допустимых решений. При этом ограничение (2') - технологические дрова - становится избыточным, и любой дальнейший рост запаса технологических дров не влияет ни на пространство допустимых решений, ни на оптимальное решение. В этой связи поднимать уровень запасов технологических дров выше точки К не рационально, поскольку в сложившейся ситуации возникает проблема утилизации избыточных запасов.
Предельный уровень запасов технологических дров определяется следующим образом. Определяются координаты точки К из системы уравнений, описывающих ограничения, линии (2) и (5),
0,5хщ + 0,5хд=30;
хд=20
решив которую, имеем хщ = 40 м3 . Затем, подставив координаты точки К в левую часть уравнения (2), определяем максимально допустимый запас технологических дров: 1хщ+3,5хД = 110 м3. Величина допустимого увеличения объема технологических дров по сравнению с прошлым составляет 30 м3.
Определим объем допустимого увеличения ресурса отходов лесопиления. Прямая (3) перемещается вверх параллельно самой себе до точки F. В точке F ограничение (3) становится связывающим (дефицитным), и оптимальному решению соответствует точка F, а многоугольник АFCD становится пространством допустимых решений. При этом ограничение (3') – отходы лесопиления - становится избыточным, и любой дальнейший рост запаса отходов лесопиления не влияет ни на пространство допустимых решений, ни на оптимальное решение. В этой связи поднимать уровень запасов отходов лесопиления выше точки F не рационально, поскольку в сложившейся ситуации возникает проблема утилизации избыточных запасов.
Предельный уровень запасов отходов лесопиления определяется следующим образом. Определяются координаты точки F из системы уравнений, описывающих ограничения, линии (2) и (Охщ),
1хщ + 3,5хд=80;
хд=0
решив которую, имеем хщ = 80 м3, хд = 0 м3. Затем, подставив координаты точки F в левую часть уравнения (3), определяем максимально допустимый запас отходов лесопиления: 0,5хщ+0,5хД = 40 м3. Величина допустимого увеличения объема технологических дров по сравнению с прошлым составляет 10 м3.
Решение подзадачи Б производится в ходе проверки на чувствительность при уменьшении правых частей несвязывающих ограничений (4) и (5). Ограничение и его линия (5) фиксируют предельный объем спроса (продаж) на тарную дощечку: если производить больше 20 м3, то произойдет затоваривание.
Прямую (5), не изменяя оптимальное решение, можно снижать до точки С. Координаты точки С определены ранее и составляют хщ= 52 м3; хд= 8 м3. Отсюда, предельная величина снижения объема продаж составит 8 - 20 = -12 м3. Дальнейшее снижение ресурса спроса на тарную дощечку нецелесообразно в связи с тем, что оно переходит в отрицательное значение.
Ограничение (4) характеризуют соответствие между объемами ежесменных продаж технологической щепы и тарной дощечки. Аналогично предыдущему, правую часть ограничения (4) можно уменьшать до тех пор, пока прямая (4) не достигнет точки С. Для удобства поиска величины снижения преобразуем неравенство (4) хщ -хд>= 0 в неравенство вида -хщ + хд=<0. Подставляя координаты точки С в преобразованное неравенство, имеем -52 + 8 = -44 м3, то есть 44 м3 может достигать разность между объемами реализации технологической щепы и тарной дощечки без ущерба для дохода.
Сведем результаты анализа в табл. 2.
| Номер п/п | Наименование ресурса | Тип ресурса | Максимальное изменение сменного объема запаса, м3 | Максимальное изменение сменного дохода от реализации, руб. |
| Технологические дрова | Дефицитный | 110-80 = +30 | 400-340=60 | |
| Отходы лесопиления | Дефицитный | 40-30 = +10 | 400-340=60 | |
| Объем реализации тарной дощечки | Недефицитный | 8-20= -12 | 340-340=0 | |
| Объем реализации технологич. щепы | Недефицитный | -44-0 =-44 | 340-340=0 |
Таблица 2 – Результаты решения подзадачи А и Б
Наиболее эффективное решение в данной ситуации принимается на основе результатов табл. 2 на выбор первая строка или вторая.
Вторая задача анализа на чувствительность
В процессе решения этой задачи получаем ответ на следующий вопрос: увеличение объема какого из ресурсов наиболее выгодно для предприятия? При ограничениях на затраты (любое, сколь угодно богатое, предприятие не имеет бесконечного множества свободных средств), связанных с дополнительным привлечением материальных и денежных средств, следует знать: какому из ресурсов отдать предпочтение при вложении дополнительных средств?
У нас дефицитные ресурсы технологические дрова и отходы лесопиления.
Z1=60/30=2
Z2=60/10=6
Z3=0/-12=0
Z4=0/-44=0
Можно сделать вывод, что для получения наибольшей отдачи от вложения дополнительных средств на развитие производства необходимо вкладывать их в развитие производства отходов лесопиления. Однако в рамках данной ситуации допускается увеличение сменного объема производства отходов лесопиления лишь до уровня 40 м3,
Вкладывать дополнительные средства в рекламную кампанию бессмысленно, так как спрос на оба вида конечной продукции избыточен (недефицитен), так же в технологические дрова.
Третья задача анализа на чувствительность
Решив эту задачу, ЛПР получает ответ на вопрос: в каких пределах допустимо изменение коэффициентов целевой функции? Изменение коэффициента целевой функции оказывает влияние на угол наклона прямой, представляющей эту функцию. Изменение угла наклона прямой в рамках анализа модели на чувствительность определяет следующие задачи: 1) нахождение диапазона изменения - увеличения и уменьшения - того или иного коэффициента целевой функции, при котором не происходит изменения оптимального решения; 2) на сколько следует изменить тот или иной коэффициент функции цели, чтобы сделать некоторый недефицитный ресурс дефицитным и наоборот, дефицитный ресурс сделать недефицитным?
Трансформируя изложенную постановку вопросов к нашему объекту - технологическому процессу производства технологической щепы и тарной дощечки и их реализации, - имеем: 1) каков может быть диапазон изменения цен на тарную дощечку и технологическую щепу, при котором не изменятся оптимальные объемы производства хщ и хд (иначе, при изменении цен в рамках этого диапазона доход, получаемый от производства и реализации хщ=52м3; хд= 8 м3 будет оставаться максимальным)?; 2) на сколько следует изменить цену на технологическую щепу или на тарную дощечку, чтобы сделать дефицитные ресурсы технологических дров или отходов лесопиления недефицитными и недефицитные ресурсы спроса на технологическую щепу или тарную дощечку дефицитными?
Для решения поставленных вопросов запишем целевую функцию в виде
y=CщХщ +СдХд, где Сщ и Сд - стоимость 1 м3 технологической щепы и тарной дощечки соответственно.
Для нахождения интервалов изменения цен (коэффициентов функции цели), при котором точка С остается оптимальной, оставим значение сд= 10 неизменным. Значение сщ можно увеличивать до тех пор, пока линия у не совпадет с линией (2), или уменьшать до совпадения у с линией (3), то есть углы линий (2) и (3), определяют допустимые углы изменения наклона линии у. Тангенс угла наклона линии у, проходящей через точку С с известным коэффициентом сд= 10, определяется как сщ/10, а для линий ограничений (2) и (3), исходя из их выражений, соответственно, как 1/3,5 и 0,5/0,5. Тогда минимальное значение сщ определяется из равенства сщ/10 = 1/3,5 (равенство углов определяет равенство их тангенсов). На основе изложенного сщ = 2,86 руб./м3. Аналогично определяется максимальное значение сщ. сщ/10 = 0,5/0,5; сщ = 10 руб./м3.
Интервал изменения Сщ, в котором точка С по-прежнему будет являться оптимальной 2,86 < Сщ < 10. Расчет пределов изменения цен на тарную дощечку проводится по аналогичной методике с использованием коэффициентов при хд в ограничениях Интервал изменения Сд, в котором точка С по-прежнему будет являться оптимальной 5 < Сд < 17,5.
В процессе торга о цене на щепу может фигурировать любая цифра в пределах от 28,57 рубля за кубометр, а также возможно позволить снижение цены от уровня средней рыночной (демпинг) в пределах выше представленного диапазона за счет каких-либо встречных обязательств партнера. Например, поставка дефицитной продукции с его стороны, увеличение объема потребления щепы и прочее.
Алгебраическое решение поставленной задачи
1. Стандартная форма линейных оптимизационных моделей
Для решения задачи ЛП необходимы алгебраические определения пространства решений и угловых точек. Для этой цели задача ЛП записывается в стандартной форме:
1) все ограничения записываются в виде равенств с неотрицательной правой частью;
2) значения всех переменных модели неотрицательны;
3) целевая функция подлежит максимизации или минимизации.
Постановка задачи в стандартной форме будет иметь следующий вид:
максимизировать при ограничениях
у = 5 хщ + 10 хд + 0s1 + 0s2 + 0s3 + 0s4 -» max
1хщ + 3,5 хд + s1 = 80
0,5хщ + 0,5хд + s2 = 30
-хщ + хд + s3 = 0
хд + s4 = 20
хщ, хд, s1, s2, s3, s4 >= 0.
2. Cимплекс-метод и процедура решения поставленной задачи на его основе.
Запись модели в стандартной форме имеет несколько преобразованный вид. Для удобства оперирования левая часть уравнения функции цели переносится в правую, и значения цен (коэффициентов) при переменных хщ и хд представляются рублях:
у - 5 хщ - 10 хд + 0s1 + 0s2 + 0s3 + 0s4 = 0
1хщ + 3,5 хд + s1 = 80
0,5хщ + 0,5хд + s2 = 30
-хщ + хд + s3 = 0
хд + s4 = 20
| Табличная форма решения задачи рационального распределения ресурсов сырья симплекс-методом | |||||||||||
| Номер итерации | Базисные переменные | У | Хщ | Xд | S1 | S2 | S3 | S4 | Решение | Отношение | Примечание |
| У | -5 | -10 | - | У-уравн | |||||||
| S1 | 3,5 | 80/3,5=22,86 | S1-уравн | ||||||||
| S2 | 0,5 | 0,5 | 30/0,5=60 | S2-уравн | |||||||
| S3 | -1 | 0/1=0 | S3-уравн | ||||||||
| S4 | 20/1=20 | S4-уравн | |||||||||
| У | -15 | - | У-уравн | ||||||||
| S1 | 4.5 | -3.5 | 80/4,5=17,78 | S1-уравн | |||||||
| S2 | -0.5 | 30/1=30 | S2-уравн | ||||||||
| Xд | -1 | - | S3-уравн | ||||||||
| S4 | -1 | 20/1=20 | S4-уравн | ||||||||
| У | 3,33 | -1,67 | 266,67 | - | У-уравн | ||||||
| Хщ | 0,22 | -0,78 | 17,78 | - | S1-уравн | ||||||
| S2 | -0,22 | 0,27 | 12,22 | 12,22/0,27=44 | S2-уравн | ||||||
| Xд | 0,22 | 0,22 | 17,78 | 17,78/0,22=80 | S3-уравн | ||||||
| S4 | -0,22 | -0,22 | 2,22 | - | S4-уравн | ||||||
| У | - | У-уравн | |||||||||
| Хщ | -0,4 | 2,8 | - | S1-уравн | |||||||
| S3 | -0,8 | 3,6 | - | S2-уравн | |||||||
| Xд | 0,4 | -0,8 | - | S3-уравн | |||||||
| S4 | -0,4 | 0,8 | - | S4-уравн |
3. Оптимальное решение. Величина дохода у = 340 рублей при объемах производства и реализации в смену: технологической щепы хщ= 52 м3, тарной дощечки хд= 8 м3
Компьютерное решение поставленной задачи в математических программных средах
| Ресурсы Продукция | производство в смену тех. щепы и тарной дощечки | Технол. дрова | Отходы лесопиления | Спрос на тарную дощ. | Соответствие спроса по тех. щепе | Доход от реализации, руб |
| Технол. Щепа | 1,00 | 1,00 | 0,50 | 0,00 | -1,00 | 5,00 |
| Тарная дощечка | 1,00 | 3,50 | 0,50 | 1,00 | 1,00 | 10,00 |
| Текущие значения объемов используемого сырья и дохода | 4,50 | 1,00 | 1,00 | 0,00 | 15,00 | |
| Ограничения по ресурсам | 80,00 | 30,00 | 20,00 | 0,00 |
| Рациональное распределение ресурсов технологических дров и отходов лесопиления по критерию дохода | ||||||
| Ресурсы Продукция | производство в смену тех. щепы и тарной дощечки | Технол. дрова | Отходы лесопиления | Спрос на тарную дощ. | Соответствие спроса по тех. щепе | Доход от реализации, руб |
| Технол. Щепа | 52,00 | 52,00 | 26,00 | 0,00 | -52,00 | 260,00 |
| Тарная дощечка | 8,00 | 28,00 | 4,00 | 8,00 | 8,00 | 80,00 |
| Текущие значения объемов используемого сырья и дохода | 80,00 | 30,00 | 8,00 | -44,00 | 340,00 | |
| Ограничения по ресурсам | 80,00 | 30,00 | 20,00 | 0,00 |
| Microsoft Excel 12.0 Отчет по результатам | ||||||
| Рабочий лист: [компьютерное решение Усольцев.xlsx]Лист1 | ||||||
| Отчет создан: 02.06.2015 16:05:37 | ||||||
| Целевая ячейка (Максимум) | ||||||
| Ячейка | Имя | Исходное значение | Результат | |||
| $G$5 | Текущие значения объемов используемого сырья и дохода Доход от реализации, руб | 340,00 | 340,00 | |||
| Изменяемые ячейки | ||||||
| Ячейка | Имя | Исходное значение | Результат | |||
| $B$3 | Технол. Щепа производство в смену тех. щепы и тарной дощечки | 52,00 | 52,00 | |||
| $B$4 | Тарная дощечка производство в смену тех. щепы и тарной дощечки | 8,00 | 8,00 | |||
| Ограничения | ||||||
| Ячейка | Имя | Значение | Формула | Статус | Разница | |
| $C$5 | Текущие значения объемов используемого сырья и дохода Технол. дрова | 80,00 | $C$5<=$C$6 | связанное | ||
| $D$5 | Текущие значения объемов используемого сырья и дохода Отходы лесопиления | 30,00 | $D$5<=$D$6 | связанное | ||
| $E$5 | Текущие значения объемов используемого сырья и дохода Спрос на тарную дощ. | 8,00 | $E$5<=$E$6 | не связан. | ||
| $F$5 | Текущие значения объемов используемого сырья и дохода Соответствие спроса по тех. щепе | -44,00 | $F$5<=$F$6 | не связан. |
| Microsoft Excel 12.0 Отчет по устойчивости | |||||||
| Рабочий лист: [компьютерное решение Усольцев.xlsx]Лист1 | |||||||
| Отчет создан: 02.06.2015 16:05:42 | |||||||
| Изменяемые ячейки | |||||||
| Результ. | Нормир. | Целевой | Допустимое | Допустимое | |||
| Ячейка | Имя | значение | стоимость | Коэффициент | Увеличение | Уменьшение | |
| $B$3 | Технол. Щепа производство в смену тех. щепы и тарной дощечки | 52,00 | 0,00 | 2,142857143 | |||
| $B$4 | Тарная дощечка производство в смену тех. щепы и тарной дощечки | 8,00 | 0,00 | 7,5 | |||
| Ограничения | |||||||
| Результ. | Теневая | Ограничение | Допустимое | Допустимое | |||
| Ячейка | Имя | значение | Цена | Правая часть | Увеличение | Уменьшение | |
| $C$5 | Текущие значения объемов используемого сырья и дохода Технол. дрова | 80,00 | 2,00 | ||||
| $D$5 | Текущие значения объемов используемого сырья и дохода Отходы лесопиления | 30,00 | 6,00 | 12,22222222 | |||
| $E$5 | Текущие значения объемов используемого сырья и дохода Спрос на тарную дощ. | 8,00 | 0,00 | 1E+30 | |||
| $F$5 | Текущие значения объемов используемого сырья и дохода Соответствие спроса по тех. щепе | -44,00 | 0,00 | 1E+30 |
| Microsoft Excel 12.0 Отчет по пределам | |||||||||
| Рабочий лист: [компьютерное решение Усольцев.xlsx]Отчет по пределам 1 | |||||||||
| Отчет создан: 02.06.2015 16:05:47 | |||||||||
| Целевое | |||||||||
| Ячейка | Имя | Значение | |||||||
| $G$5 | Текущие значения объемов используемого сырья и дохода Доход от реализации, руб | 340,00 | |||||||
| Изменяемое | Нижний | Целевой | Верхний | Целевой | |||||
| Ячейка | Имя | Значение | предел | результат | предел | результат | |||
| $B$3 | Технол. Щепа производство в смену тех. щепы и тарной дощечки | 52,00 | 8,00 | 120,00 | 52,00 | 340,00 | |||
| $B$4 | Тарная дощечка производство в смену тех. щепы и тарной дощечки | 8,00 | 0,00 | 260,00 | 8,00 | 340,00 |