Модели и методы линейного программирования

Размещено на 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

0,1x2+0,1x3 12;

x1 ? 0, x2? 0, x3? 0.

Подчеркнем, что каждое неравенство в системе функциональных ограничений отвечает в этом случае тому или другому производственному участку, а именно: первое - участку А, второе - участку В, третье - участку С.

2. Создание и отладка табличной модели линейного программирования. На основе символической модели ЛП создается ее представление в Excel. Последовательность действий при решении задачи о распределении ресурсов с помощью информационной технологии MS Excel

1. Создать табличную модель средствами электронной таблицы MS Excel. (Смотри Таблица 1.).

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

Выходные данные задачи об использовании производственных ресурсов. Таблица 1.

3. Ввести необходимые формулы в экранную форму: формулу для расчета целевой функции, формулы для расчета левых частей ограничений.

Рисунок 4 Режим проверки формул

3. Попытка оптимизации модели с помощью надстройки ПОИСК РЕШЕНИЯ.

В диалоговом окне Поиск решения в поле Установит целевую ячейку делаем ссылку на ячейку $E$11, в которой находится формула, для оптимизации модели.

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

В поле ввода Изменяя ячейки введите адреса ячеек, которые изменяют свои значения, разделяя их запятыми. Для этого делаем ссылку на ячейки $B$5:$D$5.

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

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

3. Нажмите кнопку Выполнить в окне Поиск решения для запуска решения задачи.

4. Для сохранения найденного решения установите переключатель в диалоговом окне Результаты поиска решения в положение Сохранить найденное решение. Для возобновления входных данных установите переключатель в положение Восстановить исходные значения. В окне Результаты поиска решения представлены названия трех типов отчета: Результаты, Устойчивость, Пределы. Они необходимы для анализа полученного результата на чувствительность.

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

Рисунок 6 Оптимальное решение

6. Вывод: как видно из решения, оптимальный план выпуска продукции предусматривает изготовление 25кг конфет А и 120кг конфет В. Конфеты С вообще невыгодно производить. Прибыль будет составлять 1570грн.

Размещено на Allbest.ru