Постановка задачи по оптимизации
Построение базовой аналитической модели. Описание вычислительной процедуры. Решение задачи оптимизации на основе симплекс-таблиц. Анализ на чувствительность к изменению. Примеры постановок и решений перспективных оптимизационных управленческих задач.
| Рубрика | Экономико-математическое моделирование |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 16.02.2015 |
| Размер файла | 621,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
- Введение
- 1. Постановка задачи по оптимизации
- 2. Построение базовой аналитической модели
- 3. Обоснование и описание вычислительной процедуры
- 3.1 Обоснование вычислительной процедуры
- 3.2 Описание вычислительной процедуры
- 4. Решение задачи оптимизации на основе симплекс-таблиц
- 4.1 Приведение задачи к стандартной форме
- 4.2 Поиск оптимального решения задачи на основе двухэтапного метода
- 5. Анализ задачи на чувствительность
- 5.1 Анализ на чувствительность к изменению ограничения на использование сырья
- 5.2 Анализ на чувствительность к изменению одного из коэффициентов целевой функции
- 6. Построение модифицированной аналитической модели и анализ результатов модификации
- 7. Примеры постановок и решений перспективных оптимизационных управленческих задач
- 7.1 Пример 1
- 7.2 Пример 2
- Заключение
- Список литературы
- Приложение А
- Приложение Б
- Приложение В
- Приложение Г
Введение
Цель и основные понятия в исследованиях операций
Операция - это всякая система действий (мероприятие), объединенных единым замыслом и направленных к достижению какой-то цели. Это управляемое мероприятие, то есть от нас зависит, каким способом выбрать некоторые параметры, характеризующие его организацию.
Каждый определенный выбор зависящих от нас параметров называется решением.
Целью исследования операций является предварительное количественное обоснование оптимальных решений.
Те параметры, совокупность которых образует решение, называются элементами решения. В качестве элементов решения могут быть различные числа, векторы, функции, физически признаки и т.д.
Чтобы сравнить между собой различные варианты, необходимо иметь какой-то количественный критерий - показатель эффективности (Е). Данный показатель называется целевой функцией.
Этот показатель выбирается так, чтобы он отражал целевую направленность операции. Выбирая решение, стремимся, чтобы данный показатель стремился к максимуму или к минимуму. Если Е - доход, то E max; а если E - расход, то E min.
Задачи линейного программирования
Линейное программирование является наиболее простым и лучше всего изученным разделом математического программирования. Характерные черты задач линейного программирования следующие:
1) показатель оптимальности f(X) представляет собой линейную функцию от элементов решения X = (x1, x2, ... , xn);
2) ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.
Система линейных уравнений и неравенств определяющая допустимое множество решений задачи, называется системой ограничений задачи линейного программирования, а линейная функция f(Х) называется целевой функцией или критерием оптимальности.
Допустимое решение - это совокупность чисел (план) X = (x1, x2, ... , xn), удовлетворяющих ограничениям задачи.
Оптимальное решение - это план, при котором целевая функция принимает свое максимальное (минимальное) значение.
Линейное программирование
Временем рождения линейного программирования принято считать 1939 г., когда была напечатана брошюра Леонида Витальевича Канторовича "Математические методы организации и планирования производства". Поскольку методы, изложенные Л.В. Канторовичем, были мало пригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В. Канторовича осталась почти не замеченной. Однако идеи Л.В. Канторовича не встретили понимания в момент их зарождения, были объявлены ересью, и его работа была прервана.
Американский математик А. Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течение пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.
Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В. Канторович и американец профессор Т. Купманс получили Нобелевскую премию по экономическим наукам за "вклад в разработку теории и оптимального использования ресурсов в экономике".
Оптимизационная задача - это экономико-математическая задача, которая состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений.
Методы решения оптимизационных задач зависят как от вида целевой функции f(Х), так и от строения допустимого множества E. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.
Классификация методов и моделей исследования операций
Существует несколько классификаций методов и моделей исследования операций.
К основным методам отыскания оптимальных решений относятся:
математическое программирование.
В свою очередь методы математического программирования делятся на следующие:
- линейное программирование;
- нелинейное программирование;
- динамическое программирование;
- целочисленное программирование;
- стохастическое программирование;
- эвристическое программирование;
- теория массового обслуживания;
- сетевые модели планирования и управления;
- имитационное моделирование.
Рассмотренные выше классы задач можно решать указанными методами. Методами математического программирования решаются следующие классы задач:
- задачи управления запасами;
- задачи распределения ресурсов;
- задачи замены и ремонта оборудования;
- задачи выбора маршрута.
С помощью теории массового обслуживания решаются задачи массового обслуживания.
С использованием сетевых моделей планирования и управления можно решать:
- задачи массового обслуживания;
- задачи упорядочивания;
- задачи сетевого планирования.
Методом имитационного моделирования решаются комбинированные задачи. Данным методом можно решить задачу любого класса, однако, данный метод не является универсальным. Его применение ограничено следующими факторами:
- требуется наличие высококвалифицированных специалистов, т.к. он содержит в себе элементы всех вышеперечисленных методов;
- решение обходится дороже, чем при использовании других методов.
Основные элементы метода исследования операций
При решении любой конкретной задачи применение методов исследования операций заключается в следующем:
- построение математических, экономических и статистических моделей для задач принятия решений и управления в сложных ситуациях в условиях неопределенности (наличие случайных факторов);
- изучение взаимосвязей, определяющих возможные последствия принятых решений. Установление критериев эффективности, позволяющих оценить преимущества того или иного варианта.
Методы исследования операций обладают рядом специфических черт. Чтобы подход к решению задач можно было считать операционным, он должен содержать следующие элементы:
- ориентация на принятие решений. Основные результаты анализа должны иметь непосредственное и полностью определенное отношение к выбору способа действий (стратегии или тактики);
- оценка на основе критерия экономической эффективности. Сравнение различных возможных вариантов действий должно основываться на количественных оценках, позволяющих однозначно определить полезность ожидаемого исхода. Количественные оценки для коммерческих фирм обычно предполагают использование таких измеримых величин, как расходы, доходы, наличие денежных средств, норма прибыли от дополнительных капиталовложений и т.д. В рекомендуемом решении должен быть достигнут оптимальный баланс с учетом всех, нередко противоречивых факторов;
- доверие математической модели. Процедуры обращения с упомянутыми выше параметрами должны быть определены настолько точно, чтобы любой специалист в области системного анализа смог их трактовать совершенно однозначно. Другими словами: опираясь на одни и те же данные, различные специалисты должны получить одинаковые результаты.
Необходимость использования ЭВМ. Это условие отнюдь не является лишь желательным, оно скорее необходимо. Это обуславливается сложностью используемых математических моделей и большим объемом исходных данных. Вычисления могут быть громоздкими - необходимо использовать ЭВМ; а могут быть несложными, но в больших объемах (статистические модели).
Основные этапы применения метода ИО:
- определение цели;
- составление плана разработки проекта;
- формулировка проблемы;
- построение модели;
- разработка вычислительного метода;
- разработка технического задания на программирование, само программирование и отладка программы;
- сбор данных;
- проверка модели;
- реализация результатов, то есть принятие решения.
Особенности математических методов, применяемых к решению экономических задач
В экономических исследованиях издавна применялись простейшие математические методы. В хозяйственной жизни широко используются геометрические формулы. Так, площадь участка поля определяется путем перемножения длины на ширину или объем силосной траншеи - перемножением длины на среднюю ширину и глубину. Существует целый ряд формул и таблиц, облегчающих хозяйственным работникам определение тех или иных величин.
Не стоит говорить о применении арифметики, алгебры в экономических исследованиях. Особняком здесь стоят так называемые методы оптимизации, чаще называемые как экономико-математические методы.
Несмотря на широту применения метода линейного программирования, он учитывает лишь три особенности экономических задач - большое количество переменных, ограниченность ресурсов и необходимость целевой функции. Конечно, многие задачи с другими особенностями можно свести к линейной оптимизации, но это не дает нам права упустить из виду другой хорошо разработанный метод математического моделирования - динамическое программирование. По сути, задача динамического программирования является описанием многошаговых процессов принятие решений.
Таким образом, метод динамического программирования позволяет учесть такую важную особенность экономических задач, как детерминированность более поздних решений от более ранних.
Кроме этих двух, достаточно детально разработанных методов, в экономических исследованиях в последнее время стали применяться множество других методов.
Кроме этих методов применяются методы нелинейного, целочисленного программирования и многие другие. Вкратце, сущность метода нелинейного программирования заключается в нахождении общего максимума или минимума функции. Основная сложность здесь в трудности определения, является ли этот максимум общим или локальным. Для целочисленного моделирования основная трудность как раз и заключается в трудности подбора целого значения функции. Общим для применения этих методов на современном этапе является возможность частичного сведения их к задаче линейного моделирования. Возможно, в недалеком будущем будет найдено какое-то оригинальное решение таких задач специфическими методами, более удобными, чем современные методы решения подобных задач (для которых они есть), и более точные, нежели приближенные решения методами линейного программирования.
Как можно было заключить из вышеизложенного, математические методы имеют большую степень универсальности. Основой этой универсальности является язык математики. Если исследователи различных специальностей часто говорят об одной и той же проблеме совершенно по-разному, видят разные ее особенности, и не могут связать их воедино; то перевод проблемы на математический язык сразу выявляет общие закономерности, и даже может дать уже практически готовое решение, полученное ранее где-то в другой отрасли знаний и для других целей. То есть предпосылкой использования математики является формализация количественных и качественных сторон проблемы.
То есть имеет смысл говорить о таких особенностях экономических систем, которые требуют принципиально новых методов исследования. В то же время нельзя и отмежевываться от старых, проверенных методов описания. В практике использования формализованного описания огромную роль играет аппроксимация реальных и очень сложных режимов и связей относительно более простыми. Поэтому получать информацию с точностью, необходимой для практики, мы можем, оперируя с относительно простыми пространствами, объектами. Это вовсе не ставит под сомнение необходимость дальнейшего совершенствования языка математики.
1. Постановка задачи по оптимизации
Предприятие может работать по трем технологическим процессам (ТП1, ТП2, ТП3). При работе по первому технологическому процессу предприятие выпускает 300 изделий в день, по второму - 250, по третьему - 450 изделий в день. Расходы ресурсов, необходимые предприятию для работы в течение дня по каждому из технологических процессов, приведены в таблице.
|
Ресурсы |
Технологические процессы |
|||
|
ТП1 |
ТП2 |
ТП3 |
||
|
Рабочая сила, тыс. человеко-ч/день |
15 |
20 |
25 |
|
|
Электроэнергия, тыс. кВт-ч/день |
35 |
60 |
60 |
|
|
Сырье т/день |
20 |
30 |
25 |
Это означает, например, что в случае, если предприятие в течение одного дня работает по технологическому процессу ТП1, то для этого требуется 15 тыс. человеко-ч рабочей силы, 35 тыс. кВт-ч электроэнергии, 20 т сырья.
Предприятие располагает рабочей силой в количестве 1,2 млн. человеко-ч, электроэнергией - 3 млн. кВт-ч, сырьем - 1500 т.
По требованию заказчика необходимо выпустить не менее 500 изделий по второму технологическому процессу.
Найти, сколько времени должно работать предприятие по каждому из технологических процессов, чтобы выпустить максимальное количество изделий.
2. Построение базовой аналитической модели
В данной задаче необходимо определить, сколько времени должно работать предприятие по каждому из технологических процессов, чтобы выпустить максимальное количество изделий.
Для построения математической модели введем следующие переменные: - время работы по первому технологическому процессу, - по второму технологическому процессу и - время работы по третьему технологическому процессу (в днях).
В данной задаче имеются ограничения на расход ресурсов (рабочей силы, электроэнергии, сырья). Так расход рабочей силы по первому технологическому процессу составляет 15 тыс. человеко-ч/день, по второму - 20 тыс. человеко-ч/день, по третьему - 25 тыс. человеко-ч/день. При этом предприятие располагает рабочей силой в количестве 1,2 млн человеко-ч. Поэтому можно записать следующее ограничение:
.
Аналогично можно составить ограничение на расход электроэнергии:
и на расход сырья:
.
Имеется также ограничение на выпуск изделий по второму технологическому процессу - необходимо выпустить не менее 500:
.
Так как по своему физическому смыслу переменные , , обозначают дни, то данные величины не могут иметь отрицательные значения необходимо ввести ещё два ограничения:
В данной задаче необходимо составить план производства максимального количества изделий. При работе по первому технологическому процессу предприятие выпускает 300 изделий в день, значит всего предприятие выпустит изделий, по второму - изделий, по третьему - изделий. Таким образом, общее число изделий по каждому технологическому процессу составит . Требуется найти такие , , , при которых эта величина будет максимальной. Целевая функция для этой задачи будет иметь следующий вид:
.
Приведем полную математическую модель данной задачи:
3. Обоснование и описание вычислительной процедуры
3.1 Обоснование вычислительной процедуры
В задачах линейного программирования, где все ограничения являются неравенствами вида "" (с отрицательной правой частью), дополнительные (остаточные) переменные позволяют формировать начальное допустимое базисное решение. Естественно, что возникает вопрос: как найти начальное допустимое базисное решение в задачах линейного программирования, где есть ограничения в виде равенств или неравенств типа " "?
Как известно, для построения начального базиса необходимо, чтобы в каждом уравнении стандартной формы присутствовала переменная, входящая в данное уравнение с коэффициентом 1 и не входящая в другие уравнения. Из этих переменных и составляется начальный базис (количество переменных в базисе равно количеству ограничений). Если базисные переменные имеются не во всех уравнениях, они создаются с помощью методов искусственного базиса. Это требуется практически всегда, когда в исходной постановке задачи имеются ограничения "не меньше" и/или "равно".
3.2 Описание вычислительной процедуры
Для задач с ограничениями "" обычно нельзя использовать в качестве начального допустимого решения (начальной угловой точки области допустимых решений) начало координат, то есть решение, в котором все исходные переменные математической модели равны нулю. Такое решение, как правило, оказывается недопустимым по причине не соответствия ограничениям. Избыточные переменные использовать в качестве базисных переменных невозможно, так как они входят в уравнения с коэффициентом -1. В случае, когда переменным (исходные переменные) придать нулевые значения, эти избыточные переменные принимают отрицательные значения, и решение оказывается недопустимым, а в уравнениях, которые получены из ограничений-равенств, вообще нет переменных, входящих только в данное уравнение. Поэтому во все ограничения, которые не содержат базисных переменных, вводятся искусственные переменные (по одной в каждое ограничение), используемые для построения начального базиса. На все искусственные переменные (как и на остальные) накладывается требование неотрицательности.
После построения искусственного базиса, придав нулевые значения исходным и избыточным переменным, получим начальный базис из искусственных и остаточных переменных, значения которых равны правым частям ограничений.
Искусственные переменные используются только для получения начального базиса. Они не имеют какого-либо содержательного смысла, связанного с условием задачи; их нельзя интерпретировать как объемы производства, решение, содержащее искусственные переменные, является недопустимым, то есть не соответствует исходной системе ограничений. Поэтому методы решения, которые работают на основе искусственного базиса, должны обеспечить, чтобы в оптимальном решении задачи все искусственные переменные приняли нулевые значения.
В курсовой работе данная задача будет решена двухэтапным методом. Как следует из названия этого метода, процесс решения задачи линейного программирования разбивается на два этапа: на первом этапе ведется поиск начального базисного решения, а затем на основе найденного решения ищется оптимальное решение исходной задачи.
ЭТАП 1.
Задача линейного программирования записывается в стандартной форме, а в ограничения добавляются необходимые искусственные переменные для начального базисного решения. Решается задача линейного программирования минимизации суммы искусственных переменных с исходными ограничениями. Если минимальное значение этой новой целевой функции больше нуля, значит, исходная задача не имеет допустимого решения, и процесс вычислений заканчивается. Если новая целевая функция равна нулю, переходим ко второму этапу.
ЭТАП 2.
Оптимальное базисное решение, полученное на первом этапе, используется как начальное допустимое базисное решение исходной задачи.
Рассмотрим реализацию этого метода оптимизации более подробно. Пусть в задаче, которая представлена в стандартной форме, имеется n-переменных (включая остаточные и избыточные). Базис состоит из m-переменных (m-количество уравнений), из них k-искусственных:
, , … , ().
Метод реализуется следующим образом:
1. Задача сводится к стандартной форме.
2. Выполняется переход к целевой функции, направленной на максимум (если это необходимо).
3. Строится искусственный базис, т.е. вводятся искусственные переменные
, ,…, .
4. Строится искусственная целевая функция, равная сумме искусственных переменных:
.
5. Так как в вычислительных процедурах симплекс-метода целевая функция должна быть выражена только через небазисные переменные, выполняется преобразование функции. Для этого искусственные переменные, которые составляют начальный базис, выражаются через небазисные переменные и затем подставляются в функцию.
6. Для приведения всей задачи к стандартной форме выполняется максимизация искусственной целевой функции. Для этого она умножается на -1.
7. Определяется начальное (недопустимое) решение. Базис состоит из переменных, из них k-искусственные, остальные m-k-остаточные переменные. Если остаточных переменных нет (т.е. в задаче не было ограничений "не больше"), то обычно весь базис составляется из искусственных переменных. Базисные переменные принимают значения, равные правым частям ограничений задачи. Все остальные переменные (исходные и избыточные) считаются равными нулю. В этом случае исходная целевая функция принимает значение 0, а искусственная целевая функция - значение W0.
8. Составляется исходная симплекс-таблица. Она отличается от симплекс-таблицы, используемой для обычного симплекс-метода только тем, что в нее добавляется строка искусственной целевой функции. В этой строке указываются коэффициенты искусственной целевой функции (приведенной к стандартной форме, т.е. подлежащей максимизации) с обратными знаками, как и для обычной целевой функции.
9. Реализуется первый этап двухэтапного метода: с помощью обычных процедур симплекс-метода выполняется минимизация функции W. При этом переменные, включаемые в базис, выбираются по строке искусственной целевой функции (т.е. на каждом цикле в базис включается переменная, соответствующая максимальному по модулю отрицательному коэффициенту в W-строке; столбец, соответствующий этой переменной, становится ведущим). Все преобразования выполняются по обычным формулам симплекс-метода или по "правилу прямоугольника".
10. Выполняется анализ результатов минимизации искусственной целевой функции. Если найденное минимальное значение (W равно 0) и все искусственные переменные оказались небазисными (т.е. равными 0), это означает, что найдено допустимое решение исходной задачи, т.е. решение, которое удовлетворяет исходным ограничениям; выполняется переход к шагу 11. Если в результате минимизации W какие-либо из искусственных переменных приняли ненулевые значения (т.е. вошли в базис), то исходная задача не имеет допустимых решений.
11. Так как все искусственные переменные равны нулю, то строка искусственной целевой функции и все искусственные переменные отбрасываются. Найденное решение на первом этапе используется в качестве начального допустимого решения исходной задачи. Для поиска оптимального решения строится сокращенная симплекс-таблица.
12. Над сокращенной симплекс таблицей выполняются обычные процедуры симплекс-метода (т.е. в Е-строке находится максимальный по модулю отрицательный элемент, соответствующая переменная включается в базис, выбирается переменная для исключения из базиса и т.д.). В результате находится оптимальное решение исходной задачи.
4. Решение задачи оптимизации на основе симплекс-таблиц
Математическая модель решаемой задачи:
4.1 Приведение задачи к стандартной форме
Приведем задачу к стандартной форме. Все ограничения требуется преобразовать в равенства. Для этого в ограничения "меньше или равно" необходимо ввести остаточные переменные. В ограничение "больше или равно" добавляется избыточные переменные. Математическая модель задачи в стандартной форме имеет следующий вид:
В полученной системе уравнений нет базисной переменной в четвертом уравнении. Поэтому для решения задачи требуется использовать методы искусственного базиса.
4.2 Поиск оптимального решения задачи на основе двухэтапного метода
Первый этап (поиск допустимого решения).
Во все ограничения, где нет базисных переменных, вводятся искусственные базисные переменные. В данной задаче их требуется ввести в четвертое ограничение. Система ограничений с искусственными базисными переменными будет иметь следующий вид:
.
Таким образом, начальный базис будет состоять из остаточных переменных , , , а также искусственной переменной .
Составляем искусственную целевую функцию - сумму всех искусственных переменных:
.
Эта целевая функция подлежит минимизации, так как для определения начального допустимого решения необходимо, чтобы все искусственные переменные приняли нулевые значения.
Искусственная целевая функция выражается через небазисные переменные. Для этого сначала требуется выразить искусственную переменную через небазисные переменные:
.
Выраженная таким образом искусственная переменная подставляется в искусственную целевую функцию:
.
Для приведения всей задачи к стандартной форме выполняется переход к искусственной целевой функции, подлежащей максимизации. Для этого она умножается на -1:
.
Приведем полную математическую модель задачи, приведенную к стандартной форме:
Определяется начальное решение. Все исходные, а также избыточные переменные задачи являются небазисными, т.е. принимаются равными нулю. Искусственные, а также остаточные переменные образуют начальный базис: они равны правым частям ограничений. Для рассматриваемой задачи начальное решение следующее: , , , , . Это решение является недопустимым: значения переменных не удовлетворяют постановке задачи. Начальное значение целевой функции Е равно нулю.
Составляется исходная симплекс-таблица. Она отличается от симплекс-таблицы, используемой для обычного симплекс-метода только тем, что в нее добавляется строка искусственной целевой функции. В этой строке указываются коэффициенты искусственной целевой функции (приведенной к стандартной форме, т.е. подлежащей максимизации) с обратными знаками, как и для обычной целевой функции.
Таблица 4.1
|
Базис |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
X 6 |
X 7 |
X 8 |
Решение |
|
|
E |
-300 |
-250 |
-450 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
-W |
0 |
-250 |
0 |
0 |
0 |
0 |
1 |
0 |
-500 |
|
|
X 4 |
15 |
20 |
25 |
1 |
0 |
0 |
0 |
0 |
1200 |
|
|
X 5 |
35 |
60 |
60 |
0 |
1 |
0 |
0 |
0 |
3000 |
|
|
X 6 |
20 |
30 |
25 |
0 |
0 |
1 |
0 |
0 |
1500 |
|
|
X 8 |
0 |
250 |
0 |
0 |
0 |
0 |
-1 |
1 |
500 |
Выполняется переход от недопустимого начального решения, содержащегося в исходной симплекс-таблице, к некоторому допустимому решению. Для этого с помощью обычных процедур симплекс-метода выполняется минимизация искусственной целевой функции W (или, то же самое, максимизация функции -W). При этом переменные, включаемые в базис, выбираются по строке искусственной целевой функции. Все остальные действия выполняются точно так же, как в обычном симплекс-методе. В результате минимизации искусственная целевая функция -W должна принять нулевое значение. Все искусственные переменные при этом также становятся равными нулю (исключаются из базиса), так как искусственная целевая функция представляет собой их сумму.
В таблице в строке искусственной целевой функции максимальное по модулю (в этой строке) отрицательное значение, равное -250. Это коэффициент при переменной . Столбец переменной становится ведущим.
Для определения переменной, исключаемой из базиса, найдем симплексные отношения, т.е. отношения текущих значений базисных переменных к положительным коэффициентам ведущего столбца, соответствующим данным базисным переменным. ( Если в ведущем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается)): 1200/20=60; 3000/60=50; 1500/30=140; 500/250=2. Минимальное симплексное отношение получено в строке переменной ; значит, эта переменная исключается из базиса. Строка переменной становится ведущей. Находим ведущий элемент, он расположен на пересечении ведущей строки и ведущего столбца (в нашем случае он равен 250). Затем определяем переменные, которые будем исключать из базиса и включать в него. (Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них. То же самое относится к положительным элементам последней строки симплекс-таблицы.).
Переменную, которой соответствует ведущий столбец, включим в базис вместо переменной, которой соответствует ведущая строка; в столбце "Базис" вместо переменной, исключенной из базиса, указывается переменная, включенная в базис. Все элементы ведущей строки делятся на ведущий элемент.
Все элементы ведущего столбца (кроме ведущего элемента) заменяются нулями. Все остальные элементы таблицы (включая E-строку и столбец "Решение") пересчитываются по "правилу прямоугольника". Этот пересчет выполняется следующим образом: мысленно вычерчиваем прямоугольник, одна вершина которого совпадает с ведущим элементом, а другая - с элементом, образ которого мы ищем; остальные две вершины определяются однозначно
Тогда искомый элемент будет равен произведение ведущего и пересчитываемого элементов прямоугольника; из этого произведения вычитается произведение элементов, образующих противоположную диагональ прямоугольника; результат делится на ведущий элемент.
Таблица 4.2
|
Базис |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
X 6 |
X 7 |
X 8 |
Решение |
|
|
E |
-300 |
0 |
-450 |
0 |
0 |
0 |
-1 |
1 |
500 |
|
|
-W |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
|
X 4 |
15 |
0 |
25 |
1 |
0 |
0 |
0,08 |
-0,08 |
1160 |
|
|
X 5 |
35 |
0 |
60 |
0 |
1 |
0 |
0,24 |
-0,24 |
2880 |
|
|
X 6 |
20 |
0 |
25 |
0 |
0 |
1 |
0,12 |
-0,12 |
1440 |
|
|
X 2 |
0 |
1 |
0 |
0 |
0 |
0 |
-0,004 |
0,004 |
2 |
Решение, полученное в табл.4.2, является допустимым, в базисе нет искусственных переменных. Искусственная целевая функция равна нулю. Получено допустимое решение. Таким образом, первый этап двухэтапного метода завершен. Искусственная целевая функция и искусственные переменные исключаются из симплекс-таблицы.
Таблица 4.3
|
Базис |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
X 6 |
X 7 |
Решение |
|
|
E |
-300 |
0 |
-450 |
0 |
0 |
0 |
-1 |
500 |
|
|
X 4 |
15 |
0 |
25 |
1 |
0 |
0 |
0,08 |
1160 |
|
|
X 5 |
35 |
0 |
60 |
0 |
1 |
0 |
0,24 |
2880 |
|
|
X 6 |
20 |
0 |
25 |
0 |
0 |
1 |
0,12 |
1440 |
|
|
X 2 |
0 |
1 |
0 |
0 |
0 |
0 |
-0,004 |
2 |
Второй этап (поиск допустимого решения)
Решение, полученное по результатам первого этапа (табл.4.2), не является оптимальным: в строке целевой функции имеются отрицательные элементы. Поиск оптимального решения выполняется по обычным правилам симплекс-метода. В базис включается переменная (у нее максимальный по модулю отрицательный коэффициент в строке целевой функции). Для определения переменной, исключаемой из базиса, найдем симплексные отношения: 1160/25=46,4; 2880/60=48; 1440/25=57,6. Из базиса исключается переменная . После преобразований по правилам симплекс-метода будет получена новая симплекс-таблица (табл.4.4).
Таблица 4.4
|
Базис |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
X 6 |
X 7 |
Решение |
|
|
E |
-30 |
0 |
0 |
18 |
0 |
0 |
0,44 |
21380 |
|
|
X 3 |
0,6 |
0 |
1 |
0,04 |
0 |
0 |
0,0032 |
46,4 |
|
|
X 5 |
-1 |
0 |
0 |
-2,4 |
1 |
0 |
0,048 |
96 |
|
|
X 6 |
5 |
0 |
0 |
-1 |
0 |
1 |
0,04 |
280 |
|
|
X 2 |
0 |
1 |
0 |
0 |
0 |
0 |
-0,004 |
2 |
Так как в строке целевой функции есть отрицательный коэффициент, решение не оптимально. Продолжим пересчет таблицы. В базис включается переменная (у нее максимальный по модулю отрицательный коэффициент в строке целевой функции). Для определения переменной, исключаемой из базиса, найдем симплексные отношения: 46,4/0,6=77,3; 280/50=56; Из базиса исключается переменная . После преобразований по правилам симплекс-метода будет получена новая симплекс-таблица (табл.4.5).
Таблица 4.5
|
Базис |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
X 6 |
X 7 |
Решение |
|
|
E |
0 |
0 |
0 |
12 |
0 |
6 |
0,68 |
23060 |
|
|
X 3 |
0 |
0 |
1 |
0,16 |
0 |
-0,12 |
-0,0016 |
12,8 |
|
|
X 5 |
0 |
0 |
0 |
-2,6 |
1 |
0,2 |
0,056 |
152 |
|
|
X 1 |
1 |
0 |
0 |
-0,2 |
0 |
0,2 |
0,008 |
56 |
|
|
X 2 |
0 |
1 |
0 |
0 |
0 |
0 |
-0,004 |
2 |
Получено оптимальное решение (отсутствуют отрицательные элементы в строке целевой функции): ; ; ; . Это означает, что предприятию следует работать 56 дней по технологическому процессу ТП1, 2 дня - по технологическому процессу ТП2, 12,8 дней - по технологическому процессу ТП3. При этом количество выпущенных изделий составит 23060 штук.
Остаточная переменная означает, что для изготовления деталей будет израсходована на 152 тыс. кВт-ч меньше допустимого. Остаточные переменные означают, что для изготовления деталей будет израсходована максимально возможное количество рабочей силы и сырья соответственно (рабочей силы 1,2 млн человеко-ч и 1500 т сырья).
Избыточная переменная говорит о том, что по технологическому процессу ТП2 будет изготовлено ровно минимально необходимое количество деталей (500 штук).
5. Анализ задачи на чувствительность
Анализ решения на чувствительностьэто анализ влияния изменений в постановке задачи на оптимальное решение. Анализ моделей на чувствительность -- это процесс, реализуемый после получения оптимального решения. В рамках такого анализа выявляется чувствительность оптимального решения к определенным изменениям исходной модели. В задаче изготовления деталей может представлять интерес вопрос о том, как повлияет на оптимальное решение увеличение и уменьшение запаса ресурсов. Также потребуется анализ влияния производительности деталей технологических процессов.
5.1 Анализ на чувствительность к изменению ограничения на использование сырья
Для анализа влияния данного изменения на оптимальное решение используются коэффициенты из столбца остаточной переменной, входящей в изменившееся ограничение (используем последнюю симплекс-таблицу), в данном случае .Пусть минимально возможное количество сырья, которое можно использовать для изготовления деталей, изменится на d единиц и составляет не более (1500+d) т. Величина d может быть как положительной, так и отрицательной:
Здесь коэффициенты взяты из столбца избыточной переменной в окончательной симплекс-таблице (табл. 4.5).
Диапазон изменений ограничения, при котором состав переменных в оптимальном базисе остается прежним. Определяется из условия неотрицательности всех переменных:
Решив эту систему неравенств, получим: . Это означает, что базис оптимального решения не изменится, если ограничение, определяющее минимальный и максимальный запас сырья, будет от 1220 до 1606,67 т.
Если это ограничение не будет соблюдено, то для получения нового оптимального решения потребуется решить задачу заново. Новое оптимальное решение будет отличаться от прежнего решения не только значениями, но и составом переменных в оптимальном базисе.
5.2 Анализ на чувствительность к изменению одного из коэффициентов целевой функции
Для анализа влияния изменений коэффициента целевой функции на оптимальное решение используются коэффициенты из строки переменной, для которой изменился коэффициент целевой функции.
Изменение коэффициента целевой функции не приводит к изменениям в оптимальном решении задачи. Изменяются только значения целевой функции, а также коэффициенты Е-строки при небазисных переменных в окончательной симплекс-таблице.
Пусть коэффициент при в целевой функции равен не 300, а 300+d, т. е. изменится выпуск изделий при работе предприятия по технологическому процессу ТП1. В этом случае новые значения переменных и значение целевой функции можно рассчитать по следующим формулам:
где , , новые значения коэффициентов Eстроки при небазисных переменных , , в окончательной симплекс-таблице.
Рассчитаем диапазон изменений выпуска изделий при работе по технологическому процессу ТП1, при котором решение остается оптимальным. Он находится из условия неотрицательности всех коэффициентов Е-строки:
В результате решения системы неравенств получим диапазон: . Это означает, что базис оптимального решения не изменится, если выпуск изделий при работе по технологическому процессу ТП1 будет от 270 до 360 штук.
Выход значения d за границы этого диапазона приведет к недопустимости найденного нами оптимального решения. Необходимо будет решить задачу заново, используя симплекс-метод. Новое оптимальное решение будет отличаться от прежнего решения не только значениями, но и составом переменных в оптимальном базисе. При этом прежнее решение уже не будет оптимальным, но останется допустимым, так оно удовлетворяет ограничениям задачи.
6. Построение модифицированной аналитической модели и анализ результатов модификации
Часть имеющееся электроэнергии остается неизрасходованной (152 тыс. кВт-ч из 3 млн кВт-ч). Найдем, на какую величину необходимо увеличить запасы остальных ресурсов, чтобы использовать все ресурсы по возможности более полно. Это позволит также увеличить выпуск изделий.
Попробуем увеличить количество рабочей силы. Предположим, например, что рабочей силы стало на 20 млн. человеко-ч больше. Внесем соответствующие изменения в правую часть ограничения:
.
Остальные ограничения и целевая функция остаются прежними. Получим следующее оптимальное решение: ): ; ; ; . Как видим остаток электроэнергии снизился (со 152 тыс. кВт-ч до 100 тыс. кВт-ч). Запасы остальных ресурсов израсходованы полностью.
Варьируя величину рабочей силы, подберем такие значения, чтобы расход ресурсов был наиболее полным. Для следующей математической модели
оптимальное решение будет следующим ; ; ; . Таким образом ресурсы используются практически полностью (остается неиспользованным только 1,2 тыс кВт-ч).
Рабочий лист MS Excel находится в приложении В. Сравнительная характеристика двух планов работы предприятия (при базовом и новом варианте производства изделий) приведена в таблице 6.1.
Таблица 6.1
|
Показатели |
Базовый вариант |
Новый вариант |
|
|
Ресурсы. Сырьё (т) Электроэнергия (млн кВт-ч). Рабочая сила (млн человеко-ч). |
1500 3000 1200 |
1500 3000 1258 |
|
|
Работа по ТП, дней ТП1 ТП2 ТП3 |
56 2 12,8 |
44,4 2 22,08 |
|
|
Неиспользованные ресурсы. Сырьё (т) Электроэнергия (кВт-ч). Рабочая сила (человеко-ч). |
0 152000 0 |
0 1200 0 |
|
|
Производство деталей, ед. |
23060 |
23756 |
Из таблицы 6.1 видно, что незначительное увеличение рабочей силы позволит практически полностью использовать все ресурсы. При этом производство деталей также увеличится.
7. Примеры постановок и решений перспективных оптимизационных управленческих задач
7.1 Пример 1
Косметическая фирма выпускает три вида продукции:
Бальзам, шампунь и мыло. Для изготовления продукции используется три вида сырья: крем, настойка из трав, глицерин.
Прибыль, полученная от реализации каждого вида косметического средства продукции, указана в таблице. В таблице также указано, сколько единиц каждого сырья необходимо для изготовления каждого сорта продукции и общее кол-во единиц сырья.
Таблица 7.1
|
Виды Сырья |
Виды продукции |
|||
|
Бальзам |
Шампунь |
Мыло |
||
|
Крем |
2 |
1 |
1 |
|
|
Настойка из трав |
3 |
8 |
2 |
|
|
Глицерин |
0 |
0 |
1 |
|
|
Прибыль от реализации продукции |
3 |
2 |
3 |
Известно, что крема может быть использовано не более 2 тонн, Настойки из трав должно содержаться не менее 8 тонн, а глицерина не менее 1 тонны. Определить какую продукцию и в каком количестве следует производить для получения максимальной прибыли.
Решение.
- количество выпускаемого бальзама;
- количество выпускаемого шампуня;
- количество выпускаемого мыла.
Составим математическую модель задачи. Введем ограничения.
Ограничение на использование крема:
Ограничение на использование настойки из трав:
Ограничение на использование глицерина:
Все переменные в данной задаче неотрицательны:
, , 0
Составим целевую функцию:
- это прибыль предприятия, которую необходимо максимизировать.
Таким образом, математическая модель имеет вид:
, , 0
.
Решив задачу симплекс-методом, получим: , , , . Это означает, что при производстве 2/3 тонн шампуня и 4/3 тонн мыла прибыль фирмы будет максимальной и составит 16/3 ден. ед. Избыточная переменная означает, что при производстве будет использовано на 0,33 тонн больше минимально возможного количества глицерина. Остаточная переменная означает, что крема будет использовано максимально возможное количество ( ровно 2 тонны). А избыточная переменная показывает, что настойки из трав будет использовано ровно 8 тонн. Протокол решения находится в приложении Г.
7.2 Пример 2
Мебельная фабрика изготавливает диваны двух видов - раскладные и угловые. Для производства диванов используют два вида сырья - дерево и ДСП. Максимально возможные запасы сырья в сутки составляют 900 и 730 единиц соответственно. Расход сырья на один раскладной диван и один угловой диван приведен в таблице 8.7.
Таблица 7.2
|
Сырье |
Расход сырья на 1 диван |
Запас сырья, ед. |
||
|
угловой |
раскладной |
|||
|
Дерево |
7 |
5 |
900 |
|
|
ДСП |
9 |
13 |
730 |
аналитический оптимизация симплекс управленческий
Кроме того, известно, что минимальный спрос на раскладные диваны равен 20 ед. в сутки.
Прибыль от продажи одного дивана равна: 6 д. е. - для угловых диванов и 4 д.е. для раскладных.
Какое количество диванов каждого вида должна производить фабрика, чтобы прибыль от продажи диванов был максимальным?
Решение:
- количество угловых диванов;
- количество раскладных диванов;
Составим математическую модель задачи. Введем ограничения.
Ограничение на использование дерева при производстве диванов:
Ограничение на использование ДСП при производстве диванов:
Ограничение на спрос раскладных диванов:
Все переменные в данной задаче неотрицательны и целочисленные:
, ?0, целые.
Составим целевую функцию:
- это прибыль фабрики, которую необходимо максимизировать.
Таким образом, математическая модель имеет вид:
, ?0, целые
Решив задачу симплекс-методом, получим: , , .Получено оптимальное решение (отсутствуют отрицательные элементы в строке целевой функции). Однако это оптимальное решение без учета условия целочисленности. Решим данную задачу с учетом этого условия.
Используем метод ветвей и границ. Выбираем переменную , принявшую дробное значение. Вместо исходной задачи составляем две новые. В одну из них вводится ограничение (задача 2), а во вторую вводится ограничение (задача 3).
Смысл этих ограничений:
- Эти ограничения исключают из области допустимых решений найденное оптимальное, но дробное решение.
- Эти ограничения не исключают из области допустимых решений ни одного целочисленного значения.
Задачи 2 и 3 включаются в список решаемых задач.
Получено оптимальное целочисленное решение (отсутствуют отрицательные элементы в строке целевой функции): , ; ; ; . Это означает, что при производстве 52 угловых диванов и 20 раскладных максимальная прибыль составит 392 ден.ед.
Остаточная переменная означает, что при производстве диванов останутся неиспользованными 436 т дерева. Остаточная переменная означает, что при производстве диванов останутся неиспользованными 2 т ДСП. Избыточная переменная означает, что будет выпущено ровно 20 раскладных диванов (минимально возможное количество).
Заключение
В результате проведения всех вычислительных операций мы определили оптимальное решение, производство по технологическим процессам оказалось следующим: 56 дней по ТП1, 2 дня по ТП2 и 12,8 дней по ТП3. При этом рабочая сила и сырье будут использованы полностью. 152 тыс. кВт/ч будут не израсходованы. Выпуск изделий составит 23060 штук.
В рассматриваемой задаче имеются следующие недостатки: значительная часть электроэнергии осталась неизрасходованной. Это можно устранить следующим способом: увеличим запас рабочей силы на 58 млн. человеко-ч/день (исходный запас составлял 1200 млн. человеко-ч/день). Это небольшое увеличение запаса одного из ресурсов позволит практически полностью израсходовать все ресурсы. При этом выпуск изделий также увеличится и составит 23756 штук.
Список литературы
1. Дегтярев Ю.И. Исследование операций. - М.: Высшая школа, 1979. - 320 с.
2. Смородинский С.С. Методы и алгоритмы для решения оптимизационных задач линейного программирования: Учебно-методическое пособие по курсу "Системный анализ и исследование операций" для студентов специальности "Автоматизированные системы обработки информации и управления", Ч. 1. / С.С. Смородинский, Н.В. Батин - Мн.: БГУИР, 1995. - 91 с.
3. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного программирования: Учебно-методическое пособие по курсу "Системный анализ и исследование операций" для студентов специальности "Автоматизированные системы обработки информации". - В 2-х частях. - Ч. 2. - Мн.: БГУИР, 1996. - 82 с.
4. Смородинский С.С., Батин Н.В. Оптимизация решений на основе методов и моделей математического программирования: Учебное пособие по курсу "Системный анализ и исследование операций" - Мн.: БГУИР, 2003. - 136 с.: ил.
5. Таха Х. Введение в исследование операций. М., С.-П., Киев: "Вильямс", 2001. - 910 с.
Приложение А
(справочное)
Протокол решения задачи оптимизации с использованием пакета SIMPLEX
Рисунок А.1 - Первая симплекс-таблица
Рисунок А.2 - Первое допустимое решение
Рисунок А.3 - Третья симплекс-таблица
Рисунок А.4 - Оптимальное решение
Рисунок А.4 - Результат
Приложение Б
(справочное)
Рабочий лист MS EXCEL с результатами оптимизации на основе базовой аналитической модели
Рисунок Б.1 - Рабочий лист Excel
Рисунок Б.2 - Надстройка "Поиск решения"
Приложение В
Рабочий лист MS EXCEL с результатами оптимизации на основе модифицированной аналитической модели
Рисунок В.1 - Рабочий лист Excel
Рисунок В.2 - Надстройка "Поиск решения"
Приложение Г
Протокол решения перспективной оптимизационной управленческой задачи с использованием пакета SIMPLEX-M
Задача 1.
Рисунок Г.1 - Оптимальное решение
Рабочий лист MS EXCEL с результатами оптимизации на основе перспективной оптимизационной управленческой задачи
Рисунок Г.2 - Рабочий лист Excel
Рисунок Г.3 - Надстройка "Поиск решения"
Протокол решения перспективной оптимизационной управленческой задачи с использованием пакета SIMPLEX-M
Задача 2.
Рисунок Г.4 - Оптимальное решение
Рабочий лист MS EXCEL с результатами оптимизации на основе перспективной оптимизационной управленческой задачи
Рисунок Г.5 - Рабочий лист Excel
Рисунок Г.6 - Надстройка "Поиск решения"
Размещено на Allbest.ru
Подобные документы
Задачи операционного исследования. Построение базовой аналитической модели. Описание вычислительной процедуры. Решение задачи оптимизации на основе технологии симплекс-метода. Анализ результатов базовой аналитической модели и предложения по модификации.
курсовая работа [1,5 M], добавлен 12.12.2009Постановка, анализ, графическое решение задач линейной оптимизации, симплекс-метод, двойственность в линейной оптимизации. Постановка транспортной задачи, свойства и нахождение опорного решения. Условная оптимизация при ограничениях–равенствах.
методичка [2,5 M], добавлен 11.07.2010Количественное обоснование управленческих решений по улучшению состояния экономических процессов методом математических моделей. Анализ оптимального решения задачи линейного программирования на чувствительность. Понятие многопараметрической оптимизации.
курсовая работа [4,2 M], добавлен 20.04.2015Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.
курсовая работа [458,6 K], добавлен 10.12.2013Решение задачи линейного программирования графическим способом. Построение математической модели задачи с использованием симплекс-таблиц, её экономическая интерпретация. Поиск оптимального плана перевозки изделий, при котором расходы будут наименьшими.
задача [579,8 K], добавлен 11.07.2010Виды задач линейного программирования и формулировка задачи. Сущность оптимизации как раздела математики и характеристика основных методов решения задач. Понятие симплекс-метода, реальные прикладные задачи. Алгоритм и этапы решения транспортной задачи.
курсовая работа [268,0 K], добавлен 17.02.2010Составление математической модели, целевой функции, построение системы ограничений и симплекс-таблиц для решения задач линейного программирования. Решение транспортной задачи: определение опорного и оптимального плана, проверка методом потенциалов.
курсовая работа [54,1 K], добавлен 05.03.2010Формулирование экономико-математической модели задачи в виде основной задачи линейного программирования. Построение многогранника решений, поиск оптимальной производственной программы путем перебора его вершин. Решение задачи с помощью симплекс-таблиц.
контрольная работа [187,0 K], добавлен 23.05.2010Исследование задачи оптимизации ресурсов при планировании товарооборота торгового предприятия в общем виде. Формирование математической модели задачи. Решение симплекс-методом. Свободные члены системы ограничений и определение главных требований к ним.
курсовая работа [68,6 K], добавлен 21.06.2011Построение экономической модели по оптимизации прибыли производства. Разработка математической модели задачи по оптимизации производственного плана и её решение методами линейного программирования. Определение опорного и оптимального плана производства.
дипломная работа [311,3 K], добавлен 17.01.2014
