Линейная оптимизация в MS Excel

Размещено на http://www.allbest.ru/

1

Содержание

• Введение 2
• 1. Линейная оптимизация 4
• 2. Решение задач линейной оптимизации средствами пакета MS Excel 8
• 3. Пример решения задачи 12
• Заключение 18
• Список литературы 19
• Введение
• Характерной чертой современности является стремительный научно-технический прогресс, что требует от менеджеров и бизнесменов значительного повышения ответственности за качество принятия решений. Это основная причина, которая обусловливает необходимость научного принятия управленческих решений. Одним из направлений научно-технического прогресса стало математическое программирование, которое тесно связанное с практическими проблемами оптимального распределения ресурсов в различных отраслях производства и сферы услуг.
• Поскольку различные аспекты оптимизации занимают очень важное место в бизнесе и деятельности современных организаций и предприятий, знание методов линейного программирования может помочь на практике тем людям, которые сталкиваются с такими задачами в своей повседневной роботе (менеджера, экономисты, финансисты, фермеры) или тем, кто просто интересуются этими вопросами.
• Проблемы оптимизации присутствуют в самых различных процессах производства:
• поставка сырья;
• оптимальный выпуск продукции;
• оптимальное управление запасами ;
• оптимальное распределение ресурсов;
• планирования инвестиций;
• оптимальный рацион (смесь, сплав);
• оптимальная замена оборудования и т. д
• Решение задачи оптимизации состоит в поиске оптимального плана с использованием математических моделей и вычислительных методов, которые реализуются с помощью компьютеров и специальных программ-оптимизаторов.
• Традиционный способ изучения экономико-математических методов заключается не только в определении их назначения и сути, но и в освоении техники реализации, причем, чтобы сделать доступной «ручную» реализацию, объем обрабатываемых данных приходится максимально сокращать, что, с одной стороны, часто удаляет построенную модель от реальной жизни, а с другой - снижает эффективность применения изучаемых методов.
• Цель контрольной работы изучить и научиться пользоваться MS Excel, а именно, такими компонентами, как Вставка формул, Подбор параметра, Поиск решения. Все эти функции MS Excel облегчают задачу математикам, бухгалтерам и специалистам в различных областях.
• 1. Линейная оптимизация
• Существует множество задач, решение которых может быть существенно облегченно с помощью инструмента Поиск решений в MS Excel. Но для этого следует начать с организации рабочего листа в соответствии с пригодной для поиска решений моделью, для чего нужно хорошо понимать взаимосвязи между переменными и формулами. Хотя постановка задачи обычно представляет основную сложность, время и усилия, затраченные на подготовку модели, вполне оправданы, поскольку полученные результаты могут уберечь от излишней траты ресурсов, при неправильном планирование, помогут увеличить прибыль за счет оптимального управление финансами или выявить наилучшее соотношение объемов производства, запасов и наименований продукции.
• За своей сущностью задача оптимизации - это математическая модель определенного процесса производства продукции, его распределение, хранение, переработки, транспортирования, покупки или продажи, выполнение комплекса сервисных услуг и т.д. Это обычная математическая задача типа: Дано/Найти/При условии, но которая имеет множество возможных решений. Таким образом, задача оптимизации - задача выбора из множества возможных вариантов наилучшего, оптимального.
• Решение такой задачи называют планом или программой, например, говорят - план производства или программа реконструкции. Другими словами это те неизвестные которые нам надо найти, например, количество продукции которое даст максимальную прибыль. Задача оптимизации - поиск экстремума, то есть, максимального или минимального значения определенной функции, которую называют целевой функцией, например, это может быть функция прибыли - выручка минус затраты. Так как и всё в мире ограничено (время, деньги, природные и человеческие ресурсы), в задачах оптимизации всегда есть определенные ограничения, например, количество метала, рабочих и станков на предприятии по изготовлению деталей.
• Каждая задача оптимизации обязательно должна иметь три компоненты:
• неизвестные (что ищем, то есть, план);
• ограничение на неизвестные (область поиска);
• целевая функция (цель, для которой ищем экстремум).
• Линейное программирование - наиболее развитый раздел математического программирования, вычислительные средства которого позволяют находить глобальный оптимум линейной задачи оптимизации.
• На счастье, большинство экономических управленческих задач хорошо описываются линейными моделями - именно этим обстоятельством объясняется успех практического использования линейных моделей для решения больших по размерам задач планирования и управления на уровне отдельных организаций, предприятий и даже отраслей производства.
• Линейные модели используют такое прекрасное свойство линейных задач оптимизации, как линейные уравнения или неравенства из неизвестных и целевую функцию. Это означает, что область допустимых решений - выпуклой многоугольник, одна из вершин которого и есть оптимальное решение.
• Именно этот эффективный математический результат лежит в основе симплекс-метода - для поиска оптимума нужно в определенном порядке пересмотреть небольшое количество вершин, используя простой и эффективный алгоритм последовательного улучшения значения целевой функции. Мощные и эффективные средства линейного программирования определенным образом используются и в целочисленном программировании для решения более сложных задач оптимизации.[1]
• Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:
• - количество продукции - расход сырья
• - количество продукции - качество продукции
• Выбор компромиссного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи.
• При постановке задачи оптимизации необходимо:
• 1. Наличие объекта оптимизации и цели оптимизации. При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого.
• 2. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта.
• 3. Возможность количественной оценки оптимизируемой величины, поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий.
• 4. Учет ограничений.
• Таким образом, задача оптимизации сводится к нахождению экстремума целевой функции.
• В зависимости от своей постановки, любая из задач оптимизации может решаться различными методами, и наоборот - любой метод может применяться для решения многих задач. Методы оптимизации могут быть скалярными (оптимизация проводится по одному критерию), векторными (оптимизация проводится по многим критериям), поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.), вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т.д.), теоретико-вероятностными, теоретико-игровыми и др. Подвергаться оптимизации могут задачи как с ограничениями, так и без них.
• Задача линейного программирования состоит в следующем: максимизировать (минимизировать) линейную функцию
• , где
• при ограничениях
• причем все
• .
• Если число переменных системы ограничений и целевой функции в математической модели задачи равно 2, то её можно решить графически.
• Нахождение решения задачи линейного программирования геометрическим методом включает следующие этапы:
• 1. Строят прямые, уравнения, которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.
• 2. Находят полуплоскости, определяемые каждым из ограничений задачи.
• 3. Находят многоугольник решений.
• 4. Строят вектор.
• 5. Строят прямую.
• 6. Строят параллельные прямые в направлении градиента или антиградиента, в результате чего находят точку, в которой функция принимает максимальное или минимальное значение, либо устанавливают неограниченность сверху (снизу) функции на допустимом множестве.
• 7. Определяют координаты точки максимума (минимума) функции и вычисляют значение целевой функции в этой точке.[4,c.188}

