Экономико-математический анализ модели ЗЛП
После нахождения оптимального решения ЗЛП естественно возникает вопрос о том, как влияют изменения параметров модели на полученное оптимальное решение. Рассмотрим на примере, как влияет на оптимальное решение изменение запасов ресурсов. Для этого будем использовать отчеты Excel. Пусть решается задача о выпуске двух видов продукции с использованием трех видов сырья. Необходимо найти такой план выпуска продукции, при котором прибыль от ее реализации будет максимальной.
В данной задаче оптимальное решение. Максимальная прибыль. Подставим оптимальное решение в систему ограничений:
Ограничение называется активным (связанным), если в точке оптимального решения оно выполняется как равенство. Ограничение называется неактивным (несвязанным), если в точке оптимального решения оно выполняется как строгое неравенство. Оптимальное решение зависит от активных ограничений и не зависит от неактивных. Ресурс, соответствующий активному ограничению, называется дефицитным, так как он используется полностью.
Ресурс, соответствующий неактивному ограничению, называется недефицитным ресурсом, так как он имеется в избытке.
Вид сырья |
Запас сырья |
Остаток |
Статус |
S1 |
21 |
0 |
Дефицитное |
S2 |
33 |
0 |
Дефицитное |
S3 |
18 |
6 |
Недефицитное |
Отчет о результатах. Отчет включает в себя три таблицы. В первой таблице приводится исходное и окончательное значение целевой ячейки. Во второй таблице даны исходные и окончательные значения переменных. Третья таблица отчета содержит информацию об ограничениях. В графе Значение указано фактическое значение левой части каждого ограничения. В графе Разница указано, насколько отличаются левая и правая часть каждого неравенства системы ограничений. В частности, для ресурсных ограничений - это остаток ресурсов. Число 0 означает, что данное сырье использовано полностью. Положительное число указывает на количество неиспользованного сырья.
Графа Статус указывает на связь ограничений с оптимальным решением, а именно, какие ограничения являются активными (связанными) и неактивными (несвязанными). Оптимальное решение зависит от первых и не зависит от вторых.
Отчет об устойчивости. Отчет включает в себя две таблицы. В первой таблице указаны коэффициенты целевой функции - прибыль от реализации выпускаемой продукции, и допустимые изменения.
С ее помощью можно найти интервалы изменения коэффициентов, при которых сохраняется найденное оптимальное решение.
,
,
Во второй таблице указаны теневые цены, которые характеризуют выгодность ресурсов. Теневая цена ресурса показывает, на сколько денежных единиц изменится максимальная прибыль от реализации продукции при изменении запаса соответствующего ресурса на единицу.
Если запасы ресурсов увеличить соответственно на, то можно определить влияние этих изменений на прибыль. В отчете об устойчивости указаны допустимые границы увеличения и уменьшения запасов ресурсов. , , . Если изменения запасов ресурсов удовлетворяют этим неравенствам, теневые цены остаются неизменными. Это позволяет оценить влияние этих изменений на прибыль. Определим раздельное влияние этих изменений на прибыль (для трех видов ресурсов):
, ,
Суммарное влияние на прибыль:
В данном примере: пусть.
Новая максимальная прибыль составит
Двойственные задачи. Задача об использовании ресурсов. Рассматриваем задачу о выпуске двух видов продукции с использованием трех видов сырья.
Вид сырья |
Расход сырья |
Запас сырья |
Цена ед. продукции |
Обозначим и - число единиц продукции и,
- запас ресурса, - расход ресурса на единицу продукции ;
- цена продукции.
Исходная задача. Составить план выпуска продукции, при котором прибыль (выручка) от реализации продукции будет максимальной:
При ограничениях
Предположим, что некоторая организация решила закупить ресурсы предприятия по ценам. Она заинтересована в том, чтобы затраты на все ресурсы были минимальны.
Предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не менее той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. Затраты на ресурсы, потребляемые при изготовлении единицы продукции, должны быть не менее ее цены.
Двойственная задача. Найти такой набор цен ресурсов, при котором общие затраты на ресурсы будут минимальными:
Коэффициенты при переменных в системах ограничений описываются матрицами:
Эти задачи обладают следующими свойствами:
- 1. В одной задаче ищут максимум линейной функции, в другой - минимум. 2. Каждая задача задана в стандартной форме. В задаче максимизации все неравенства вида "?", а в задаче минимизации неравенства вида "?". 3. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче. 4. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений в другой. 5. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг другу. 6. Условия неотрицательности переменных имеются в обеих задачах.
Две ЗЛП, обладающие указанными свойствами, называются симметричными взаимно двойственными задачами.
Как составить математическую модель двойственной задачи:
- 1. Записать расширенную матрицу, в которую включить матрицу коэффициентов при переменных, столбец свободных членов ограничений и строку коэффициентов при переменных целевой функции. 2. Найти матрицу, транспонированную к матрице. 3. На основании полученной матрицы сформулировать двойственную задачу и условия неотрицательности переменных.
Пример. Дана математическая модель ЗЛП:
Математическая модель двойственной задачи:
В исходной задаче оптимальное решение. . Теневые цены (см. лекцию 3). В двойственной задаче оптимальное решение. . Основная теорема двойственности. Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их целевых функций равны:
Таким образом, оптимальное решение двойственной задачи - это теневые цены в отчете об устойчивости исходной задачи.
Числа называются объективно обусловленными оценками. Объективно обусловленные оценки ресурсов определяют степень дефицитности ресурсов: если ресурс дефицитный, то, а если недефицитный, то. С помощью этих оценок можно определить целесообразность включения в план нового вида продукции. Допустим, что появилась возможность выпуска еще одного вида продукции. Затраты ресурсов на единицу продукции соответственно равны. Дополнительные затраты на ресурсы составят.
Осталось сравнить это число с ценой реализации. Если, продукцию можно включить в план выпуска. Если, продукцию не следует включать в план выпуска. В рассмотренном примере. Оценить целесообразность введения в план третьего вида продукции, если нормы расхода сырья на его единицу составляют соответственно 2, 1, 3, а прибыль - 2 ден. ед. , .Так как прибыль равна 2 ден. ед., то, и продукцию не следует включать в план выпуска.
Транспортная задача.
Постановка задачи. В различных местах отправки имеется однородный груз, который требуется доставить в несколько пунктов назначения. Известно, сколько груза имеется у каждого поставщика, и сколько груза должен получить каждый потребитель. Требуется организовать перевозки так, чтобы затраты на перевозки были минимальны.
Введем обозначения:
- - число поставщиков (складов, хранилищ); - число потребителей, количество пунктов назначения,
- запас груза в ом пункте (мощность i-го поставщика),
- спрос j-го потребителя, количество груза, которое должно быть завезено в й пункт,
- количество груза, перевозимого от i-го поставщика j-му потребителю,
- затраты на перевозку единицы груза от i-го поставщика j-му потребителю.
Требуется найти объемы перевозок для каждой пары "поставщик-потребитель" так, чтобы:
- 1) все грузы были вывезены; 2) спрос всех потребителей был удовлетворен; 3) суммарные затраты на перевозку были бы минимальны.
Пример.
Склады |
Спрос потребителей |
Запасы груза | |
П1 |
П2 | ||
90 |
80 | ||
С1 |
5 |
3 |
70 |
С2 |
3 |
4 |
100 |
1) 2)
Математическая модель задачи.
(1) (2)
(3)
На множестве неотрицательных решений системы ограничений (1) и (2) найти такое решение, при котором линейная функция (3) принимает минимальное значение. Математическая модель транспортной задачи имеет каноническую форму, так как система ограничений есть система уравнений. Для того чтобы транспортная задача была разрешима, т. е. имела оптимальный план, должно выполняться условие, т. е. суммарная мощность поставщиков должна быть равна суммарному спросу потребителей. В этом случае транспортная задача называется закрытой. Если суммарная мощность поставщиков не равна суммарному спросу потребителей, т. е. , то транспортная задача называется открытой.
Рассмотрим два случая.
Случай 1. Суммарный запас груза больше суммарного спроса потребителей:
Предложение превышает спрос. В данном случае имеется избыток запасов. Потребности потребителей будут удовлетворены полностью, а грузы будут вывезены со складов не в полном объеме. Поэтому знаки равенств в первой системе необходимо заменить знаками неравенств "<=". Система ограничений примет вид:
Случай 2. Суммарный запас груза меньше суммарного спроса потребителей:
Спрос превышает предложение. В ситуации дефицита все запасы будут вывезены полностью, а потребности будут удовлетворены не в полном объеме. Это означает, что знаки равенств во второй системе необходимо заменить знаками неравенств "<=".
Целевой ячейка цена прибыль
Похожие статьи
-
Модели линейного программирования. Основные определения Еще одним классом задач экономико-математического моделирования являются задачи линейного...
-
Модель с определением точки заказа - Экономико-математические модели управления запасами
В реальных ситуациях следует учитывать время выполнения заказа Q. Для обеспечения бесперебойного снабжения заказ должен подаваться в момент, когда...
-
Моделирование временной переменная автокорреляция Главным инструментом эконометрического исследования является модель. Выделяют три основных класса...
-
Применение экономико-математических методов и ЭВМ позволяет получить оптимальный план сочетания отраслей агропромышленного предприятия, обеспечивающий...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Элементы математических методов и моделей
Введение Основной целью данного курса является ознакомление студентов с основными математическими моделями и методами, используемых в процессах принятия...
-
Теоретическое обоснование математического моделирования - Математические методы и модели в экономике
Коммерческая деятельность в том или ином виде сводится к решению таких задач: как распорядиться имеющимися ресурсами для достижения наибольшей выгоды или...
-
Необходимость введения нового ограничения может возникнуть, например, когда первоначально для сокращения затрат машинного времени некоторые интуитивно...
-
Введение - Экономико-математические модели управления запасами
Разница в ритме производства продукции у различных поставщиков, дискретность процесса поставок, возможность случайных колебаний в интенсивности...
-
ДОПУЩЕНИЯ МОДЕЛИ РЕГРЕССИОННОГО АНАЛИЗА, ФАКТОРНЫЙ АНАЛИЗ - Многомерный статистический анализ
Регрессионная модель при оценке параметров и проверке значимости исходит из ряда допущений: 1. Ошибочный член уравнения регрессии (остаточный компонент)...
-
Возможны две различных стратегии реструктуризации сферы централизованного теплоснабжения, и, как следствие, различные методики анализа возникающих...
-
Гомоскедастичностью называется выполняемость предпосылки о постоянстве дисперсии отклонений. Гетероскедастичностью называется невыполняемость этой самой...
-
Уровень науки и техники Надежность средств, с помощью которых человек достигает космоса высокая, но не идеальна. РН -- сложная конструкция, и даже в...
-
Модели и моделирование - Экономико-математические методы
Одним из основных методов научного познания является эксперимент, а самой распространенной его разновидностью - метод моделирования систем. В процессе...
-
Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...
-
Теория игр исследует оптимальные стратегии в ситуациях игрового характера. К ним относятся ситуации, связанные с выбором наивыгоднейших производственных...
-
Заключение - Экономико-математические модели управления запасами
В любой задаче управления запасами решается вопросы выбора размеров и сроков размещения заказов на запасаемую продукцию. К сожалению, общее решение этой...
-
Ограничение чувствительность задача программирование Вариации правых частей ограничений приводят к изменению области допустимых решений ЗЛП, в действии...
-
Оптимальное решение модели. - Методика решения задачи целочисленного программирования
Рис. 1 Шаг 1. Исходную задачу 1 заносим в дерево задач. В качестве исходного допустимого решения берем: x1=x2=x3=0. Соответствующее значение целевой...
-
Детерминированные модели, Модель Уилсона - Экономико-математические модели управления запасами
Чрезвычайно трудно построить обобщенную модель управления запасами, которая учитывала бы все разновидности условий, наблюдаемых в реальных системах. Но...
-
В предыдущем разделе обсуждается важность учета пространственных взаимодействий при изучении влияния факторов арендной ставки на рынке недвижимости, как...
-
В данной работе были рассмотрены два теста, которые позволяют выявить гетероскедастичность. И тест Вайта, и тест Парка являются простыми тестами, которые...
-
Литература - Синтез скоринговой модели методом системно-когнитивного анализа
1. Луценко Е. В. Автоматизированный системно-когнитивный анализ в управлении активными объектами (системная теория информации и ее применение в...
-
Оптимизация, Верификация модели - Синтез скоринговой модели методом системно-когнитивного анализа
Оптимизируем полученную модель с помощью удаления признаков, по которым имеется недостаточно данных. За пороговое значение встреч признаков в модели...
-
Разработав описательные и классификационные шкалы, переходим к формированию обучающей выборки, которая включает в себя информацию о факторах, влияющих на...
-
Введение - Синтез скоринговой модели методом системно-когнитивного анализа
Кредитно-финансовая система является одной из важнейших структур рыночной экономики, так как от темпов ее развития напрямую зависят темпы развития...
-
Анализ результатов, Список литературы - Модель складской системы с контролем уровня запасов
Графики распределения запасов и дневного оборота представлены на рис. 2 и 3. Рис. 2. График распределения запасов Рис. 3. График распределения дневного...
-
После проведения регрессионного анализа получается модель объекта исследований в виде некоторой функции. В простейшем случае линейной регрессии она имеет...
-
Моделирование в условиях противодействия, игровые модели - Основы теории систем и системного анализа
Как уже неоднократно отмечалось, системный анализ невозможен без учета взаимодействий данной системы с внешней средой. Ранее упоминалась необходимость...
-
Регрессионный метод оценки, апроксимационные модели - Корреляционно-регрессионный анализ
При изучении любого процесса (физического, социального) прихоится сталкиваться с необходимостью представлять его в качестве некоторой модели, т. е. в...
-
Адсорбция активированный уголь Развитие теории адсорбционных сил еще не достигло такой стадии, когда по известным физико-химическим свойствам газа и...
-
Модель с учетом неудовлетворенных требований - Экономико-математические модели управления запасами
В некоторых случаях, когда потери из-за дефицита сравнимы с издержками хранения, дефицит допускается. Пусть требования, поступающие в момент отсутствия...
-
Введение - Стохастическая полумарковская модель
Анализ функционирования экономических систем пожалуй самое востребованное в современном мире направление стохастической теории управления. Например, в...
-
Модели теории игр. Основные определения и термины В разных областях целенаправленной деятельности, например при разработке и эксплуатации АСУ, часто...
-
Оптимальный план - Модели оптимального плана управления запасами
Найдем наилучший план поставок. План, для которого в моменты доставок очередных партий запас равен 0 (т. е. y(t) = 0), назовем напряженным. Утверждение...
-
При управлении подвижными объектами (такими, например, как мобильные роботы, подводные аппараты и т. п.) часто имеет место неопределенность цели, когда...
-
Формирование цен различных товаров зависит от большого числа факторов, совокупное влияние которых не может быть детерминировано в рамках общей модели без...
-
Элементы матричного анализа - Методы решения системы линейных уравнений
Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...
-
Экономико-математическая модель ТЗ - Экономико-математические методы
Рассмотрим ситуацию (3.1). Обозначим через количество единиц груза, которое необходимо доставить от i-го поставщика к j-му потребителю....
-
Односекторные и многосекторные модели прогнозов - Многосекторные модели прогнозирования
"Односекторным считается прогноз, рассматривающий процессы в одной из хозяйственных ячеек, многосекторным - во взаимодействующей группе таких ячеек" [4,...
Экономико-математический анализ модели ЗЛП