Расчет оптимизационных моделей

Практическое занятие

«Расчет оптимизационных моделей»

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

Оптимизационная модель формируется в общем виде следующим образом: «Надо отыскать значения управляемых параметров (показателей) x1, x2,…xn, характеризующих управляемый экономический объект или процесс, придающие максимальное или минимальное значение целевой функции F (x1,x2,…xn,)при соблюдении ограничений, накладываемых на область изменения показателей x1, x2,…xn, и связей между ними в виде f (x1,x2,…xn,)a». Если целевая функция, ограничения, связи между искомыми показателями выражены в виде линейных зависимостей, то оптимизационная модель сводится к задаче линейного математического программирования и саму модель также называют линейной.

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

Задача 1. Простейшая задача на максимизацию прибыли компании Компания производит два продукта в количестве x1 и x2 тонн за месяц соответственно. Тонна первого продукта приносит 12 тысяч гривен прибыли, а тонна второго продукта — 8 тысяч гривен. Производственные мощности компании позволяют выпускать не более 100 тонн двух продуктов вместе, при этом производство первого продукта не может превышать более чем в три раза производство второго. Надо определить оптимальный объем производства, приносящий компании максимальную прибыль.

Применительно к данной задаче целевая функция (критерий оптимальности) имеет вид:

F (x1, x2,…xn,)=F (x1, x2)=12×1 +8×2 тысяч гривен Объемы выпуска x1 и x2 есть заведомо положительные величины, то есть

x1 0; x2 0

Между значениями x1 и x2 имеются связи

x1 + x2 100

x1 3 x2

Таким образом, подходим к типичной задаче линейного математического программирования, когда надо отыскать значения управляющих параметров x1, x2, придающие максимальное значение целевой функции 12×1 +8×2 с учетом фиксированных связей и ограничений.

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

0 20 40 60 75 80 100 120

Рисунок.3.1. — Графическая интерпретация задачи В силу положительных значений параметров x1 и x2 (x10;x20) решение следует искать в первом квадранте. Ограничение по суммарному выпуску (x1 + x2 100) сужает область поиска до находящейся внутри треугольника ОАС, ограниченного сверху прямой x1 + x2 =100. Ограничение x1 3×2 еще более сужает область допустимых по условию задачи значений x1 и x2, заключая ее в треугольник ОАВ, ограниченный снизу прямой x1 3×2. Среди всех значений x1 и x2, заключенных внутри ОАВ, оптимальным соответствует точка В. В этой точке, соответствующей координатам x1 = 75; x2 = 25, достигается наибольшее из допустимых значений x1 равное 75. К наибольшему же значению x1 и надо стремиться, так как первый вид продукции приносит в расчете на одну тонну больше прибыли, чем второй (12 > 8), то есть надо выбирать наибольшее из возможных, допустимых значений x1. Оптимальному решению соответствует, таким образом, точка В, в которой целевая функция достигает своего максимального значения

12×1 +8×2 =1275+8 25=1100 тысяч гривен Легко проверить, что внутри треугольника ОАВ любое другое сочетание, кроме x1 = 75; x2 = 25, обеспечивает меньшую суммарную прибыль.

Задача 2. Постановка и решение транспортной задачи Рассмотрим вначале общую постановку этой достаточно сложной оптимизационной задачи и построим ее экономико-математическую модель, которую потом проиллюстрируем простейшим примером.

Пусть имеется n поставщиков товара и m его потребителей. Каждый «i» поставщик способен поставлять потребителям за определенное время количество товара, равное Ni, а каждый «j» потребитель нуждается в количестве товара, равном Mj. Обозначим через xij количество товара, поставляемое «i» поставщиком «j» потребителю. Тогда общий объем поставок Q равный объему спроса всех потребителей, выразится соотношением:

где

Nj =- есть сумма поставок всем m потребителям со стороны «i» поставщика.

Mj = - есть сумма потребностей «j» потребителя, удостоверяемых поставщиками всех n поставщиков.

Примем далее, что стоимость перевозки товара «i» поставщиком «j» потребителю равна cij. Тогда общая стоимость перевозок, зависящих от прикрепления «i» поставщика к «j» потребителю, то есть от значений xij равна

