Ее применяют для определения оптимального способа распределения дефицитных ресурсов при наличии конкурирующих потребностей. Согласно опросу журналом «Форчун» вице-президентов по производству из 500 фирм, модели линейного программирования и управления запасами пользуются в промышленности наибольшей популярностью. Линейное программирование обычно используют специалисты штабных подразделений для разрешения производственных трудностей. Некоторые типичные применения этого метода в управлении производством перечислены в табл. 4.
Таблица 4. Типичные варианты применения линейного программирования в управлении производством
Укрупненное планирование производства. Составление графиков производства, минимизирующих общие издержки с учетом издержек в связи с изменением ставки процента, заданных ограничений по трудовым ресурсам и уровням запасов. |
Планирование ассортимента изделий. Определение оптимального ассортимента продукции, в котором каждому ее виду свойственны свои издержки и потребности в ресурсах (например, определение оптимальной структуры производства компонентов для бензина, красок, продуктов питания для человека, кормов для животных). |
Маршрутизация производства изделия. Определение оптимального технологического маршрута изготовления изделия, которое должно быть последовательно пропущено через несколько обрабатывающих центров, причем каждая операция центра характеризуется своими издержками и производительностью. |
Управление технологическим процессом. Сведение к минимуму выхода стружки при резке стали, отходов кожи или ткани в рулоне или полотнище. |
Регулирование запасов. Определение оптимального сочетания продуктов на складе или в хранилище. |
Календарное планирование производства. Составление календарных планов, минимизирующих издержки с учетом расходов на содержание запасов, оплату сверхурочной работы и заказов на стороне. |
Планирование распределения продукции. Составление оптимального графика отгрузки с учетом распределения продукции между производственными предприятиями и складами, складами и магазинами розничной торговли. |
Определение оптимального местоположения нового завода. Определение наилучшего пункта местоположения путем оценки затрат на транспортировку между альтернативными местами размещения нового завода и местами его снабжения и сбыта готовой продукции. |
Календарное планирование транспорта. Минимизация издержек подачи грузовиков под погрузку и транспортных судов к погрузочным причалам. |
Распределение рабочих. Минимизация издержек при распределении рабочих по станкам и рабочим местам. |
Перегрузка материалов. Минимизация издержек при маршрутизации движения средств перегрузки материалов (например, автопогрузчиков) между отделениями завода и доставке материалов с открытого склада к местам их переработки на грузовых автомобилях разной грузоподъемности с разными технико-экономическими характеристиками. |
Нижеследующий пример иллюстрирует простую ситуацию, в которой для принятия решения следует воспользоваться моделью линейного программирования. Управляющий производством должен решить, сколько галлонов краски каждого из трех ее типов следует производить, чтобы получить наивысшую прибыль. На решение налагается несколько ограничений:
1. В наличии имеется только 40 тыс. фунтов исходных реагентов - 10 тыс. фунтов реагента А, 18 тыс. фунтов реагента В и 12 тыс. фунтов реагента С.
2. Общее время работы оборудования 30 тыс. ч.
3. На один галлон краски типа 1 расходуется один фунт реагента А, 3/4 фунта реагента В и 1 1/2 фунта реагента С, а также 1/8 ч времени работы оборудования. На один галлон краски типа 2 требуется один фунт реагента А, 1/2 фунта реагента В и 3/4 фунта реагента С, а также 1/4 ч работы оборудования. На один галлон краски типа 3 идет 1 1/4 фунта реагента А, 1 1/4 фунта реагента В и 1 1/2 реагента С при 1/6 ч времени работы оборудования.
4. Чистая прибыль от продажи одного галлона краски типов 1,2 и 3 составляет 0,80, 0,65 и 1,25 долл. соответственно.
Задача проиллюстрирована рис. 7. С помощью модели линейного программирования управляющий может определить, какое количество краски каждого типа производить при известных запасах реагентов и имеющемся резерве времени работы оборудования, а также с учетом вклада в прибыль краски каждого типа. Не имея такой модели, крайне сложно принять оптимальное решение даже в сравнительно простой ситуации.
Рис. 7. Модель линейного программирования (линейное программирование применяется для решения задач с несколькими переменными, как например, задачи об ассортименте красок в тексте).
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на 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) сфера человеческой деятельности, функцией которой является выработка и теоретическая… … Википедия
Математическая дисциплина, предметом к рой являются модели экономич. объектов и процессов и методы их исследования. Однако понятия, результаты, методы М. э. удобно и принято излагать в тесной связи с их экономич. происхождением, интерпретацией и… … Математическая энциклопедия
Функция f(x) называется целевой функцией
, а Х - множеством допустимых решений
. Оптимальным решением
задач называется пара (x*,f(x*)) , где x* - точка максимума (минимума), а f(x*) , - значение функции f в этой точке, то есть ее максимальное (минимальное) значение на множестве Х
.
Решить задачи это значит: либо найти оптимальное решение; либо убедиться, что оптимальное решение не существует.
Решение задачи требует разрешения трех проблем: 1) проблему существования оптимального решения; 2) проблему установления необходимых и достаточных признаков оптимальности (то есть характерных свойств, присущих точкам максимума и минимума); 3) проблему численного вычисления оптимальных решений.
Пример №1 . Построить математическую модель следующей задачи экономической деятельности. Для этого:
Перед проектировщиками автомобиля поставлена задача сконструировать самый дешевый кузов, используя листовой материал, стекло и пластмассу. Основные характеристики материалов представлены в таблице.
| Характеристики | Материалы | ||
| Металл | Стекло | Пластмасса | |
| Стоимость (тыс. руб./м 2) | 25 | 20 | 40 |
| Масса (кг/м 2) | 10 | 15 | 3 |
Общая поверхность кузова (вместе с дверьми и окнами) должна составлять 14 м 2: из них не менее 3,5 м 2 и не более 5 м 2 следует отвести под стекло. Масса кузова не должна превышать 150 кг, а масса пластмассы не должна превышать 20% от массы кузова. Металлическая составляющая поверхности кузова должна превышать стеклянную поверхность не менее, чем в два раза. Сколько металла, стекла и пластмассы должен использовать наилучший проект.
Проблема заключается в ограниченных ресурсах для получения оптимального результата.
Описание переменных.
x 1 - количество металла, м 2
x 2 - количество стекла, м 2
x 3 - количество пластмассы, м 2
Функция цели.
Ограничения:
Система ограничений.
x 1 + x 2 + x 3 ≥ 14
10x 1 + 15x 2 + 3x 3 ≤ 150
2x 1 + 3x 2 - 2,4x 3 ≥ 0
x 1 - 2x 2 ≥ 0
x 2 ≥ 3,5
x 2 ≤ 5
x 1 , x 2 , x 2 ≥ 0
F(x) = 25x 1 + 20x 2 + 40x 3 → min
Пример №2 . На фабрике производится ткань двух артикулов. Каждая из этих тканей проходит последовательную обработку на станках их трех типов. Ниже указаны: производительность станка каждого типа при изготовлении тканей артикулов 1 и 2; суммарные мощности станочного парка фабрики в расчете на одну рабочую неделю; трудовые затраты по обслуживанию станков в минутах рабочего времени на 1 час работы станка; цена метра ткани каждого артикула. Известно также, что недельный ресурс трудозатрат на обслуживание станков равен 14800 ч.
| Тип станков | Мощность (тыс. ч) | Трудозатраты (мин/ч) | Производительность, м/ч | |
| Артикул 1 | Артикула2 | |||
| 1 | 22 | 10 | 20 | 15 |
| 2 | 40 | 6 | 12 | 6 |
| 3 | 75 | 6 | 6 | 4 |
| Цена 1 м ткани (тыс.руб.) | 18 | 25 | ||
Требуется составить недельный план выпуска тканей с целью максимизации прибыли изготовленной продукции, если 1 час оплачивается в размере 5400 рублей, а 1 час простоя станка 1-го типа составляет 1800 рублей, 2-го типа составляет 2000 рублей, 3-го типа составляет 1400 рублей. Стоимость сырья в расчет не принимать. При решении задачи следует учесть, что выпуск ткани артикула 1 должен не мене чем в 2 раза превышать выпуск ткани артикула 2.
Описание переменных.
x 1 - выпуск тканей артикула 1, м
x 2 - выпуск тканей артикула 2, м
y 1 - время работы 1-го станка, час.
y 2 - время работы 2-го станка, час.
y 3 - время работы 3-го станка, час.
y 1 =x 1 /20 + x 2 /15
y 2 =x 1 /12 + x 2 /6
y 3 =x 1 /6 + x 2 /4
x 1, x 2 , y 1 , y 2 , y 3 ≥ 0
Ограничения:
Функция цели.
Прибыль = Выручка - Затраты = Цена*Количество - Затраты на простой станков - Трудозатраты
Выручка = 18x 1 + 25x 2
Затраты на простой станков =1,8y 1 + 2y 1 + 1,4y 3
Трудозатраты = 5,4(1/6y 1 + 1/10y 2 +1/10y 3)
F(x) = 18x 1 + 25x 2 - 1,8y 1 - 2y 2 - 1,4y 3 - 5,4(1/6y 1 + 1/10y 2 +1/10y 3)→ max
или
F(x) = 1/50 (900x 1 +1250x 2 -135y 1 -127y 2 -97y 3) → max
С учетом
y 1 =x 1 /20 + x 2 /15
y 2 =x 1 /12 + x 2 /6
y 3 =x 1 /6 + x 2 /4
имеем:
Система ограничений.
x 1 ≥ 2x 2
1/6(x 1 /20 + x 2 /15) + 1/10(x 1 /12 + x 2 /6) +1/10(x 1 /6 + x 2 /4) ≤ 14800
x 1 /20 + x 2 /15≤ 22000
x 1 /12 + x 2 /6 ≤ 40000
x 1 /6 + x 2 /4 ≤ 75000
x 1 ≥ 2x 2
x 1 /30+19x 2 /360 ≤ 14800
x 1 /20 + x 2 /15≤ 22000
x 1 /12 + x 2 /6 ≤ 40000
x 1 /6 + x 2 /4 ≤ 75000
F(x) = 17.33x 1 +23.91x 2 → max
Пример №3
. На предприятии имеется два цеха. В первом цеху работают 50 рабочих, из них 20 имеют 6 разряд и 30 - третий разряд. Во втором цеху, из 100 рабочих 50 имеют 6 разряд и остальные - третий. Требуется выполнить заказ на изготовление 2 типов деталей. На изготовление одной детали первого типа рабочий 6 разряда тратит 10 мин., а рабочий 3 разряда - 15 мин. На изготовление одной детали второго типа рабочий 6 разряда тратит 25 мин., а рабочий третьего - 30 мин.
13) составить план выпуска продукции для каждого из цехов на неделю, исходя из стандартной продолжительности рабочей недели, максимизирующий общий объем выпуска продукции с учетом того, что потребность в детали второго типа в два раза меньше потребности в деталях первого типа.
14) Определить план выпуска продукции для каждого из цехов на неделю, исходя из стандартной продолжительности рабочей недели, максимизируя прибыль, с учетом того, что рабочий 6 разряда получает 300 руб./мес., а рабочий 3 разряда - 200 руб./мес., притом, что цена реализации детали 1 типа равна 20 руб./шт, а второго типа - 34 руб./шт.
Решение.
x 11 - количество деталей 1 типа, изготовленные рабочими 6 разряда за неделю,
x 12 - количество деталей 2 типа, изготовленные рабочими 6 разряда за неделю,
x 21 - количество деталей 1 типа, изготовленные рабочими 3 разряда за неделю,
x 22 - количество деталей 2 типа, изготовленные рабочими 3 разряда за неделю,
13) Целевая функция
20x 11 + 50x 21 + 30x 12 + 50x 22 = max
Ограничения:
2(x 12 +x 22) ≤ x 11 +x 21
14) Целевая функция: Прибыль = Доход - Затраты = Количество деталей * Цена реализации - ЗП работников
Затраты на заработную плату рабочим приведем к недельным, т.е разделим месячный заработок на 4.
F(x) = 20(20x 11 + 50x 21) + 23(30x 12 + 50x 22) - [(20+50)*300 + (30+50)*200]/4 = max
Ограничения:
2(x 12 +x 22) ≤ x 11 +x 21
10/60x 11 + 15/60x 21 + 25/60x 11 + 30/60x 21 ≤ N
N - недельный фонд времени в часах.
Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.
Итак, линейное программирование возникло после Второй Мировой Войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической «стройности».
Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.
Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств.
Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:
Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций.
Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:
Выбор компромиcного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи.
При постановке задачи оптимизации необходимо:
1. Наличие объекта оптимизации и цели оптимизации. При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого. Приведем примеры.
Типичный пример неправильной постановки задачи оптимизации:
«Получить максимальную производительность при минимальной себестоимости».
Ошибка заключается в том, что ставится задача поиска оптимальности 2-х величин, противоречащих друг другу по своей сути.
Правильная постановка задачи могла быть следующая:
В первом случае критерий оптимизации - производительность, а во втором - себестоимость.
Обычно оптимизируемая величина связана с экономичностью работы рассматриваемого объекта (аппарат, цех, завод). Оптимизируемый вариант работы объекта должен оцениваться какой-то количественной мерой - критерием оптимальности.
Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.
На основании выбранного критерия оптимальности составляется целевая функция, представляющая собой зависимость критерия оптимальности от параметров, влияющих на ее значение. Вид критерия оптимальности или целевой функции определяется конкретной задачей оптимизации.
Таким образом, задача оптимизации сводится к нахождению экстремума целевой функции.
В зависимости от своей постановки, любая из задач оптимизации может решаться различными методами, и наоборот - любой метод может применяться для решения многих задач. Методы оптимизации могут быть скалярными (оптимизация проводится по одному критерию), векторными (оптимизация проводится по многим критериям), поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.), вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т.д.), теоретико-вероятностными, теоретико-игровыми и др. Подвергаться оптимизации могут задачи как с ограничениями, так и без них.
Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.
В общем виде модель записывается следующим образом:
Целевая функция:
При этом aij, bi, cj () - заданные постоянные величины.
Задача состоит в нахождении оптимального значения функции (1.1) при соблюдении ограничений (1.2) и (1.3).
Систему ограничений (1.2) называют функциональными ограничениями задачи, а ограничения (1.3) - прямыми.
Вектор, удовлетворяющий ограничениям (1.2) и (1.3), называется допустимым решением (планом) задачи линейного программирования. План, при котором функция (1.1) достигает своего максимального (минимального) значения, называется оптимальным.