Рис.1. Пункт меню Поиск решения

Рис. 2. Включение надстройки Поиск решения

Режим Поиск решения (рис. 4.3) позволяет, задавая некоторую ячейку в виде целевой при условии обеспечения зависимости результата вычислений в ней от значений некоторых изменяемых ячеек, с учетом заданных ограничений получить или максимальное, или минимальное, или заданное значение целевой ячейки.

Рис. 3. Режим Поиск решения

В качестве параметров режима (рис. 4) задаются ограничение по времени поиска решения в секундах (Максимальное время) (максимально 32767), количеству итераций (Предельное число итераций), точности соответствия результата заданному значению (Относительная погрешность), допустимого отклонения экстремума от оптимального значения при использовании режима целочисленной математики (Допустимое отклонение), а также условие прекращения поиска экстремума (Сходимость), задающее величину относительного приращения экстремума за последние пять итераций.

Рис. 4. Параметры режима Поиск решения

Кроме этого, в виде флажков могут задаваться отдельные режимы работы, например Линейная модель, определяющая класс методов решения задачи. При установке параметра Линейная модель Excel ищет экстремум симплекс-методом. Если флажок Линейная модель выключен, решение задачи ведется методом Ньютона или градиентным с использованием прямых или центральных конечных разностей на основе линейной или квадратичной оценки уменьшения приращения экстремума в зависимости от установленных флажков.

Флажок Неотрицательные значения накладывает дополнительное ограничение на значения переменных задачи. Другие флажки (например, Линейная, Квадратичная) определяют способ экстраполяции данных, метод вычисления конечных разностей (Прямые, Центральные), и метод поиска экстремума (Ньютона, Сопряженных градиентов).

Флажок Значения не отрицательны позволяет задать диапазон значения аргумента. Его установка эквивалентна введению ограничения xi ?0. Режим Автоматическое масштабирование позволяет перейти к отображению данных в относительных единицах, а при установке флажка Показывать результаты итераций включается пошаговый режим. Вариант настройки параметров может быть сохранен.

