Углирж. Учебное пособие для студентов I курса факультета международного бизнеса, направление подготовки Реклама и связи с общественностью
 Скачать 5.93 Mb.
|
|
Под математической моделью экономической задачи будем понимать совокупность математических соотношений, описывающих рассматриваемый экономический процесс. Для составления математической модели необходимо а) выбрать переменные величины задачи б) составить систему ограничений в) задать целевую функцию. Переменными задачи называются величины x 1 , x 2 , x 3 , . . . , x с помощью которых можно полностью описать рассматриваемый процесс. Их обычно записывают в виде вектора = (x 1 , x 2 , x 3 , . . . , x Системой ограничений задачи называется совокупность уравнений и неравенств, которым удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других экономических условий, например, условия положительности переменных. В общем случае система ограничений имеет вид i (x 1 , x 2 , x 3 , . . . , x n ) = 0, i = 1, 2, . . . , k, v i (x 1 , x 2 , x 3 , . . . , x n ) ≤ 0 (≥ 0), i = k + 1, k + 2, . . . , m. 188 Целевой функцией называют функцию) = f (x 1 ,x 2 ,x 3 ,. . . , x n ) переменных задачи, которая характеризует качество выполнения задачи и экстремум которой необходимо найти. В общем виде математическая постановка задачи математического программирования состоит в нахождении такого вектора = (x 1 , x 2 , x 3 , . . . , x n ) (те. в нахождении значений переменных, который обеспечивает наибольшее или наименьшее значение целевой функции Z(X) те или) → min) и удовлетворяет системе ограничений g i (x 1 , x 2 , x 3 , . . . , x n ) = 0, i = 1, 2, . . . , k, v i (x 1 , x 2 , x 3 , . . . , x n ) ≤ 0 (≥ 0), i = k + 1, k + 2, . . . , Задачи математического программирования делятся на задачи линейного и нелинейного программирования. Если все функции и v i – линейны, то соответствующая задача является задачей линейного программирования. Если хотя бы одна из указанных функций – нелинейная, то соответствующая задача является задачей нелинейного программирования. В дальнейшем (для простоты) будем рассматривать только задачи линейного программирования. Сформулируем общий вид такой задачи требуется найти экстремум функции) = a 1 x 1 + a 2 x 2 + a 3 x 3 + . . . + a n x n → max (при ограничениях+ a 12 x 2 + a 13 x 3 + . . . + a 1n x n ≤ (≥ 0) b 1 , a k1 x 1 + a k2 x 2 + a k3 x 3 + . . . + a kn x n ≤ (≥ 0) b k , a k+1,1 x 1 + a k+1,2 x 2 + a k+1,3 x 3 + . . . + a k+1,n x n = b k+1 , a m,1 x 1 + a m,2 x 2 + a m,3 x 3 + . . . + a m,n x n = b m , x j ≥ 0, j = 1, 2, . . . p, p ≤ n. 189 Задача в краткой записи имет вид Z(x) = n j=1 c j x j → max (при ограничениях j=1 a ij x j ≤ (≥ 0) b i , i = 1, 2, . . . , k, n j=1 a ij x j = b i , i = k + 1, k + 2, . . . , m, x j ≥ 0, j = 1, 2, . . . , p, p Замечание. Говорят, что задача линейного программирования представлена в канонической форме, если все ее ограничения заданы в виде уравнений. Если в задаче линейного программирования все ограничения заданы в виде неравенств, то говорят, что задача представлена в симметрической форме. Допустимым решением (планом) задачи линейного программирования называется любой мерный вектор = (x 1 , x 2 , x 3 , . . . , x n ), удовлетворяющий системе ограничений и условиям неот- рицательности. Множество допустимых решений задачи образует область допустимых решений. Оптимальным решением (планом) задачи линейного программирования называют такое допустимое решение (план) задачи, при котором целевая функция достигает экстремума. Замечание. Таким образом, оптимизационные модели отражают в математической форме смысл экономической задачи. Отличительной особенностью этих моделей является наличие условия нахождения оптимального решения (критерии оптимальности), которое записывается в виде функционала (переменная величина, зависящая от одного или нескольких условий. Эти модели при определенных исходных данных задачи позволяют получить множество решений, удовлетворяющих условиям задачи, и обеспечивают выбор оптимального решения, отвечающего критерию оптимальности. Составление математической модели расчета оптимальной производственной программы. Для того, чтобы процесс составления математической модели расчета оптимальной производственной программы предприятия был изложен проще и доступнее, рассмотрим его на конкретном примере. Задача на составление смеси. Пусть известны дневная потребность в белках, жирах, углеводах и витаминах содержание этих веществ в имеющихся продуктах цены единиц каждого продукта. Требуется составить такой рацион, который, удовлетворяя дневной потребности в необходимых веществах, был бы наиболее дешевым. Известно, что откорм животных экономически выгоден при условии, когда каждое животное получает в дневном рационе не менее 6 единиц питательного вещества A, не менее 12 единиц питательного вещества B и не менее 4 единиц питательного вещества. Для откорма животных используют два вида кормов. Следующая таблица показывает сколько единиц каждого питательного вещества содержит 1 кг каждого вида корма: Цена корма 1 – 5 ден. еда корма 2 – 6 ден. ед. Какое количество каждого вида корма необходимо расходовать, чтобы затраты на него были минимальными? Решение. Построим математическую модель этой задачи. Число единиц корма 1, входимого в дневной рацион, обозначим через, корма 2 – через x 2 . Используя условия и ограничения, указанные в условии задачи, можно составить три неравенства+ x 2 ≥ 6, 2x 1 + 4x 2 ≥ 12 и 2x 1 + 2x 2 ≥ 4. Целевая функция, описывающая условия данной задачи, будет иметь вид, x 2 ) = 5x 1 + Таким образом, математическая модель, полностью отражающая условия задачи, принимает вид, x 2 ) = 5x 1 + 6x 2 → min 191 2x 1 + x 2 ≥ 6, 2x 1 + 4x 2 ≥ 12, 2x 1 + 2x 2 ≥ 4, x i ≥ 0, i = 1, 2. 7.3. Графический метод решения задачи линейного программирования. Пользуясь случаем, что рассмотренная в предыдущем пункте задача содержит всего две переменные, ее можно решить графическим способом, который состоит из нескольких этапов строится многоугольная область допустимых решений предложенной задачи линейного программирования в декартовой системе координат строится вектор-градиент целевой функции в какой нибудь точке принадлежащей области допустимых решений Z = ∂Z ∂x 1 ; ∂Z ∂x 2 = (c 1 ; c 2 ); – линия уровня c 1 x 1 + c 2 x 2 = a (a – постоянная величина) прямая, перпендикулярная вектору-градиенту, – передвигается в направлении этого вектора в случае максимизации Z(x 1 ; x 2 ) до тех пор, пока не покинет пределов области допустимых решений. Предельная точка (или точки) области при этом движении и является точкой максимума Z(x 1 ; x 2 ); – для нахождения координат точки максимума достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума значение, найденное в получаемой точке, является максималь- ным. Замечание 1. При минимизации функции Z(x 1 ; x 2 ) линия уровня перемещается в направлении, противоположном вектору-гра- диенту. Замечание 2. Если прямая, соответствующая линии уровня, при своем движении не покидает области допустимых решений, то минимум (максимум) функции Z(x 1 ; x 2 ) не существует. Замечание 3. Если линия уровня параллельна какому-либо функциональному ограничению задачи, то оптимальное значение целевой функции будет достигаться в любой точке этого ограничения, лежащей между двумя оптимальными угловыми точками, и, соответственно, любая из этих точек является оптимальным решением задачи линейного программирования. Продолжим решение задачи на составление смеси. Прежде всего укажем в декартовой системе координат (далее по тексту см. рис. 25) область допустимых решений. Рассмотрим первое ограничение системы 2x 1 + x 2 ≥ 6. Проведем в системе координат прямую, соответствующую этому ограничению. Уравнение этой прямой будет получено, если оно будет записано как равенство 2x 1 + x 2 = 6. Для выявления точек, координаты которых строго удовлетворяют данному ограничению, нужно указать на одну из образовавшихся полуплоскостей. Для определения полуплоскости, координаты которой являются строгими решениями данного неравенства, необходимо выбрать пробную точку, явно принадлежащую какой-либо из двух полуплоскостей, полученных после проведения прямой, соответствующей этому неравенству. Если координаты пробной точки обращают неравенство в верное числовое неравенство, то полуплоскость, которой она принадлежит, является искомой. Если числовое неравенство получилось ложным, то указывается (например, штриховкой) полуплосколсть, которой не принадлежит пробная точка. Взяв для данного условия точку (0; 0) видно, что нужная нам полуплоскость на рисунке расположена выше построенной прямой. Подобным образом следует поступить с каждым ограничением и граничным условием поставленной задачи. В результате мы получаем открытую часть плоскости, лежащую впервой четверти декартовой системы координат (на рисунке показана штрихов- кой). Под линией уровня целевой функции данной задачи понимается геометрическое место точек, для которых зависимая переменная имеет постоянное числовое значение. Например, уравнение линии нулевого уровня будет иметь вид 0 = 5x 1 + 6x 2 , или уравнение линии уровня 20 будет иметь видит. д Очевидно, что для всех возможных значений линии уровня целевой функции являются прямыми, которые будут параллельными между собой и покрывать всю плоскость. Под градиентом целевой функции данной задачи понимается вектор grad Z = (5; 6). Очевидно, что в случае линейной целевой функции направление градиента не зависит от положения точки, от которой он откладывается. Построим вектор-градиент и перпендикулярно ему линию нулевого уровня. Окончательно рис. принимает следующий вид: Рис. Так как мы решаем задачу на минимизацию заданной функции, то необходимо определить наиболее близкую по отношению к направлению градиента линию уровня, имеющую общую точку с областью допустимых решений. Такой линией уровняв данном случае является линия, проходящая через точку (2; 2), Эта точка получается от пересечения двух прямых 2x 1 + x 2 = 6 и+ 4x 2 = 12. Значит, в этой точке достигается минимальное значение уровня целевой функции над построенной областью допустимых решений, которое легко вычисляется постановкой координат точки в целевую функцию Z = 5 · 2 + 6 · 2 = 22. Отсюда оптимальным решением задачи является x 1 = 2 и x 2 = 2. Другими словами – в дневном рационе должно быть по 2 ед. каждого из двух видов корма. Технология решения задач линейного программирования с помощью надстройки Поиск решения в среде. Методы оптимизации пока не получили должного практического распространения при разработке управляющих решений в производственной и финансовой сферах, так каких применение требует определенной математической подготовки, а также использования высокопроизводительных ЭВМ, оснащенных соответствующими пакетами прикладных программ. Вместе стем возрастающие возможности персональных компьютеров и достижения в области програмного обеспечения открывают широкие перспективы для применения методов математической оптимизации в финансово-экономической сфере, делая их доступными широкому кругу специалистов. Замечание. Поиск решения – это надстройка Excel, в которой можно решать задачи оптимизации. Если вменю Сервис отсутствует команда Поиск решения, значит необходимо загрузить эту надстройку. Выполните команду Сервис → Надстройки и активизируйте надстройку Поиск решения, поставив галочку рядом с ней. Если в окне Надстройки нет элемента Поиск решения, необходимо доустановить Excel. Для этого необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и удаление программ и с помощью программы установки или Office) установить надстройку Поиск решения. После выбора команд Сервис → Поиск решения появится диалоговое окно Поиск решения. В диалоговом окне Поиск решения есть три основных параметра а) установить целевую ячейку; б) изменяя ячейки в) ограничения. Сначала нужно заполнить поле Установить целевую ячейку. Во всех задачах для средства Поиск решения оптимизируется результат водной из ячеек рабочего листа. Целевая ячейка связана с другими ячейками этого рабочего листа с помощью формул. Средство Поиск решения использует формулы, которые дают результат в целевой ячейке, для проверки возможных решений. Можно выбрать поиск наименьшего или наибольшего значения для целевой ячейки или установить конкретное значение. Второй важный параметр средства Поиск решения – это параметр Изменяя ячейки. Здесь указываются ячейки, значения которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К этим ячейкам предъявляется два основных требования они не должны содержать формул и изменение их значений должно отражаться на изменении результата в целевой ячейке. Другими словами, целевая ячейка зависит от изменяемых ячеек. Третий параметр, который нужно вводить на вкладке Поиск решения, – это ограничения. Для решения задачи необходимо 1) указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки) ввести исходные данные 3) ввести зависимость для целевой функции 4) ввести зависимости для ограничений 5) запустить команду Поиск решения 6) назначить ячейку для целевой функции (установить целевую ячейку 7) ввести ограничения 8) ввести параметры для решения задачи линейного программирова- ния. Вернемся к задаче, рассмотренной в пункте 7.2.: Z(x 1 , x 2 ) = 5x 1 + 6x 2 → min 2x 1 + x 2 ≥ 6, 2x 1 + 4x 2 ≥ 12, 2x 1 + 2x 2 ≥ 4, x i ≥ 0, i = 1, Рассмотрим технологию решения, используя данные рассматриваемой задачи. Вводим эти формулы переменные 0 3 x 2 целевая функция 5x 1 + 6x 2 = 5 · B2 + 6 · B3 ограничения 2x 1 + x 2 = 2 · B2 + B3 8 2x 1 + 4x 2 = 2 · B2 + 4 · B3 9 2x 1 + 2x 2 = 2 · B2 + 2 · B3 10 x 1 = B2 11 x 2 = Выделяем ячейку B5, в которой вычисляется целевая функция. Вызываем Сервис → Поиск решения. В диалоговом окне в поле ввода Установить целевую ячейку уже содержится Установим переключатель, Равный минимальному значению (согласно условию задачи. Щелкнем кнопку Предложить, ив поле ввода Изменяя ячейки появится $B$2 : $B$3. Щелкнем кнопку Добавить. Появится диалоговое окно Добавление ограничения. В поле ввода Ссылка на ячейку укажем $B$7. Правее, в выпадающем списке с условными операторами выберем >= (согласно условию задачи. В поле ввода Ограничение введем 6. Щелкнем кнопку Добавить и введем другие ограничения. Мы окажемся в диалоговом окне и увидим введенные ограничения. С помощью кнопок Изменить и Удалить мы можем изменить и удалить ограничение. Щелкнем Параметры. Установим два флажка Линейная модель и Неотрицательные значения. Далее ОК, Выполнить. Через непродолжительное время появятся результаты поиска решения и исходная таблица с заполненными ячейками переменные 2 3 x 2 целевая функция 5x 1 + 6x 2 22 ограничения 2x 1 + x 2 6 8 2x 1 + 4x 2 12 9 2x 1 + 2x 2 8 10 x 1 2 11 x 2 В результате решения задачи был получен ответ минимальные затраты достигаются при расходовании по 2 единицы каждого вида корма. ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ № ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ» Решить задачу линейного программирования графическим методом и с помощью надстройки Поиск решения в среде Excel: Вар. Задачи Вар. Задачи 1 Z(X) = 2x 1 + 4x 2 → max 2 Z(X) = 5x 1 + 7x 2 → max −2x 1 + x 2 ≤ 2, x 1 − 3x 2 ≥ −9, 4x 1 + 3x 2 ≤ 24, x i ≥ 0, i = 1, 2. −2x 1 + x 2 ≤ 2, −x 1 + 3x 2 ≥ 9, x 1 + x 2 ≤ 10, x i ≥ 0, i = 1, 2. 3 Z(X) = 5x 1 − 3x 2 → min 4 Z(X) = −x 1 − x 2 → min 4x 1 − x 2 ≥ 0, −x 1 + x 2 ≤ 3, 2x 1 − 3x 2 ≤ 6, x i ≥ 0, i = 1, 2. −3x 1 + 2x 2 ≤ 4, −x 1 + 2x 2 ≤ 8, x 1 + x 2 ≥ 10, 4x 1 − x 2 ≤ 20, x i ≥ 0, i = 1, 2. 198 Вар. Задачи Вар. Задачи 5 Z(X) = −2x 1 + 3x 2 → max 6 Z(X) = 5x 1 − x 2 → min −6x 1 + x 2 ≤ 3, −5x 1 + 9x 2 ≤ 45, x 1 − 3x 2 ≤ 3, x i ≥ 0, i = 1, 2. 2x 1 − 3x 2 ≤ 0, −5x 1 + 9x 2 ≤ 45, x 1 − 2x 2 ≤ 4, x i ≥ 0, i = 1, 2. 7 Z(X) = 3x 1 + 2x 2 → max 8 Z(X) = 4x 1 + 2x 2 → min −3x 1 + 2x 2 ≤ 4, −x 1 + 2x 2 ≤ 8, x 1 + x 2 ≤ 10, 4x 1 − x 2 ≤ 20, x i ≥ 0, i = 1, 2. −3x 1 + 2x 2 ≤ 6, x 1 + 2x 2 ≥ 10, x 1 − 3x 2 ≤ 6, x 1 + x 2 ≥ 6, x i ≥ 0, i = 1, 2. 9 Z(X) = 2x 1 + 4x 2 → max 10 Z(X) = −3x 1 − x 2 → min −3x 1 + 2x 2 ≤ 6, x 1 + 2x 2 ≥ 10, x 1 − 5x 2 ≤ 5, x 1 + x 2 ≤ 14, x i ≥ 0, i = 1, 2. 4x 1 − x 2 |