Применение графического метода линейного программирования к экстремальным задачам экономики

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

ВВЕДЕНИЕ

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

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

Таким образом, цель курсовой работы применение графического метода линейного программирования к экстремальным задачам экономики.

Для достижения поставленной цели решаются задачи линейного программирования графическим методом.

Графический метод существенно нагляднее и обычно проще для понимания и решения (хотя занимает много времени, так как требует тщательного построения чертежа). Также этот метод позволяет практически одновременно найти решение на минимум и максимум, тогда как симплекс-методом придется делать "два подхода".

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

1 Решение задач линейного программирования: графический метод

1.1 Понятие линейного программирования

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

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

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

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

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

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

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

В экономических науках, в том числе и в таких как землеустройство, кадастр, для исследований влияния множества факторов на какой-либо процесс используются экономико-математические модели.

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

Экономико-математическая модель - это концентрированное выражение существенных взаимосвязей и закономерностей процесса в математической форме.

Математическая модель представляет собой уравнение или систему уравнений и неравенств, описывающую взаимосвязи, происходящие в оригинале. Запись процессов через систему ограничений с использованием буквенных символов имеют следующий вид: ? a_ij x_ij <=> B_i

Решение системы неравенств и уравнений имеет цель - найти наилучшие значения параметров системы, то есть цель моделирования - поиск наилучших решений. Математически это означает решение задач на экстремум (max, min.) функции цели.

Функция цели имеет вид: F=?c_jx_j>max (min)

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

Если ограничения (система уравнений и неравенств) и целевая функция представлены переменными (Х₁, Х₂,…Хn) в первой степени, т.е. линейны, возникает задача линейного программирования. Если имеет место хотя бы одно нелинейное выражение, то задача относится к нелинейному программированию.

Задачи линейного программирования решаются с применением алгоритмов симплексного и распределительного методов.

Использование экономико-математических моделей возможно при условиях:

- ограниченности ресурсов;

- неоднозначности (многовариантности) получаемых решений;

- наличия единой целевой функции.

Как правило, землеустроительные и кадастровые задачи имеют многовариантный, альтернативный характер. Вопрос состоит в том, как из множества допустимых вариантов выбрать оптимальный по заданному критерию.

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

1.2 Составные части общей модели линейного программирования

Все модели линейного программирования имеют стандартные составные части, к которым относятся:

- совокупность основных переменных, характеризующих моделируемый объект. В землеустройстве это чаще всего размеры землевладений и землепользовании, площади посевов, объемы производства продукции, затраты ресурсов (материальных, трудовых, финансовых);

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

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

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

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

Допустимым решением или планом задачи линейного программирования называют любой набор неотрицательных переменных, который удовлетворяет всем поставленным в ней ограничениям, а оптимальным решением (планом) -- допустимое решение, приводящее к максимуму значение целевой функции (или минимуму, если задача решается на минимум).

Если в задаче имеется m уравнений и n неизвестных, причем n>m, базисным называется такое допустимое решение, в котором число положительных (не равных нулю) переменных не превосходит числа ограничений. Иначе говоря, базисным будет такое решение, при котором не менее n -- m неизвестных равны нулю. Ненулевые переменные в этом решении называются базисными, а все остальные--небазисными.

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

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

- оптимизация перераспределения земель в схеме землеустройства района;

- обоснование размещения, специализации и концентрации сельскохозяйственного производства в административном районе на основе данных экономической оценки земель;

- установление размеров и структуры землевладений и землепользовании сельскохозяйственных и несельскохозяйственных предприятий при межхозяйственном землеустройстве;

- формирование сырьевых зон промышленных предприятий по переработке сельскохозяйственной продукции;

- противоэрозионная организация склоновых земель на основе моделирования условий и факторов водной эрозии почв;

- оптимизация размеров и размещения производственных подразделений и хозяйственных центров в проектах внутрихозяйственного землеустройства;

- обоснование сельскохозяйственного освоения, мелиорации и трансформации земельных угодий в рабочих проектах, связанных с использованием и охраной земли;

- организация системы севооборотов в сельскохозяйственных предприятиях;

- устройство территории многолетних насаждений (садов, ягодников, виноградников), сенокосов и пастбищ;

- оптимизация показателей агроэкономического обоснования проектов землеустройства.

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

1.3 Схема решения задач линейного программирования графическим методом

1.4 Пример решения задачи линейного программирования с помощью графического метода

Графический метод основан на геометрической интерпретации задачи линейного программирования.

1. Графически могут решаться:

- задачи, заданные в стандартной форме, содержащие не более двух переменных;

- задачи, заданные в канонической форме с числом свободных переменных (r - ранг матрицы системы ограничений);

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

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

3. Решение задачи первого типа выполняется в два этапа: построение области допустимых решений и нахождение в этой области оптимального решения.

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

I - пустая область;

II - выпуклый многоугольник;

III - неограниченная выпуклая многоугольная область.

Условие задачи.

Предприятие выпускает два вида продукции: Изделие 1 и Изделие 2. На изготовление единицы Изделия 1 требуется затратить 2 кг сырья первого типа, 3 кг сырья второго типа, 5 кг сырья третьего типа. На изготовление единицы Изделия 2 требуется затратить 5 кг первого типа, 4 кг сырья второго типа, 3 кг сырья третьего типа. Производство обеспечено сырьем каждого типа в количестве 432 кг, 424 кг, 582 кг соответственно. Рыночная цена единицы Изделия 1 составляет 34 тыс. руб., а единицы Изделия 2 - 50 тыс. руб.