F (xij) = cij xij, i=1,2…n, j=1,2,…m

Оптимизационная задача заключается в том, чтобы найти значения xij, то есть величины поставок (перевозок) товара от каждого поставщика к каждому потребителю, при которых общая стоимость перевозок F (x11, x12,…xij,…xnm) будет минимальной. Решение задачи должно удовлетворять следующим ограничениям:

все значения xij неотрицательны, то есть xij0

возможность перевозок и запросы потребителя удовлетворяются полностью Экономико-математическая модель транспортной задачи, в представленном виде характеризуемая целевой функцией и ограничениями, представляет оптимизационную модель задачи линейного математического программирования. Решение таких задач при больших значениях количества поставщиков товара «n» и количества потребителей товара «m» требует применения сложных математических методов. Поэтому проиллюстрируем решение транспортной задачи на простом примере, в котором отыскание оптимального решения не составит большого труда.

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

Таблица 2.

Задача заключается в том, чтобы найти значение объемов поставок X11, X12, X13 первого поставщика первому, второму и третьему потребителям и объемы поставок X21, X22, X23 второго поставщика соответственно первому, второму и третьему потребителям при которых суммарные затраты

F (X11, X12, X13, X21, X22, X23) = c11×11 + c12×12 + c13×13 + c21×21 + c22×22 + c23×23 = 10×11 + 9×12 +11×13 + 8×21 + 10×22 + 9×23 min

Одновременно должны соблюдаться условия:

x11 + x12 + x13 = 100

x21 + x22 + x23 = 60

x13 + x23 = 40

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

Т. к. самой дешевой является стоимость доставки ед. товара вторым поставщиком первому потребителю, то используем эту возможность полностью и примем x21 =50 т. и тем самым полностью удовлетворим его потребность. Оставшуюся возможность доставки 60−50=10т. товара со стороны второго поставщика представим третьему потребителю, т. е. x23 = 10, т. к. расход на доставку ему единицы товара (с23 = 9) (с22 = 10), чем второму потребителю меньше чем доставка первым поставщиком (с13 = 11). Следовательно, x23 = 10.

Возможности второго поставщика на этом исчерпаны и оставшиеся потребности должны быть удовлетворены первым поставщиком. Он поставит второму потребителю x12 = 70 т. и третьему потребителю x13 = 30 т., т. к. 10 т. этот потребитель уже получил от второго поставщика. Поставки товара первым поставщиком первому потребителю, также как и поставки 2 поставщика 2 потребителю окажутся ненужными поэтому x11 = 0 и x22 = 0. В итоге искомое решение задачи имеет вид:

x11 = 0; x12 =70; x13 = 30

x21 =50; x22 =0; x23 = 10

Суммарный расход на поставку товара равны:

010 + 709 + 3011 + 508 + 010 + 109 = 1450 грн. и являются минимально возможными. Средняя стоимость перевозки одной тонны товара составит

грн. за тонну, при отсутствии оптимизации средняя цена равна

грн./тонну Задача. Фирма производит два вида изделий в количестве x1 и x2. Единица первого изделия приносит П1 — гривен прибыли, а второго П2 гривен прибыли. Производственные мощности позволяют выпускать не более N единиц двух наименований изделий вместе, при этом производство первого изделия не может превышать более чем в 4 раза производство второго изделия. Определить объем производства приносящей фирме максимальную прибыль. Построить график оптимизации прибыли. Варианты заданий приведены в таблице 1.

Таблица 1

Таблица 3.

Варианты заданий к решению транспортной задачи

Контрольные вопросы.

1.Что понимается под термином «модель»?

2. Какие виды моделей вам известны?

3. В чем сущность оптимизационных моделей?

4. Что понимается под термином «оптимизационная функция»?

5. Для решения каких задач используется «оптимизационные модели»?

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

В самом общем виде балансовое соотношение имеет вид:

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

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

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

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

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

