Green-sell.info

Новые технологии
1 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

Оптимизационные модели

Автор: Андрей Нестеров ✔ 25.12.2016

Нестеров А.К. Оптимизационные модели // Энциклопедия Нестеровых

Рассмотрим задачи, элементы оптимизационных моделей и этапы их построения.

Понятие оптимизационных моделей

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

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

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

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

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

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

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

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

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

  • склад предприятия,
  • выпуск новой продукции,
  • транспортировка готовой продукции и т.п.

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

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

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

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

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

Элементы оптимизационной модели

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

Элементы оптимизационной модели

Описание элементов оптимизационной модели приведено в таблице.

ПОСТРОЕНИЕ ЛИНЕЙНЫХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ

ЭКОНОМИКО – МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ

Методические указания к практическим работам

УДК 330.105

Печатается по решению редакционно-издательского совета

Владимирского государственного университета

Экономико-математические методы и модели (в туризме и гостиничном хозяйстве): Метод. указания к практич. работам / Владим. гос. ун – т ; Сост.: Т.К. Снегирева,. Владимир, 2007. 35с.

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

Рекомендуется студентам специальности 080502 (0608.17) – экономика и управление туризмом и гостиничным хозяйством.

Табл. 12. Библиогр.: 8 назв.

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

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

Читать еще:  Запуск андроид оптимизация приложения

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

Практическая работа № 1

ПОСТРОЕНИЕ ЛИНЕЙНЫХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ

ЦЕЛЬ РАБОТЫ: развить навыки теоретического построения линейных оптимизационных моделей в задачах планирования деятельности туристской фирмы.

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ. В общем виде экономико-математические модели представляют собой функциональные зависимости между количественными переменными.

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

В общем виде такая­ модель записывается так:

В этой модели x1, x2, …, xn – управляющие переменные, то есть независимые, а z, zr, zl – управляемые переменные, то есть зависимые (от xn).

В наиболее общем виде все переменные и коэффициенты модели (1) имеют следующий экономический смысл:

pj – прибыль с единицы j-го вида услуг, j = 1, n;

arj – норматив расхода r-го ресурса на единицу j-й услуги, r = 1, k, j = 1, n;

ar – контрольный уровень фондов r-го ресурса, наличие ресурса ;

zl – суммарный результат по l-му экономическому показателю, l = k + 1, m;

alj – нормативный результат по l-му экономическому показателю с единицы j-й услуги, l = k + 1, m, j = 1, n;

al – контрольный уровень результата по l-му экономическому показателю, l = k + 1, m.

Для последующего экономического анализа модель (1) необходимо упростить так, чтобы ограничения на все переменные, входящие в модель, были одинаковые и простые. Другими словами, все переменные, за исключением z, должны быть 0.

Для этого вычтем из обеих частей каждого r-го неравенства переменную ar, а из обеих частей каждого l-го — ar.

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

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

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

Практическая работа № 1

ПОСТРОЕНИЕ ЛИНЕЙНЫХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ

ЦЕЛЬ РАБОТЫ: развить навыки теоретического построения линейных оптимизационных моделей в задачах планирования деятельности туристской фирмы.

ЗАДАНИЕ К ПРАКТИЧЕСКОЙ РАБОТЕ

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

Организация предоставляет два вида услуг:

-продажу авиабилетов в страны Европы.

Организационно-экономические возможности фирмы следующие:

-выход в Интернет — не более 500 Мб в неделю,

-поездки в посольства и представительства стран Европы в других городах — не более 6 раз в неделю.

Дополнительные сведения о нормах объемов информации по сети Интернет (по ADSL-технологии) и поездок в посольства или представительства в других городах приведены в таблицах 1, 2.

Выручка фирмы от предоставления двух видов услуг должна составлять не менее 20000 руб. в день, в т.ч. от продажи авиабилетов — не менее 10000 руб.

Определим потребляемые организацией ресурсы z:

zr1 — суммарный расход от выхода в интернет;

zr2 — суммарный расход от поездок;

zr1 = 40×1 + 50×2 ? 500;

определим выходные экономические показатели:

zl1 — суммарный результат по общей выручке.

zl2 — суммарный результат по выручке от продажи билетов

zl1 = 4400×1 + 7000 x2 ? 20000,

zl2 = 7000 x2 ? 10000

выбрем показатель эффективности или качества принимаемых решений z0;

z0 = 440 x1 + 700×2 > max

Цель моделирования: z0 > max.

Ограничения на ресурсы и экономические показатели: x1 ? 0, x2 ? 0.

Таким образом, получаем:

z0 = 440 x1 + 700×2 > max;

zr1 = 40×1 + 50×2 ? 500;

zl1 = 4400×1 + 7000 x2 ? 20000,

zl2 = 7000 x2 ? 10000

Приведем модель к стандартной форме, получим:

z0 = 440 x1 + 700×2 > max;

yr1 = -40×1 — 50×2 + 500 ? 0;

yl1 = 4400×1 + 7000 x2 — 20000? 0,

yl2 = 7000 x2 -10000 ? 0

Практическая работа № 2

ГРАФИЧЕСКИЕ МЕТОДЫ ПОИСКА ОПТИМАЛЬНОГО РЕШЕНИЯ ЛИНЕЙНЫХ МОДЕЛЕЙ

ЦЕЛЬ РАБОТЫ: развить навыки анализа экономико-математических моделей на основе графических методов поиска их оптимальных решений.

Необходимо найти максимальное значение целевой функции F = 440×1+700×2 > max, при системе ограничений:

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

Границы области допустимых решений

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

Обозначим границы области многоугольника решений.

