Лекция №1
Тема: Модели линейного программирования.
1. Понятие модели и моделирования. Классификация математических моделей.
2.Общая задача линейного программирования. Различные формы моделей задач линейного программирования.
3.Постановка и ЭММ задачи планирования производства.
4.Постановка и ЭММ задачи оптимального составления смесей.
Цель: Дать общую характеристику предмету экономико-математического моделирования, показать классификацию видов моделирования и математических моделей. Дать постановку и математическую формулировку общей задачи линейного программирования, а также основных экономико-математических моделей.
1.Понятие модели и моделирования. Классификация математических моделей.
Основным методом исследования систем является метод моделирования , т.е. способ теоретического анализа и практического действия, направленный на разработку и использования моделей. Под моделью понимается образ реального объекта (процесса) в материальной или идеальной форме (т.е. описанный знаковыми средствами на каком-либо языке), отражающие существенные свойства моделируемого объекта (процесса) и замещающий его в ходе исследования и управления.
Математическая модель – это система математических соотношений, приближенно, в абстрактной форме, описывающих изучаемый процесс или систему.
Экономико-математическая модель – это математическая модель, предназначенная для исследования экономической проблемы.
Построение и расчет математической модели позволяют проанализировать ситуацию и выбрать оптимальные решения по управлению ею или обосновать предложенные решения. Применение математических моделей необходимо в тех случаях, когда проблема сложна, зависит от большого числа факторов, по-разному влияющих на её решение. Использование математических моделей позволяет осуществить предварительный выбор оптимальных или близких к ним вариантов решений по определенным критериям.
По числу критериев эффективности математические модели делятся на однокритериальные и многокритериальные. Многокритериальные математические модели содержат два и более критерия.
По учету неизвестных факторов математические модели делятся на детерминированные, стохастические и модели с элементами неопределенности. В детерминированных моделях неизвестные факторы не учитываются. Несмотря на кажущуюся простоту этих моделей, к ним сводят многие практические задачи, в том числе большинство экономических задач. В стохастических моделях неизвестные факторы – это случайные величины, для которых известны функции распределения и различные статистические характеристики. Для моделирования ситуаций, зависящих от факторов, для которых невозможно собрать статистические данные и значения, которых неопределенны, используются модели с элементами неопределенности.
2.Общая задача линейного программирования. Различные формы моделей задач линейного программирования.
В общем виде задача линейного программирования ставится следующим образом: максимизировать (минимизировать) функцию:
при ограничениях:
где x j - управляющие переменные или решения задачи, j =1,… n
b i , a ij , c j - параметры i =1,… m ; j =1,… n
Z - целевая функция или критерий эффективности задачи.
Решить задачу линейного программирования – это значит найти значения управляющих переменных, удовлетворяющих заданным ограничениям (1-3), при которых целевая функция принимает максимальное или минимальное значение.
Задача линейного программирования в развернутом виде записывается следующим образом:
При условии, что все переменные неотрицательны, система ограничений состоит лишь из одних неравенств – такая задача линейного программирования называется стандартной , если система ограничений состоит из одних уравнений, то такая задача называется канонической (основной)
3. Постановка и ЭММ задачи планирования производства.
Постановка задачи планирования производства заключается в следующем: найти такой план выпуска продукции, удовлетворяющий системе ограничений по использованию ресурсов, при котором целевая функция достигает максимального значения.
Обозначим x j (j =1,… n ) - число единиц продукции j –вида, запланированной к производству, b i (i =1,… m ) - запас ресурса i – вида; a ij -затраты i –го ресурса на изготовление единицы продукции j - вида; c j -прибыль от реализации единицы продукции j –вида. Тогда ЭММ задачи планирования производства примет вид
при условиях:
4. Постановка и ЭММ задачи оптимального составления смесей.
Постановка задачи составления смеси (рациона, диеты) заключается в следующем: составить смесь (рацион, диету), удовлетворяющую системе ограничений по сбалансированности питательных веществ, при котором стоимость смеси (рациона, диеты) будет минимальной.
Обозначим x j (j =1,… n ) - число единиц продукта (корма) j –вида, b i (i =1,… m ) – необходимый минимум содержания в рационе (смеси) питательного вещества i – вида; a ij – число единиц питательного вещества i –го вида в единице продукта (корма) j - вида; c j – стоимость единицы продукта (корма) j –вида. Тогда ЭММ задачи примет вид
при условиях:
Вопросы для самоконтроля:
1. Что означает термин «моделирование»?
2. Дайте определение «модели»
3. Как записывается общая задача линейного программирования.
4. Какие существуют формы записи задачи линейного программирования.
5. Запишите ЭММ задачи планирования производства.
6. Запишите ЭММ задачи оптимального составления смеси.
1.«Исследование операций в экономике» под редакцией профессора Кремера Н.Ш., М: Банки и биржи, 1997, стр17-26
2.Хазанова Л.Э. «Математическое моделирование в экономике» Учебное пособие, М: Изд. БЕК, 2005, стр11-20, 24-26
3.Покровский В.В. «Математические методы в бизнесе и менеджменте» Учебное пособие. М.: Финансы и статистика, 2008г
4.Рахметова Р.У. «Математические модели и методы экономики» Учебное пособие. А.:Экономика, 2008г
Лекция №2-3
Тема: Методы решения моделей линейного программирования.
1. Алгоритм метода последовательного улучшения опорного плана в симплексных таблицах (симплексный метод).
2. Алгоритм М-метода решения задач линейного программирования со смешанными ограничениями.
Цель: Дать характеристику методам решения задач линейного программирования.
1. Алгоритм метода последовательного улучшения опорного плана в симплексных таблицах (симплексный метод).
Впервые симплексный метод был предложен Данцигом в 1949 г. Симплекс – это выпуклый простейший многогранник в n -мерном пространстве. Алгоритм симплексного метода построен так, что достаточно найти одну из вершин многогранника допустимых решений, а далее с помощью перебора вершин симплекса план будет улучшаться до нахождения оптимального варианта. Решение экономико–математической задачи проводится в несколько этапов:
1) математическая формулировка условий задачи в виде неравенств и уравнений.
2) решение задачи симплексным методом:
а) приведение задачи к канонической форме и нахождение первоначального варианта допустимого плана соответственного одной из вершин выпуклого многогранника,
б) проверка найденного плана на оптимальность, если план оптимален, то решение получено, в противном случае план должен быть улучшен,
в) последовательное улучшение плана до получения оптимального,
3) экономический анализ оптимального плана.
В зависимости от характера ограничений задачи линейного программирования могут решаться симплексным методом с использованием естественного и искусственного базиса. Если ограничения задаются неравенствами типа , то задача решается с естественным базисом. Если ограничения заданы неравенствами или , то решение ведется с искусственным базисом.
Условие задачи :
Для производства изделия «А» и «В» используется 3 вида сырья.
|
Вид сырья |
Норма расхода сырья на одно изделие, кг |
Общее количество сырья, кг |
|
|
Прибыль от реализации 1 изд., д. ед. |
|||
Определить оптимальный план выпуска изделий, при котором прибыль от реализации будет максимальной.
x 1 -производство изделий вида «А», шт.
x 2 -производство изделий вида «В», шт.
Математическая модель задачи:
Для приведения задачи к каноническому виду в систему неравенств введем дополнительные неизвестные (x 3, x 4, x 5 ) – недоиспользование ресурсов.
Дополнительные переменные входят в целевую функцию с нулевой оценкой, так как недоиспользование ресурсов не приносит никакого дохода. Вынесем дополнительные переменные за знак равенства.
Дополнительные переменные x 3, x 4, x 5 называются базисными, а x 1 и x 2 – основными или небазисными. Находим базисное решение задачи. Для этого примем x 1 =0 x 2 =0.
Тогда x 3 =300, x 4 =120, x 5 =252, Z =0.
Решение проводится в симплексных таблицах на основе тождественных преобразований, путем последовательного исключения неизвестных из уравнений.
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Лекция
Модели и методы линейного программирования
1. МОДЕЛИ И МОДЕЛИРОВАНИЕ
Термин «модель» происходит от латинского слова «modulus» образец, норма, мера. Модель - это объект, который замещает оригинал и отобр а жает важнейшие черты и свойства оригинала для данного исследования, данной цели исследов а ния при выбранной системе гипотез.
Модели обеспечивают структуру для целостного логического анализа.Модели широко используются благодаря тому, что заставляют выполнять следующие действия:
1. Явно определить цели.
2. Определить и зафиксировать типы решений, которые влияют на достижение этих целей.
3. Выявить и зафиксировать взаимосвязи и компромиссы между этими решениями.
4. Тщательно изучить входящие в них переменные и определить возможность их измерения.
5. Разобраться, какие данные нужны для количественного определения значений переменных и найти способ описать их взаимное влияние.
6. Осознать какие ограничения могут налагаться на значения этих переменных.
7. Обсудить идеи, что помогает членам группе управления в совместной работе.
Существует три типа моделей:
1. Физическая модель.
2. Аналоговая модель.
3. Символическая модель.
|
Тип модели |
Свойства |
||
|
Физическая модель |
Осязаемость. Понимание: простое. Дублирование и совместное использование: сложные. Модификация и манипулирование: сложные. Сфера использования: наиболее узкая. |
Макет самолета, макет дома, макет города. |
|
|
Аналоговая модель |
Неосязаемость. Понимание: более сложное. Дублирование и совместное использование: более простые. Модификация и манипулирование: более простые. Сфера использования: более широкая. |
Карта дорог, спидометр, круговая диаграмма. |
|
|
Символическая модель |
Неосязаемость. Понимание: самое сложное. Дублирование и совместное использование: самые простые. Модификация и манипулирование: самые простые. Сфера использования: самая широкая. |
Имитационная модель, алгебраическая модель, модель, построенная в электронной таблице. |
Наиболее абстрактной является символическая модель, в которой все понятия выводятся посредством количественно определенных переменных, а все связи представляются в математическом, а не физическом или аналоговом виде. Поскольку в символических моделях используются количественно определенные переменные, связанные уравнениями, их часто называют математическими моделями, табличными моделями (т.е. моделями на основе электронных таблиц).
Менеджерам приходится работать со всеми типами моделей, чаще всего с аналоговыми моделями в форме графиков и диаграмм, а также с символическими моделями в виде электронной таблицы или отчетов информационно-управляющей системы.
Математическая модель -- это абстракция реальной действител ь ности (мира), в которой отношение между реальными элементами, а име н но те, которые интересуют исследователя, замененные отношениями между матем а тическими категориями. Эти отношения обычно подаются в форме уравнений и/или неравенств, отношениями формальной логики между показателями (переменными), которые характеризуют функционирование реальной системы, которая моделируе т ся.
Невозможно представить себе современную науку, в частности экономику, без широкого применения математического моделирования.
Сущность этой методологии заключается в замене исходного объекта его «образом» - математической моделью - и последующим изучением (исследованием) модели на основании аналитических методов и вычислительно-логических алгоритмов, которые реализуются с помощью компьютерных программ.
Работа не с самим объектом (явлением, процессом), а с его моделью дает возможность относительно быстро и безболезненно исследовать его основные (существенные) свойства и поведения при любых вероятных ситуациях (это преимущества теории). В то же время вычислительные (компьютерные, симулятивные, имитационные) эксперименты с моделями объектов позволяют, опираясь на мощность современных математических и вычислительных методов и технического инструментария информатики, тщательным образом и достаточно глубоко изучать объект в достаточно детальном виде, что недоступно сугубо теоретическим подходам (это преимущество эксперимента). Не удивительно, что методология математического моделирования бурно развивается, охватывая анализ чрезвычайно сложных экономических и социальных процессов.
2. ПОНЯТИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. ВИДЫ ЗАДАЧ ЛИНЕЙНОГО ПР О ГРАММИРОВАНИЯ
Линейное программирование рассматривается как революционное достижение, давшее человеку способность формулировать общие цели и находить посредством симплекс-метода оптимальные решения для широкого класса практических задач принятия решений большой сложности.
Линейное программирование - математическая дисциплина, посвящённая теории и методам решения задач об экстремумах линейных функций на множествах n -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного представления реального мира.
Задача линейного программирования (ЛП), состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.
Линейное программирование применяется при решении следующих экон о мических задач :
1. Задача управления и планирования производства (распределения ресурсов).
2. Задачи о смесях, диете (планирование состава продукции).
3. Задача определения оптимального плана перевозок груза (транспортная задача, задача о назначениях).
4. Задача оптимального распределения кадров (расстановка персонала).
3. МОДЕ ЛЬ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, ЕЁ ПРЕДСТАВЛЕНИЕ В ЭЛЕКТРОННЫХ ТАБЛИЦАХ MS EXCEL
Традиционно наукой управления называют построение детально разработанных моделей, в результате анализа которых принимаются управленческие решения. Сегодня миллионы менеджеров для анализа деловых задач применяют электронные таблицы. Современные электронные таблицы имеют много мощных средств, которые можно использовать для более точного анализа моделей, в результате чего могут приниматься более взвешенные и близкие к оптимальным решения. С учетом все более широкого применения электронных таблиц в процессе управления будущим специалистам необходимо владеть профессиональными навыкам разработки моделей - как «спланировать» чистый рабочий лист так, чтобы получить полезную и практическую модель деловой ситуации, не углубляясь в алгоритмические и математические тонкости расчетов.
Основные этапы создания модели линейного программирования в Excel: линейный программирование электронный поиск
1. Написание и проверка символической модели линейного программиров а ния. Модель записывается на бумаге в математическом виде.
2. Создание и отладка табличной модели линейного программирова ния. На основе символической модели ЛП создается ее представление в Excel .
3. Попытка оптимизации модели с помощью надстройки ПОИСК РЕШЕНИЯ.
4. ИСПОЛЬЗОВАНИЕ НАДСТРОЙКИ ПОИСК РЕШЕНИЯ
С помощью электронных таблиц можно моделировать реальные ситуации и оценивать полученные результаты. Другими словами с помощью электронных таблиц можно делать анализ результатов деятельности и прогнозирования будущих перспектив предприятия. Эти задачи в среде MS Excel дает возможность решать на д стройка Поиск решения .
Поиск решения - это надстройка, которая предназначена для оптимизации моделей при наличии ограничений. Она состоит из двух программных компонентов: программы написанной на языке Visual Basic, который транслирует представленную на рабочем письме информацию для внутреннего представления, которая используется другой программой. Вторая программа находится в памяти компьютера в виде отдельного программного модуля. Она выполняет оптимизацию и возвращает найденное решение первой программе, которая возобновляет данные на рабочем листе. С помощью ее можно найти оптимальное значение формулы, которая сохраняется в целевой ячейке. Эта процедура работает с группой ячеек, которые непосредственно связанные с формулой в целевой ячейке. Чтобы получить результат по формуле в целевой ячейке, процедура изменяет значение в ячейках, которые влияют на поиск. Для того, чтобы уменьшить множественное число значений, которые используются в модели задачи, применяют ограничение. Эти ограничения могут содержать ссылку на другие ячейки, которые влияют на поиск.
Общий алгоритм работы с надстройкой Поиск решения .
1. В меню Серв и с выбрать команду Поиск решения .
2. В поле Установит целевую ячейку введите адрес ячейки, в которй находится формула, для оптимизации модели.
3. Для того, чтобы максимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Максимальному значению . Для того, чтобы минимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Минимальному значению . Для того, чтобы целевая ячейка приобретала значение конкретного числа, установите переключатель в положение Значение и введите соответствующее число.
4. В поле Изменяя ячейки введите адреса ячеек, которые изменяют свои значения, разделяя их запятыми. Изменяемые ячейки должны быть прямо или непрямо связанные с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.
5. В поле Ограничения введите все ограничения, которые налагаются на поиск решения.
6. Нажмите кнопку Выполнить .
7. Для сохранения найденного решения установите переключатель в диалоговом окне Результаты поиска решения в положение Сохранить на й денное решение . Для возобновления входных данных установите переключатель в положение Восстановить исхо д ные значения .
8. Для того, чтобы прервать поиск решения, нажмите клавишу Еsс . MS Excel пересчитает лист с учетом найденных значений ячеек, которые влияют на результат.
Алгоритм р о бот и з надбудовою Поиск реш е ния.
5. РЕШЕНИЕ ЗА ДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ ПОМОЩ И ПРОГРАММЫ MS EXCEL
Пример. Кондитерский цех для изготовления трех видов карамели А, В, С использует три основных вида сырья: сахар, патоку и фруктовое пюре. Нормы затрат сахара на изготовление 1кг карамели каждого вида соответственно уровни: 0,8кг; 0,5кг; 0,6кг; патоки - 04кг; 0,4кг; 0,3кг; фруктового пюре - 0кг; 0,1кг; 0,1кг. Конфеты можно производить в любых количествах (реализация обеспечена), но запас сырья ограниченный: запасы сахара - 80кг, патоки - 60кг, фруктового пюре - 12кг. Прибыль от реализации 1кг карамели вида А составляет 10грн., вида В - 11грн., вида С - 12грн.
Таблица 1
Определить план производства карамели, которая обеспечивает максимальную прибыль от деятельности кондитерского цеха.
Решение.
1. Написание и проверка символической модели линейного программир о вания . Модель записывается на бумаге в математическом виде .
По данному условию задачи сформулируем задачу линейного программирования то есть построим математическую модель. Обозначим: x1 - количество карамели вида А , x2 - количество карамели вида В , x3 - количество карамели вида С . Карамель выпускается ежедневно.
Найти наибольшее значение целевой функции F = 10x1 + 11x2 +12x3 > max,
при ограничениях
0,8x1 + 0,5x2 +0,6x3 80
0,4x1 + 0,4x2+0,3x3 60
x1 ? 0, x2? 0, x3? 0.
Подчеркнем, что каждое неравенство в системе функциональных ограничений отвечает в этом случае тому или другому производственному участку, а именно: первое - участку А , второе - участку В , третье - участку С.
2. Создание и отладка табличной модели линейного программир о вания. На основе символической модели ЛП создается ее представление в Excel . Последовательность действий при решении задачи о распределении ресурсов с п о мощью информационной технологии MS Excel
1. Создать табличную модель средствами электронной таблицы MS Excel. (Смотри Таблица 1.).
2. Для решения задачи создать экрану форму ввода условий задачи: переменных, целевой функции, ограничений и предельных условий. Ввести исходные данные в экранную форму: коэффициенты целевой функции, коэффициенты при переменных в ограничениях, правые части ограничений
Выходные данные задачи об использовании производственных ресурсов. Таблица 1.
3. Ввести необходимые формулы в экранную форму: формулу для расчета целевой функции, формулы для расчета левых частей ограничений.
Рисунок 4 Режим проверки формул
3. Попытка оптимизации модели с помощью надстройки ПОИСК РЕШЕНИЯ.
1. Оптимизировать задачу (меню Сервис команда Поиск решения). Для этого в диалоговом окне Поиск решения задать ячейку целевой функции, направление оптимизации целевой функции, ввести ячейки со значениями переменных, изменяемые ячейки, ограничения.
Рисунок 5 Диалоговое окно Поиск решения
В диалоговом окне Поиск решения в поле Установит целевую ячейку делаем ссылку на ячейку $E$11, в которой находится формула, для оптимизации модели.
Для того, чтобы максимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Максимальному значению.
В поле ввода Изменяя ячейки введите адреса ячеек, которые изменяют свои значения, разделяя их запятыми. Для этого делаем ссылку на ячейки $B$5:$D$5.
В поле Ограничения введите все ограничения, которые налагаются на поиск решения. Для этого нажимаем кнопку Добавить и появится окно Добавить ограничения где нужно ввести ограничение. Если при вводе ограничений возникает необходимость в замене или удалении внесенных ограничений, то нажмите кнопки Изменить или Удалить.
2. Для установления конкретных параметров решения задачи необходимо нажать кнопку Параметры в окне Поиск решения. В окне Параметры поиска решения отметить Линейная модель, Неотрицательные значения что обеспечивает ускорение поиска решения линейной задачи. Подтверждение установленных параметров осуществляется нажатием кнопки Ок.
3. Нажмите кнопку Выполнить в окне Поиск решения для запуска решения задачи.
4. Для сохранения найденного решения установите переключатель в диалоговом окне Результаты поиска решения в положение Сохранить найденное решение. Для возобновления входных данных установите переключатель в положение Восстановить исходные значения. В окне Результаты поиска решения представлены названия трех типов отчета: Результаты, Устойчивость, Пределы. Они необходимы для анализа полученного результата на чувствительность.
5. Для получения ответа (значений переменных, целевой функции и левых частей ограничения) нужно нажать кнопку Ок. После этого в экранной форме появится оптимальное решение задачи.
Рисунок 6 Оптимальное решение
6. Вывод : как видно из решения, оптимальный план выпуска продукции предусматривает изготовление 25кг конфет А и 120кг конфет В . Конфеты С вообще невыгодно производить. Прибыль будет составлять 1570грн.
Размещено на Allbest.ru
Подобные документы
Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа , добавлен 29.05.2015
Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа , добавлен 20.11.2010
Ознакомление с разнообразными надстройками, входящими в состав Microsoft Excel; особенности их использования. Примеры решения задач линейного программирования с помощью вспомогательных программ "Подбор параметра", "Поиск решения" и "Анализ данных".
реферат , добавлен 25.04.2013
Краткие сведения об электронных таблицах MS Excel. Решение задачи линейного программирования. Решение с помощью средств Microsoft Excel экономической оптимизационной задачи, на примере "транспортной задачи". Особенности оформления документа MS Word.
курсовая работа , добавлен 27.08.2012
Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа , добавлен 09.12.2008
Принципы решения задач линейного программирования в среде электронных таблиц Excel, в среде пакета Mathcad. Порядок решения задачи о назначении в среде электронных таблиц Excel. Анализ экономических данных с помощью диаграмм Парето, оценка результатов.
лабораторная работа , добавлен 26.10.2013
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа , добавлен 21.03.2012
Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа , добавлен 10.06.2014
Особенности задач линейного программирования. Симплексный метод решения задач линейного программирования. Обоснование выбора языка, инструментария программирования, перечень идентификаторов и блок-схема алгоритма. Логическая схема работы программы.
дипломная работа , добавлен 13.08.2011
Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.
МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- математические модели решения экономических задан, представленные в форме задач линейного программирования. Целевая функция, связи и в такой модели выражены в виде линейных уравнений.
Экономика и право: словарь-справочник. - М.: Вуз и школа . Л. П. Кураков, В. Л. Кураков, А. Л. Кураков . 2004 .
Смотреть что такое "МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ" в других словарях:
Математические модели решения экономических задач, представленные в форме задач линейного программирования. Целевая функция, связи и ограничения в такой модели выражены в виде линейных соотношений. Райзберг Б.А., Лозовский Л.Ш., Стародубцева Е.Б … Экономический словарь
модели линейного программирования - математические модели решения экономических задач, представленные в форме задач линейного программирования. Целевая функция, связи и ограничения в такой модели выражены в виде линейных соотношений … Словарь экономических терминов
МОДЕЛЬ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В МЕНЕДЖМЕНТЕ - вид модели, который применяют для определения оптимального способа распределения дефицитных ресурсов при наличии конкурирующих потребностей. Некоторые типичные применения этого метода в управлении производством: планирование ассортимента изделий; … Большой экономический словарь
Модели в экономике используются начиная с 18 в. В «Экономических таблицах» Ф. Кенэ, которые К. Маркс назвал идеей «...бесспорно самой гениальной из всех, какие только выдвинула до сего времени политическая экономия» (Маркс К. и Энгельс Ф., Соч.,… …
I Модели в биологии применяются для моделирования (См. Моделирование) биологических структур, функций и процессов на разных уровнях организации живого: молекулярном, субклеточном, клеточном, органно системном, организменном и популяционно … Большая советская энциклопедия
Модели экономических объектов или процессов, при описании которых используются математические средства. Цели создания Э. м. м. разнообразны: они строятся для анализа тех или иных предпосылок и положений экономической теории, логического… … Большая советская энциклопедия
- (scarcity) Свойство (товаров или производственных факторов), состоящее в том, что при нулевой цене спрос на них (по сравнению с предложением) будет чрезмерно высоким. Это значит, что в условиях равновесия цена дефицитного товара или фактора… … Экономический словарь
Построение, разработка и приложения математич. моделей принятия оптимальных решений. Содержанием теоретич. аспекта И. о. являются анализ и решение математич. задач выбора в заданном множестве допустимых решений Xэлемента, удовлетворяющего тем или … Математическая энциклопедия
- (НИР и ОКР, applied research, research and development R D) – научные исследования, направленные на решение социально практических проблем. Наука (science) сфера человеческой деятельности, функцией которой является выработка и теоретическая… … Википедия
Математическая дисциплина, предметом к рой являются модели экономич. объектов и процессов и методы их исследования. Однако понятия, результаты, методы М. э. удобно и принято излагать в тесной связи с их экономич. происхождением, интерпретацией и… … Математическая энциклопедия
Книги
- Экономико-математические методы и модели в коммерческой деятельности. Учебник , Г. П. Фомин. В учебнике рассмотрены операции, экономические показатели, схема образования прибыли, структура связи экономических и математических методов, методы и модели изучения, анализа и…
- Методы и модели оптимизации управленческих решений. Учебное пособие , А. Р. Урубков, И. В. Федотов. В учебном пособии изложены принципы оптимизации управленческих решений на основе методов и моделей линейного программирования. На примерах реальных бизнес-ситуаций показано, как, используя…
Рассмотренные выше модели можно отнести к разряду статических моделей линейного программирования, поскольку в них временной интервал был фиксирован. Если возникает необходимость найти решение для другого временного интервала, то нужно заново вводить данные в модель и производить новую оптимизацию. Иначе говоря, в подходе, рассмотренном выше, предполагалось, что все временные интервалы являются независимыми и для каждого временного интервала должна решаться своя задача оптимизации.
В динамических моделях
рассматривается поведение системы на нескольких временных интервалах, а поиск решения производится один раз, оптимизируя поведение модели на всех временных интервалах сразу.
Динамические модели являются более реалистическими и более адекватно описывают многие производственные ситуации. Зависимость принятия решения от поведения системы во времени делает динамические модели исключительно полезным методом экономического анализа, но они оказываются значительно сложнее статических по своей постановке, содержат, как правило, большое число переменных, требуют определенного навыка при составлении табличной модели.
В качестве примера рассмотрим практически значимую модель управления производственными запасами (другое название этой модели – многофазовые модели управления запасами
). Для общности результатов мы не будем присваивать параметрам числовые значения. После построения модели можно будет задать явные значения параметров и получить численное решение.
Пример 3.10
Рассмотрим химическую фирму, производящую полиуретан. Производитель имеет заказы на поставку полиуретана в количестве d i тонн в месяц на ближайшие четыре месяца (i=1,2,…,4). Пусть затраты на производство одной тонны полиуретана составляют C i тыс. рублей, а максимальный объем производства полиуретана по месяцам ограничен и равен K i тонн в месяц. Производственная фирма имеет возможность хранить продукцию на складе, причем стоимость хранения одной тонны продукции за месяц составляет n i тыс. рублей. На начальный период времени запас полиуретана на складе составлял L 0 тонн. Менеджеру компании требуется составить план производства полиуретана по месяцам, который бы обеспечил выполнение заказов при минимальной стоимости производства и хранения продукта.
Решение
Заметим, что если бы не было возможности хранить продукцию на складе, то задача разбилась бы на четыре независимые статические задачи и потеряла бы для нас всякий смысл.
Составим уравнение материального баланса, позволяющего вычислить количество продукции, хранящееся на складе в течение i-го месяца. Пусть x i – количество полиуретана, произведенного в i-й временной период. Тогда в течение первого месяца товарный запас на складе будет равен L 1 =L 0 +x 1 -d 1 . Товарный запас второго месяца
Продолжая этот процесс, легко получить общую формулу товарных запасов для любого временного интервала :
. (3.24)
После того как мы вывели уравнение (3.24), описывающее поведение товарных запасов, легко записать математическую модель задачи:
(3.25)
Поставленная задача (3.25) является типичной задачей линейного программирования и может быть достаточно легко решена с помощью программы Поиск решения.
Используя численные значения удельных затрат производства
и необходимого объема поставок и производственных мощностей по месяцам
требуется составить оптимальный план производства полиуретана, если на первое января запас полиуретана на складе составлял 15 тонн.
Табличная модель задачи управления запасами
Табличная модель задачи после нахождения оптимального решения приведена на рис. 21.
Рис. 21. Табличная модель задачи динамического программирования
Следует сказать несколько слов и об отчете по устойчивости для этой модели, приведенном на рис. 22.
Рис. 22. Отчет по устойчивости для динамической модели
Если используется простое ограничение на значение оптимизируемых переменных (x i ≤K i в нашем случае), то в отчете по устойчивости теневые цены для этих ограничений помещаются в столбце нормированная стоимость, а информация о допустимом диапазоне теневых цен для этих ограничений не выводится. Таким образом, если увеличить на одну тонну производственные мощности в январе, то общие затраты уменьшатся на 1,7 тыс. рублей.
Требует дополнительных пояснений и столбец Целевой коэффициент отчета по устойчивости. Приведенные здесь значения Excel вычисляет самостоятельно. Смысл целевого коэффициента при переменной состоит в том, что он показывает, насколько увеличится значение целевой функции при увеличении оптимального значения переменной на единицу.
В этом легко убедиться на практике. Оптимальное значение производства полиуретана в январе – 60 тонн, а суммарные затраты равны 4 776,45 тыс. рублей. Если в качестве оптимального значения за январь подставить число 61 и пересчитать суммарные затраты, то получим новое значение – 4 805,50. Разность этих чисел как раз и равна 29,05 – целевому коэффициенту при переменной объема производства в январе.
Широко известны и другие постановки задач динамического программирования. Некоторые из них (модель замены оборудования и модель инвестиций) будут рассмотрены на практических занятиях.
Математическое программирование ("планирование") – это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Идея линейного программирования возникла в 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича "Математические методы организации и планирования производства". Американский математик А. Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода ).
Дальнейшее изложение материала предполагает, что студенты изучали теорию линейного программирования в курсе математики. В связи с этим рекомендуется совмещать чтение этой главы с просмотром презентаций. Электронные версии презентаций размещены в папке «Линейное программирование». При этом часть материала предназначена для восстановления знаний, полученных в курсе математики, а часть для их расширения и углубления с акцентом на прикладные возможности теоретических моделей.
Теория линейного программирования
Общая постановка задачи
Идея линейного программирования представлена в формате презентаций, электронная версия которых размещена в файле «Идея - линейное программирование».
Геометрическая интерпретация и графический метод решения
Графически способ решения задач линейного программирования целесообразно использовать:
1. Для решения задач с двумя переменными, когда ограничения выражены неравенствами.
2. Решения задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных.
Геометрический метод решения задач линейного программирования представлен в формате презентации - файл «Геометрический метод ЛП»
2.2. Симплекс-метод, общая характеристика, критерий оптимальности допустимого базисного плана
Графический способ решения задачи линейного программирования показывает, что оптимальное решение этой задачи всегда ассоциируется с угловой точкой пространства решений (в математике она также называется крайней точкой множества ). Это является ключевой идеей при разработке общего алгебраического симплекс-метода для решения любой задачи линейного программирования.
Переход от геометрического способа решения задачи линейного программирования к симплекс-методу лежит через алгебраическое описание крайних точек пространства решений. Для реализации этого перехода сначала надо привести задачу линейного программирования к стандартной (канонической) форме:
· преобразовать неравенства ограничений в равенства путем введения дополнительных переменных;
· преобразовать свободные переменные в неотрицательные;
· преобразовать задачу максимизации в задачу минимизации.
Стандартная форма задачи линейного программирования необходима, потому что она позволяет получить базисное решение (используя систему уравнений, порожденную ограничениями). Это (алгебраическое) базисное решение полностью определяет все (геометрические) крайние точки пространства решений. Симплекс-метод позволяет эффективно найти оптимальное решение среди всех базисных.
Восстановить знания по решению задач симплекс-методом можно с помощью презентации «Симплекс метод».
Двойственные задачи
Любая задача линейного программирования имеет двойственную природу. Правило построения двойственной задачи:
Если исходная задача на max, то двойственная на min и наоборот.
В двойственной задаче столько переменных, сколько ограничений в исходной постановке. При этом переменные соответствуют ограничениям и наоборот.
Коэффициентами целевой функции двойственной задачи являются правые части ограничений исходной задачи.
Матрица коэффициентов ограничений двойственной задачи получается транспонированием матрицы коэффициентов ограничений исходной задачи.
Правыми частями ограничений двойственной задачи являются коэффициенты целевой функции исходной.
Ограничениям неравенствам исходной задачи соответствуют неотрицательные переменные двойственной задачи, а ограничениям равенствам – переменные любого знака и наоборот.
Теорема 1: Если исходная задача имеет оптимальный план x*, то двойственная задача также имеет оптимальный план y*, причем значения функций на этих планах равны: f(x*)=g(y*).
Теорема 2: Если исходная и двойственная задачи имеют планы, то они имеют и оптимальные планы, причем f(x*)=g(y*).
Признаки оптимальности для двойственных задач:
Признак 1: Если исходная и двойственная задачи имеют планы X и Y, причем f(X)=g(Y), то эти планы оптимальные.
Определение: Ограничения, расположенные на одной строке в схеме пары двойственных задач, называют сопряженными.
Признак 2: Для того, чтобы планы X и Y исходной и двойственной задач были оптимальны, необходимо и достаточно чтобы на этих планах хотя бы одно из каждой пары сопряженных ограничений являлось равенством.
Второй признак позволяет, зная оптимальный план одной из задач, найти оптимальный план другой задачи.
Основные положения двойственной задачи изложены в презентациях «Теория двойственности» и «Двойственная задача».
Транспортные задачи
Транспортная задача является одной из наиболее распространенных специальных задач линейного программирования. Первая строгая постановка транспортной задачи принадлежит Ф. Хичкоку, а первый точный метод решения разработан Л. В. Канторовичем и М. К. Гавуриным.
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов. Различают два типа транспортных задач: по критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).
Наиболее часто встречаются следующие задачи, относящиеся к транспортным:
· прикрепление потребителей ресурса к производителям;
· привязка пунктов отправления к пунктам назначения;
· взаимная привязка грузопотоков прямого и обратного направлений;
· отдельные задачи оптимальной загрузки промышленного оборудования;
· оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.
Постановки задач транспортного типа, алгоритмы их решения и примеры практического использования представлены в трех презентациях:
1. «Обобщенная транспортная задача (λ-задача)».
2. «Закрытая транспортная задача. Метод потенциалов».
3. «Усложнённые постановки транспортной задачи».
Экономические приложения
Многообразие экономических приложений математического моделирования методами линейного программирования рассмотрим на примерах формулирования конкретных постановок прикладных задач (заимствовано из курса лекций Диязитдиновой А.П.).
Задача 1
Для сохранения нормальной жизнедеятельности человек должен в сутки потреблять белков не менее 120 условных единиц (усл. ед.), жиров – не менее 70 и витаминов – не менее 10 усл. ед. Содержание их в каждой единице продуктов П 1 и П 2 равно соответственно (0,2; 0,075; 0) и (0,1; 0,1; 0,1) усл. ед.
Стоимость 1 ед. продукта П 1 – 2 руб., П 2 –3 руб.
Постройте математическую модель задачи, позволяющую так организовать питание, чтобы его стоимость была минимальной, а организм получил необходимое количество питательных веществ.
Задача 2
Из пункта А в пункт В ежедневно отправляются пассажирские и скорые поезда. Данные об организации перевозок следующие:
Сколько должно быть сформировано скорых и пассажирских поездов, чтобы перевезти наибольшее количество пассажиров?
Задача 3
Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 тонны. Овощехранилища имеют соответственно 20, 20 ,15 и 25 тонн. Тарифы (в д.е. за 1 тонну) указаны в следующей таблице:
Задача 4
Имеются два склада готовой продукции: А 1 и А 2 с запасами однородного груза 200 и 300 тонн. Этот груз необходимо доставить трем потребителям В 1 , В 2 и В 3 в количестве 100, 150 и 250 тонн соответственно. Стоимость перевозки 1 тонны груза из склада А 1 потребителям В 1 , В 2 и В 3 равна 5, 3 ,6 д.е., а из склада А 2 тем же потребителям – 3, 4, 2 д.е. соответственно.
Составьте план перевозок, минимизирующий суммарные транспортные расходы.
Задача 5
При откорме каждое животное должно получить не менее 9 ед. белков, 8 ед. углеводов и 11 ед. протеина. Для составления рациона используют два вида корма, представленных в следующей таблице.
Стоимость 1 кг корма первого вида – 4 д.е., второго – 6 д.е.
Составьте дневной рацион питательности, имеющий минимальную стоимость.
Задача 6
Хозяйство располагает следующими ресурсами: площадь – 100 ед., труд – 120 ед., тяга – 80 ед. Хозяйство производит четыре вида продукции: П 1 , П 2 , П 3 и П 4 . Организация производства характеризуется следующей таблицей:
Составьте план выпуска продукции, обеспечивающий хозяйству максимальную прибыль.
Задача 7.
Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа – 3 тонны, проволоки – 18 тонн. На один трансформатор первого вида расходуются 5 кг железа и 3 кг проволоки, а на один трансформатор второго вида расходуются 3 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д.е., второго – 4 д.е.
Составьте план выпуска трансформаторов, обеспечивающий заводу максимальную прибыль.
Задача 8
Совхоз отвел три земельный массива размером 5000, 8000 и 9000 га на посевы ржи, пшеницы, кукурузы. Средняя урожайность в центнерах на 1 га по массивам указана в следующей таблице:
| Посевы | Массивы | ||
| I | II | III | |
| рожь | |||
| пшеница | |||
| кукуруза |
За 1 центнер ржи совхоз получает 2 д.е., за 1 центнер пшеницы – 2,8 д.е., за 1 центнер кукурузы – 1,4 д.е. Сколько гектаров и на каких массивах совхоз должен отвести на каждую культуру, чтобы получить максимальную выручку, если по плану он обязан сдать не менее 1900 тонны ржи, 158 000 тонны пшеницы и 30 000 тонн кукурузы?
Задача 9
Из трех продуктов – I, II, III составляется смесь. В состав смеси должно входить не менее 6 ед. химического вещества А, 8 ед. – вещества В и не менее 12 ед. вещества С. Структура химических веществ приведена в следующей таблице:
| Продукт | Содержание химического вещества в 1 ед. продукции | Стоимость 1 ед. продукции | ||
| А | В | С | ||
| I | ||||
| II | ||||
| III | 1,5 | 2,5 |
Составьте наиболее дешевую смесь.
Задача 10
В школе проводится конкурс на лучшую стенгазету. Одному школьнику дано следующее поручение:
купить акварельной краски по цене 30 д.е. за коробку, цветные карандаши по цене 20 д.е. за коробку, линейки по цене 12 д.е., блокноты по цене 10 д.е.;
красок нужно купить не менее трех коробок, блокнотов – столько, сколько коробок карандашей и красок вместе, линеек не более пяти. На покупки выделяется не менее 300 д.е.
В каком количестве школьник должен купить указанные предметы, чтобы общее число предметов было наименьшим?
Задача 11
Имеются три специализированные мастерские по ремонту двигателей. Их производственные мощности равны соответственно 100, 700, 980 ремонтов в год. В пяти районах, обслуживаемых этими мастерскими, потребность в ремонте равна соответственно 90, 180, 150, 120, 80 двигателей в год. Затраты на перевозу одного двигателя из районов к мастерским следующие:
| Районы | Мастерские | ||
| 4,5 | 3,7 | 8,3 | |
| 2,1 | 4,3 | 2,4 | |
| 7,5 | 7,1 | 4,2 | |
| 5,3 | 1,2 | 6,2 | |
| 4,1 | 6,7 | 3,1 |
Спланируйте количество ремонтов каждой мастерской для каждого из районов, минимизирующее суммарные транспортные расходы.
Задача 12
Нефтеперерабатывающий завод получает четыре полуфабриката: 400 тыс. л алкилата, 250 тыс. л крекинг-бензина, 350 тыс. л бензина прямой перегонки и 100 тыс. л изопентона. В результате смешивания этих четырех компонентов в разных пропорциях образуются три сорта авиационного бензина: бензин А-2:3:5:2, бензин В-3:1:2:1, бензин С-2:2:1:3. Стоимость 1 тыс. л указанных сортов бензина характеризуется числами 120 д.е., 100 д.е., 150 д.е.
Составьте план выпуска разных сортов авиационного бензина из условия получения максимальной стоимости всей продукции.
Задача 13
Для участия в соревнованиях спортклуб должен выставить команду, состоящую из спортсменов I и II разрядов. Соревнования проводятся по Буге, пряжкам в высоту, прыжкам в длину. В беге должны участвовать 5 спортсменов, в прыжках в длину – 8 спортсменов, а в прыжках в высоту – не более 10. количество очков, гарантируемых спортсмену каждого разряда по каждому виду, указано в таблице:
Распределите спортсменов в команды так, чтобы сумма очков команды была наибольшей, если известно, что в команде I разряд имеют только 10 спортсменов.
Задача 14
Звероферма выращивает черно-бурых лисиц и песцов. На звероферме имеется 10 000 клеток. В одной клетке могут быть либо 2 лисицы, либо 1 песец. По плану на ферме должно быть не менее 3000 лис и 6000 песцов. В одни сутки необходимо выдавать каждой лисе корма – 4 ед., а каждому песцу – 5 ед. Ферма ежедневно может иметь не более 200 000 единиц корма. От реализации одной шкурки лисы ферма получает прибыль 10 д.е., а от реализации одной шкурки песца – 5 д.е.
Какое количество лисиц и песцов нужно держать не ферме, чтобы получить наибольшую прибыль?
Задача 15
Имеются два элеватора, в которых сосредоточено соответственно 4200 и 1200 тонн зерна. Зерна необходимо перевезти трем хлебозаводам в количестве 1000, 2000 и 1600 тонн каждому. Расстояние от элеватора до хлебозавода указано в следующей таблице:
Затраты на перевозку 1 тонны продукта на 1 км составляют 25 д.е. Спланируйте перевозки зерна из условия минимизации транспортных расходов.
Задача 16
Из двух сортов бензина образуются две смеси – А и В. Смесь А содержит Бензина 60% 1-го сорта и 40% 2-го сорта; смесь В – 80% 1-го сорта и 20% 2-го сорта. Цена 1 кг смеси А – 10 д.е., а смеси В – 12 д.е.
Составьте план образования смесей, при котором будет получен максимальный доход, если в наличии имеется бензин 50 т 1-госорта и 30 т второго сорта.
Задача 17
Имеются две почвенно-климатические зоны, площади которых соответственно равны 0,8 и 0,6 млн. га. Данные об урожайности зерновых культур приведены в таблице:
Определите размеры посевных площадей озимых и яровых культур, необходимые для достижения максимального выхода продукции в стоимостном выражении.
Задача 18
На заводе выпускают изделия четырех типов. От реализации 1 ед. каждого изделия завод получает прибыль соответственно 2, 1, 3, 5 д.е. На изготовление изделий расходуются ресурсы трех видов: энергия, материалы, труд.
Данные о технологическом процессе приведены в следующей таблице:
Спланируйте производство так, чтобы прибыль от их реализации была наибольшей.