Задача. Простейшая двухпродуктовая балансовая модель Предположим, что производится два товара, один — в количестве x1 и другой — в количестве x2, измеренном в одних и тех же единицах. На производство первого товара тратится 0,1 общего выпуска этого же товара (например, на производство топлива затрачивается 10% производимого топлива) и 0,15 единиц второго товара. Кроме того, 3300 единиц первого товара производится на другие нужды. На производство единицы второго товара затрачивается 0,2 единицы первого товара и 0,05 единиц второго товара (например, на производство металла затрачивается 5% производимого металла). Кроме того, 6600 единиц второго товара производится на другие нужды. Надо определить x1 и x2, то есть требуемые объемы производства одного и второго товара.

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

{x1 = a11×1 + a12×2 + x1d

{x2 = a21×1 + a22×2 + x2d

В модели приняты обозначения:

x1 — объем производства первого товара;

x2 — объем производства второго товара;

a11 — доля первого товара, затрачиваемая на его же производство;

a12 — доля первого товара, затрачиваемая на производство второго;

a21 — доля второго товара, затрачиваемая на производство первого;

a22 — доля второго товара, затрачиваемая на его же производство;

x1d — объем производства первого товара на другие нужды;

x2d — объем производства второго товара на другие нужды.

Приводимая простейшая балансовая модель представляет систему двух линейных уравнений относительно неизвестных x1 и x2.

Согласно условиям задачи a11== 0,1; a12 = 0,15; a21 = 0,2; a22 = 0,05; x1d =3300; x2d = 6600. В итоге приходим к системе уравнений баланса:

{x1 =0.1×1 + 0.15×2 + 3300

{x2 =0.2×1 + 0.05×2 + 6600

Решая систему, находим искомые объемы производства

x1 = 5000 единиц; x2 == 8000 единиц.

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

откуда находим искомое значение x0, то есть оптимальный объем партии товара

x0 =

Это и есть решение задачи.

Например, если C1 = 6000 гривен за доставку партии товара, C2 = 300 гривен за хранение тонны товара на складе в течение суток, общий объем поставки Q = 100 тонн за время Т = 40 суток, то

X0 = тонн то есть для минимизации затрат на доставку и хранение товара на складе надо поставлять его на склад партиями по 10 тонн в каждой партии.

Задача. Определить объемы производства товаров x1 и x2 при следующих условиях. Варианты заданий приведены в таблице Варианты заданий

где

x1 — объем производства первого товара;

x2 — объем производства второго товара;

a11 — доля первого товара, затрачиваемая на его же производство;

a12 — доля первого товара, затрачиваемая на производство второго;

a21 — доля второго товара, затрачиваемая на производство первого;

a22 — доля второго товара, затрачиваемая на его же производство;

x1d — объем производства первого товара на другие нужды;

x2d — объем производства второго товара на другие нужды.

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

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

Предположим, что в игре участвуют игроки, А и В. Игрок имеет в своем распоряжении n стратегий, способов действий: A1, A2,…An, а игрок В располагает возможностью реализовать m стратегий: B1, B2,…Bm. В зависимости от того, какую стратегию Аi (i=1,2,…, n) выберет игрок, А и какую стратегию Вj (j=1, 2,…m) выберет игрок В, зависит исход игры каждого из них, то есть выигрыш aij одного из игроков и, соответственно, проигрыш другого. Таким образом, любой паре стратегий (Аi, Вj) соответствует определенное значение выигрыша aij. В итоге совокупность всех возможных выигрышей в данной игре образует матрицу, столбцы которой соответствуют стратегии одного игрока, а строки — стратегии другого. Такую матрицу называют платежной матрицей или матрицей игры.

Общий вид платежной матрицы, строки которой соответствуют стратегиям игрока А, а столбцы — стратегиям игрока В, изображен на рис. 3.2.

Рисунок 3.2. — Платежная матрица парной игры При выборе своей стратегии Аi из набора n возможных стратегий A1, A2,…An игрок, А должен учитывать, что его соперник В выберет в ответ стратегию Вj из набора возможных стратегий, стремясь свести выигрыш игрока, А к минимуму. Пусть наименьший из всех возможных выигрышей игрока, А при выборе им стратегии Аi, то есть наименьшее значение aij в «i» строке платежной матрицы равно ai то есть aj = min aij. Наибольшее из значений aj (i=1,2,…n) обозначим а, следовательно, а = max aj Такое максимальное значение из набора минимальных выигрышей игрока, соответствующих всему спектру применяемых им стратегий, называют нижней ценой или максимальным выигрышем из минимальных — максимином. Максимин представляет гарантированный выигрыш игрока, А при любой стратегии игрока В, так как игрок, А может выбрать ту стратегию, которая приносит ему максимальный выигрыш из минимально возможных.

Игрок В, стремясь уменьшить выигрыш игрока, А и понимая, что, А стремится к максимальному выигрышу, выбирая свою контрстратегию Вj анализирует прежде всего максимально возможные выигрыши игрока А. Пусть среди всех выигрышей игрока, А при выборе игроком В стратегии Вj максимально возможное значение равно bj, то есть bj = max bij. Наименьшее из всех возможных значений bj (j=1,2,…n) обозначим Ь, то есть b= min bj Такое минимальное значение из набора максимальных выигрышей игрока, соответствующее всему спектру применяемых им стратегий, называют верхней ценой игры или минимальным выигрышем из максимальныхминимаксом. Минимакс представляет неизбежный проигрыш игрока В при любой из стратегий игрока А, ибо игрок, А будет, естественно, стремиться максимизировать проигрыш игрока В и соответствующим образом выбирать свою стратегию.

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

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

Пусть Человек располагает возможностью осуществлять три стратегии действий Аi в целях получения прибыли, а Природа способна создать четыре вида ситуаций Вj, каждая из которых влияет тем или иным способом на величину прибыли. Составим платежную матрицу, в клетках которой зафиксированы рассчитанные определенными методами (которые в примере не рассматриваются) величины возможной прибыли. Например, матрица прибылей в тысячах гривен имеет вид:

Применим максиминную стратегию, стремясь получить наибольшую прибыль. Выделим в каждой из строк матрицы минимальные значения прибыли, которые могут быть получены при осуществлении одной из возможных стратегий A1, A2, A3 и самых неблагоприятных условиях, создаваемых Природой. Это 25 тысяч гривен при стратегии A1, 28 тысяч гривен при стратегии A2 и 24 тысячи гривен при стратегии A3. Максимальное из этих значений — 28 тысяч гривен соответствует максиминной стратегии Аз, которую и следует выбрать, обеспечив тем самым гарантированное получение этой величины прибыли при любых условиях, ситуациях, создаваемых Природой.

Проиллюстрируем теперь минимаксную стратегию, используя платежную матрицу, в клетках которой указаны величины потерь, возникающих при осуществлении стратегий A1, A2, A3 в условиях B1, B2, B3, B4. Пусть матрица имеет вид.

Выделяем в каждой из строк матрицы максимально возможные при осуществлении данной стратегии потери. Это — 55 при стратегии A1, 56 — при стратегии A2 и 52 — при стратегии A3. Минимальное из этих значений равно 52 и соответствует стратегии A3, которая и является минимаксной.

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

На рис. 3.3. приведен упрощенный сетевой график работ по выпуску книги, в котором буквами обозначены работы, а цифрами события.

Рисунок 3.3. — Примерный сетевой график подготовки и выпуска новой книги Исходное событие 1 — возникновение идеи, замысла у автора, за ним следует работа «а» — подготовка материалов, написание первого варианта рукописи, завершающиеся событием 2 — появлением первичной рукописи, с которой автор обращается в издательство.

Рукопись книги издательство передает на заключение рецензенту (работа «б») и готовит также собственное заключение (работа «в») с учетом передаваемого заключения рецензента (работа «г»). Так что событие 3 — это заключение рецензента, а событие 4 — итоговое заключение издательства. При положительном заключении готовиться договор с автором на издание книги (работа «д»), который в завершенном виде представляет событие 5. Затем рукопись передается редактору (работа «е»), который исправляет ее, доводя до более кондиционного состояния, характеризуемого как событие 6. Автор тоже работает над рукописью параллельно с редактором (работа «ж»), и после передачи редактором доработанной рукописи (работа «з») в издательстве наступает событие 7 — готовая к набору рукопись книги. Издательство передает рукопись в типографию (работа «и») в требуемом виде, что отражается в событии 8, а типография печатает книгу (работа «к»), в результате чего появляется готовая книга — завершающее событие — 9.

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