Рассмотрим целевую функцию задачи F = 440×1+700×2 > max.

Построим прямую, отвечающую значению функции F = 0: F = 440×1+700×2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

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

Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (6), то ее координаты удовлетворяют уравнениям этих прямых:

Читать еще:  Классификация методов оптимизации

Решив систему уравнений, получим: x1 = 0, x2 = 10
Откуда найдем максимальное значение целевой функции:
F(X) = 440*0 + 700*10 = 7000.

Практическая работа № 3

СИМПЛЕКС-МЕТОД ПОИСКА И АНАЛИЗА ОПТИМАЛЬНОГО РЕШЕНИЯ ЛИНЕЙНЫХ МОДЕЛЕЙ

ЦЕЛЬ РАБОТЫ: развить навыки поиска и анализа оптимальных решений линейных моделей на основе симплексного метода.

ЗАДАНИЕ К ПРАКТИЧЕСКОЙ РАБОТЕ

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

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

Определим максимальное значение целевой функции F(X) = 440×1 + 700×2 при следующих условиях-ограничений.

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (?) вводим базисную переменную x3. В 2-м неравенстве смысла (?) вводим базисную переменную x4. В 3-м неравенстве смысла (?) вводим базисную переменную x5 со знаком минус. В 4-м неравенстве смысла (?) вводим базисную переменную x6 со знаком минус.

40×1 + 50×2 + 1×3 + 0x4 + 0x5 + 0x6 = 500

2×1 + 0x2 + 0x3 + 1×4 + 0x5 + 0x6 = 6

4400×1 + 7000×2 + 0x3 + 0x4-1×5 + 0x6 = 20000

0x1 + 7000×2 + 0x3 + 0x4 + 0x5-1×6 = 10000

Введем искусственные переменные x: в 3-м равенстве вводим переменную x7; в 4-м равенстве вводим переменную x8;

40×1 + 50×2 + 1×3 + 0x4 + 0x5 + 0x6 + 0x7 + 0x8 = 500

2×1 + 0x2 + 0x3 + 1×4 + 0x5 + 0x6 + 0x7 + 0x8 = 6

4400×1 + 7000×2 + 0x3 + 0x4-1×5 + 0x6 + 1×7 + 0x8 = 20000

0x1 + 7000×2 + 0x3 + 0x4 + 0x5-1×6 + 0x7 + 1×8 = 10000

Для постановки задачи на максимум целевую функцию запишем так:

F(X) = 440×1+700×2 — Mx7 — Mx8 > max

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

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

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

Из уравнений выражаем искусственные переменные:

которые подставим в целевую функцию:

F(X) = 440×1 + 700×2 — M(20000-4400×1-7000×2+x5) — M(10000-7000×2+x6) > max

F(X) = (440+4400M)x1+(700+14000M)x2+(-M)x5+(-M)x6+(-30000M) > max

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Построение оптимизационных моделей линейного программирования (простейшие экономические модели)

4.3.1. Общая характеристика

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

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

Важнейшие управленческие решения в этом случае связаны со следующими процессами:

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

2. добыча сырой нефти;

3. обмен сырой нефти, добываемой фирмой, на нефтесырьё других нефтяных компаний;

4. дополнительная закупка сырой нефти;

5. доставка нефти на нефтеперегонные заводы;

6. крекинг и ректификация с целью получения различных нефтепродуктов для смешения (промежуточных продуктов);

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

8. доставка (транспортировка) готовой продукции к местам сбыта.

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

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

Качественно такая же картина может возникнуть применительно к фирмам по выращиванию лесомассивов (лес на корню) и производству лесоматериалов и др. ресурсов.

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

4.3.2. Потенциальные возможности линейного программирования

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

Читать еще:  Лучший оптимизатор системы

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

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

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

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

Оптимизационная модель задачи линейного программирования

Дата добавления: 2014-11-28 ; просмотров: 1462 ; Нарушение авторских прав

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

Общая задача линейной оптимизации заключается в нахождении максимума (минимума) линейной целевой функции

(5)

при заданных ограничениях

(6)

Функция называется целевой функцией, критерием оптимальности или линейной формой (5).

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

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

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

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

· Для определения каких величин должна быть построена модель, т.е. как идентифицировать переменные задачи?

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

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

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

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

Предприятие выпускает соляную и серную кислоту. Выпуск одной тонны соляной кислоты приносит предприятию прибыль в размере 30 ден.ед., выпуск одной тонны серной кислоты – 35 ден.ед. Для выполнения поступившего заказа предприятию необходимо выпустить не менее 250 т соляной и не менее 170 т серной кислоты. Выпуск кислот связан с образованием токсичных отходов, общее количество которых не должно превышать 600 т. При выпуске одной тонны соляной кислоты образуется 0,4 т токсичных отходов, а при выпуске одной тонны серной кислоты – 1,2 т. Необходимо определить, сколько соляной и серной кислоты должно выпустить предприятие, чтобы получить максимальную прибыль.

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

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

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

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

Целевая функция будет иметь вид: .

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

составить план , удовлетворяющий системе ограничений

,

при которой функция принимает минимальное значение.

Сформулируем данную задачу в общем виде.

Обозначим через xj (j = 1, 2,…, n) – количество единиц j-го продукта в дневном рационе. В рационе используется n видов продуктов. Каждый продукт содержит m питательных веществ в количестве не менее bi (i = 1,2,…,m) единиц, aij – число единиц питательного вещества si в единице продукта j-го вида. Известна стоимость cj единицы j-го продукта. Необходимо составить рацион нужной питательности при минимальных затратах на него.

Экономико-математическая модель примет вид:

Ссылка на основную публикацию
Adblock
detector