Решение задач линейного программирования

В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся в нахождении в заданной области точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это так называемые задачи математического программирования, возникающие в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства. Изучение этого круга задач и методов их решения привело к созданию новой научной дисциплины, получившей позднее название линейного программирования. В конце 40-х годов американским математиком Дж. Данцигом был разработан эффективный метод решения данного класса задач — симплекс-метод. К задачам, решаемых этим методом в рамках математического программирования относятся такие типичные экономические задачи как «Определение наилучшего состава смеси», «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», «Задача о выборе производственной программы», «Транспортная задача», «Задача размещения», «Модель Неймана расширяющейся экономики» и другие. Решение таких задач дает большие выгоды как народному хозяйству в целом, так и отдельным его отраслям.

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

линейный программирование целевой функция.

1. Теоретическое положение

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробнолинейное программирование.

Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.

Математическая формулиовка задачи линейного программирования Нужно определить максимум линейной целевой функции (линейной формы).

при условиях.

Иногда на xi также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя её во всех остальных равенствах и неравенствах (а также в функции f).

Такую задачу называют «основной» или «стандартной» в линейном программировании. Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования (ЛП) является симплекс метод.

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

Для решения задач анализа чувствительности ограничения линейной модели классифицируются следующим образом. Связывающие ограничения проходят через оптимальную точку. Несвязывающие ограничения не проходят через оптимальную точку. Аналогично ресурс, представляемый связывающим ограничением, называют дефицитным, а ресурс, представляемый несвязывающим ограничением — недефицитным. Ограничение называют избыточным в том случае, если его исключение не влияет на ОДР и, следовательно, на оптимальное решение. Выделяют следующие три задачи анализа на чувствительность.

1. Анализ сокращения или увеличения ресурсов:

на сколько можно увеличить (ограничения типа) запас дефицитного ресурса для улучшения оптимального значения ЦФ?

на сколько можно уменьшить (ограничения типа) запас недефицитного ресурса при сохранении оптимального значения ЦФ?

2. Увеличение (ограничения типа) запаса какого из ресурсов наиболее выгодно?

3. Анализ изменения коэффициентов ЦФ.

2. Практическая часть

Банк Thriften, предоставляющий полный набор банковских услуг, находится в процессе формирования портфеля кредитов объемом 12 миллионов долларов. В таблице 1 представлены возможные типы банковских кредитов.

Безнадежные долги считаются невозвратимыми, поэтому они должны вычитаться из возможного дохода.

Конкурентная борьба с другими финансовыми институтами вынуждает банк не менее 40% капитала помещать в сельскохозяйственные и коммерческие кредиты. Для содействия строительной индустрии своего региона банк планирует вложить в кредиты на покупку жилья не менее 50% от общей суммы кредитов физических лиц, на покупку автомобилей и жилья. Банк также поддерживает государственную политику, указывающую, что отношение безнадежных долгов ко всей сумме кредитов не должно превышать 0.04.

Математическая модель.

Переменные для создаваемой модели можно определить следующим образом:

х1 — кредиты физическим лицам, х2 — кредиты на покупку автомобилей, х3 — кредиты на покупку жилья, х4 —- сельскохозяйственные кредиты, х5 — коммерческие кредиты.

Банк Thriftem, естественно, желает максимизировать чистую прибыль, т. е. разность между доходом от инвестируемых сумм и суммой невозвращенных кредитов. Поскольку безнадежные долги считаются невозвратимыми, они вычитаются как из инвестируемых сумм, так и общей прибыли. Исходя из этих соображений, целевую функцию можно записать следующим образом.

Максимизировать.

После приведения подобных членов получаем.

Максимизировать.

Задача имеет пять ограничений.

1. Ограничение общей суммы кредитов.

2. Ограничение на сельскохозяйственные и коммерческие кредиты.

Или.

3. Ограничение кредитов на покупку жилья.

4. Ограничение на невозвращенные кредиты.

Решение в Excel.

1. Подготовим форму для ввода условий задачи (рис. 1.1). В задаче оптимальные значения вектора X = (х1, х2×3, х4,) будут помещены в ячейках А2: Е2, оптимальное значение целевой функции — в ячейке G2.(таблица в режиме чисел).

Рис. 1.1.

Введем исходные данные в созданную форму. Получим результат, показанный на рис. 1.2.(таблица в режиме формул).

Рис. 1.2.

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

Вносим целевую функцию и ограничения. Рис. 1.3.

Рис 1.3.

После того, как мы ввели все необходимые функции, ограничения и обозначения, нажимаем кнопку «выполнить» и далее программа рассчитает результат.

Получаем следующее решение на рис. 1.4.

Рис1.4.

Ввод параметров для решения ЗЛП (рис. 1.5).

• * Открыть окно «Параметры поиска решения».
• * Установить флажок Линейная модель, что обеспечивает применение симплекс-метода.
• * Установить флажок Неотрицательные значения.
• * ОК.

оптимальное решение сформулированной задачи линейного программирования показаны на оно рекомендует использовать кредиты на покупку жилья.