Требуется:

- построить математическую модель задачи;

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

Решение задачи. Построение модели.

Через x₁ и x₂ обозначим количество выпускаемых изделий 1-го и 2-го типа.

Тогда ограничения на ресурсы:

Кроме того, по смыслу задачи

Целевая функция экономико-математической модели, выражающая получаемую от реализации выручку:

Получаем следующую экономико-математическую модель:

Построение области допустимых решений

Решим полученную задачу линейного программирования графическим способом:

Для построения области допустимых решений строим в системе координат соответствующие данным ограничениям-неравенствам граничные прямые:

Найдем точки, через которые проходят прямые:

Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее.

Для определения полуплоскости возьмём любую точку, например O(0;0), не принадлежащую прямой (1), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:

Области решений соответствующего 1-го неравенства соответствует левая полуплоскость.

Возьмём любую точку, например O(0;0), не принадлежащую прямой (2), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:

Области решений соответствующего 2-го неравенства соответствует левая полуплоскость.

Возьмём любую точку, например O(0;0), не принадлежащую прямой (3), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:

Области решений соответствующего 2-го неравенства соответствует левая полуплоскость.

Областью допустимых решений является фигура ABCDE.

Нахождение решения задачи ЛП.

Строим вектор , координаты которого пропорциональны коэффициентам целевой функции. Здесь - коэффициент пропорциональности.

Перпендикулярно к построенному вектору проводим линию уровня f = 0.

Перемещаем линию уровня f = 0 в направлении вектора так, чтобы она касалась области допустимых решений в крайней точке. Решением на максимум является точка A, координаты которой находим как точку пересечения прямых (2) и (1).

Ответ

Таким образом необходимо выпускать 56 изделий 1-го вида и 64 изделия 2-го вида. При этом выручка от реализации изделий будет максимальна и составит 5104 ден.ед.

2. Расчётная часть

Хлебозавод производит два типа тортов «БИС» и «КВИТ». Для производства 1 т «БИС» требуется 0,3 ч работы оборудования, а для «КВИТ» - 0,5 ч. Расход специального ингредиента на них составляет 0,4 и 0,1 т на 1 т соответственно. Ежедневно в распоряжении завода 12 т специального ингредиента и 15 ч работы оборудования. Доход от продажи 1 т торта «БИС» составляет 20 тыс. руб., а «КВИТ» - 31 тыс. руб. Определите ежедневный план производства тортов каждого вида, обеспечивающий максимальный доход от продажи.

Для решения этой задачи с помощью табличного процессора Exel необходимы следующие действия.

1. Создать в Excel таблицу вида (рис.1). Вводим в ячейку B4 целевую функцию.

Рисунок 1 - Построение таблицы

2. Также к исходным данным в таблицу следует добавить ограничения в ячейку A7 и ячейку A8 в соответствии с условием задачи (см. рисунок 2 и рисунок 3).

Рисунок 2 - Ввод 1-ого ограничения

Рисунок 3 - Ввод 2-ого ограничения

3. После создания таблицы с исходными данными установить курсив на ячейку целевой функции (В4) и запустить инструмент «поиск решения» (office -параметры Excel - надстройки - в раскрывшемся списке Управление - надстройки Excel - Перейти - установить флажок «Поиск решения»)

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

Рисунок 4 - Заполнение поиска решений

5. После занесения данных нажать кнопку «Найти решение» (рис. 5).

Рисунок 5 - Результат решения задачи

Если всё сделано правильно, Excel сообщит о том, что решение найдено и удовлетворяет ограничениям. В результате решения данной задачи получилось, что ежедневный план производства, обеспечивающий максимальный доход от продажи: «БИС» - 26 тортов, «КВИТ» - 14 тортов.

ЗАКЛЮЧЕНИЕ

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

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Волков, С. Н. Экономико-математические методы и модели в землеустройстве - М.: Колос, 2007. - 696 с.

2. Выгодчикова И.Ю. Введение в линейное программирование: учебное пособие.-Саратов: Издательский центр «Наука», 2014.-47с.

3. Елисеева И.И., Юзбалиев М.М. «Общая теория статистики» - 2001. -480 с.

4. Желясков А.Л., Методы линейного программирования при выполнении земельно-кадастровых работ: учебно-методическое пособие по дисциплине «Экономико-математические методы и моделирование» /А. Л. Желясков, Н.П. Шалдунова, О.А. Шестакова; М-во с. - х. РФ, ФГБОУ ВПО «Пермская ГСХА», 2013. - 68с.

5. Сагитов Р. В., Шершнев В.Г. Линейная алгебра. Часть II. Линейное программирование, динамическое программирование и теория игр: Учебно-методическое пособие. - М.: Издательство «Менеджер», 2007. - 192 с.

6. Соловицкий А.Н. «Экономико-математические методы и моделирование» - 2012. - 99 с.

7. «Экономико-математические методы и модели» под редакцией С.Ф. Миксюк, - 2008 - 311 с.

8. http://www.reshmat.ru/ZLP_Graf.html

9. http://www.ccas.ru/mmes/educat/lab05/04/graphich.html

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