Решение задачи линейного программирования средствами табличного процессора Excel осуществляется в режиме Сервис/Поиск решения. Для работы в этом режиме требуется предварительно разместить в рабочем листе коэффициенты cj целевой функции (коэффициенты значимости), матрицу коэффициентов aij, ограничения в виде количества имеющихся ресурсов bi и выделить ячейки для расчета значения целевой функции E и значений вектора управления X = (x1, x2,…, xn). Решением задачи является рассчитываемый надстройкой Поиск решения набор переменных X = (x1, x2 ,..., xn ) , обеспечивающий максимальное (минимальное, заданное) значение целевой функции E(x1, x2 ,..., xn ) .

Следующим этапом при подготовке задачи к решению является программирование математических выражений, связывающих между собой исходные числовые данные и вычисляемые выражения. Электронные таблицы Excel позволяют записывать в выбранную ячейку не только числа, но и математические выражения, составленные по общим правилам языков программирования с использованием символа присваивания =, знаков операций (+,-,*,/) и встроенных функций. В качестве операндов в таких выражениях могут использоваться константы или имена ячеек Excel. [3,c.113]

3. Пример решения задачи

Задача .Отделы кредитования коммерческого банка К₁, К_2, К_3, К₄ , выделяют кредиты фирмам Ф₁, Ф₂, Ф₃ , Ф₄ . Дана матрица Р, в которой на позиции (i,j) указана процентная ставка, под которую i-тый отдел может выделить деньги j-й фирме. Даны также векторы А и В; i-тая координата вектора А равна общей сумме кредита, который может выделить отдел Кi, j-я координата вектора В равна потребности в кредитах фирмы Фj. Найти оптимальное распределение банковских кредитов между фирмами, максимизирующее общую прибыль банка при дополнительном условии, что спрос фирм Ф1 и Ф3 должен выполнен полностью.

Представим данные в табличной форме:

Так как сумма потребностей фирм превышают суммарную возможность банков по предоставлению кредита введем фиктивный банк с нулевыми процентными ставками и возможностью предоставить кредит на сумму 514-465 =49.

Составим математическую модель задачи.

Обозначим х_i,j - сумма кредита i-го банка j-той фирме, тогда целевая функция примет вид:

8*х11+13*х12 + 9*х13+6*х14 + 2*х21 + 16*х22 + 8*х23 + 5*х24 + 7*х31 + 8*х32 + 14*х33 + 9*х34 + 11*х41 + 4*х42 + 8*х43 + 3*х44> max

При следующих ограничениях:

х11+х12+х13+х14=170

х21+х22+х23+х24=124

х31+х32+х33+х34=96

х41+х42+х43+х44=75

х51+х52+х53+х54=49

х11+х21+х31+х41=184

х12+х22+х32+х42+х52<=99

х13+х23+х33+х43=156

х14+х24+х34+х44+х54<=75

х_i,j > 0.

Задачу решаем в MS Excel. Предварительно заполним данными матрицы кредитов и процентов. Введем формулы расчета ограничений в ячейки В12:Е12 по фирмам и F5:F9 по кредитам.

линейная оптимизация задача формула

Воспользуемся надстройкой «Поиск решения» для решения задачи:

Введем адрес ячейки для целевой функции Н12, выберем максимальное значение. Далее в окне ограничения введем все ограничения из условия задачи:

Введем дополнительные ограничения:

Установим диапазон ячеек для изменения:

Получаем результат:

Таким образом, если не учитывать фиктивный банк К5 имеем решение задачи:

Для получения максимальной выгоды:

Банк К1 должен дать кредит фирмам- Ф1 -109, Ф3- 48, Ф4 - 13;

Банк К2 кредит фирмам - Ф2 -99, Ф3 -12, Ф4 -13;

Банк К3 кредит банкам - Ф3 - 96;

Банк К4 кредит банкам - Ф1 - 75.

Тогда общий доход составит - 5296.

Невыполненным останется спрос фирмы Ф4 - 26 при спросе - 75.

Если не учитывать фиктивный банк К5, решение будет выглядеть следующим образом:

Получаем решение ЦФ=3978

Заключение

Традиционный способ изучения экономико-математических методов заключается не только в определении их назначения и сути, но и в освоении техники реализации, причем, чтобы сделать доступной «ручную» реализацию, объем обрабатываемых данных приходится максимально сокращать, что, с одной стороны, часто удаляет построенную модель от реальной жизни, а с другой - снижает эффективность применения изучаемых методов.

Использование компьютерных технологий освобождает от рутинной вычислительной работы по реализации математических методов и позволяет сконцентрировать внимание не на алгоритме вычисления, а непосредственно на анализе результатов моделирования, что заметно повышает «коэффициент полезного действия» затраченного времени. [1]

Список литературы