Основы математики и ее приложения в экономическом образовании (стр. 32 )

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

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

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

Наиболее разработанным разделом математического про­граммирования является линейное программирование.

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

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

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

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

Динамическое программирование — один из разделов ме­тодов оптимизации, в котором процесс принятия решения мо­жет быть разбит на отдельные этапы. В основе метода лежит принцип оптимальности, разработанный Р. Беллманом.

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

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

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

Часть 5. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Общая постановка задачи

Определение 1. Линейное программирование — наука о ме­тодах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения.

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

Определение 2. Математическое выражение целевой функ­ции и ее ограничений называется математической моделью экономической задачи.

В общем виде математическая модель задачи линейного программирования (ЛП) записывается как

при ограничениях:

где xj — неизвестные; aij, bi, cj — заданные постоянные вели­чины.

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

Математическая модель в более краткой записи имеет вид

при ограничениях:

Определение 3. Допустимым решением (планом) зада­чи линейного программирования называется вектор = (x1, x2,..., xп), удовлетворяющий системе ограничений.

Множество допустимых решений образует область допус­тимых решений (ОДР).

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

Базисное допустимое решение (х1, х2,..., xr, 0, …, 0) яв­ляется опорным решением, где r — ранг системы ограничений.

Виды математических моделей

Математическая модель задачи ЛП может быть каноничес­кой и неканонической.

Определение 5. Если все ограничения системы заданы урав­нениями и переменные xj неотрицательные, то такая модель задачи называется канонической.

Если хотя бы одно ограничение является неравенством, то модель задачи ЛП является неканонической. Чтобы перейти от неканонической модели к канонической, необходимо в каждое неравенство ввести балансовую переменную xn+i. Если знак неравенства ≤, то балансовая переменная вводится со знаком плюс, если знак неравенства ≥, то — минус. В целевую функ­цию балансовые переменные не вводятся.

Чтобы составить математическую модель задачи ЛП, не­обходимо:

— ввести обозначения переменных;

— исходя из цели экономических исследований, составить целевую функцию;

— учитывая ограничения в использовании экономических показателей задачи и их количественные закономернос­ти, записать систему ограничений.

Для рассмотрения решения задач линейного программиро­вания дадим некоторые понятия аналитической геометрии в n-мерном пространстве.

19.1. Основные понятия и определения

Дано n-мерное пространство, точки которого имеют коор­динаты (x1, x2, . . . ,xп).

Определение 1. Множество точек n-мерного пространства, координаты которых удовлетворяют уравнению

где хотя бы одно из чисел а1, a2, ..., an отлично от нуля, на­зывается гиперплоскостью п-мерного пространства.

В векторной форме оно записывается следующим образом:

где = (a1, a2,..., an), = (x1, x2,..., xn).

Даны две гиперплоскости

Определение 2. Множество точек n-мерного пространства, координаты которых одновременно удовлетворяют каждому уравнению системы, называется пересечением гиперплоскос­тей.

Дано неравенство

Эта зависимость определяет полуплоскость двухмерного про­странства, лежащую по одну сторону от прямой

которая называется граничной прямой.

Определение 3. Множество точек n-мерного пространства, координаты которых удовлетворяют неравенству

называется полупространством n-мерного пространства, рас­положенным по одну сторону от гиперплоскости

Определение 4. Множество точек n-мерного пространства, содержащее вместе с любыми двумя точками A и В и все точ­ки отрезка АВ, называется выпуклым телом (областью, фи­гурой).

Примеры плоских выпуклых фигур приведены на рис. 19.1.

Примеры невыпуклых фигур приведены на рис. 19.2.

Дадим некоторые определения выпуклой области.

Определение 5. Точка А называется внутренней точкой вы­пуклой области, если в сколь угодно малой окрестности этой точки содержатся только точки этой области.

Определение 6. Точка В называется граничной точкой вы­пуклой области, если в сколь угодно малой окрестности этой точки содержатся как точки данной области, так и не принад­лежащие ей (рис. 19.3).

Определение 7. Точка С называется угловой точкой вы­пуклой области, если она является граничной и не лежит внутри отрезка, соединяющего две другие точки этой облас­ти (рис. 19.3).

Определение 8. Если область включает все свои граничные точки, то она называется замкнутой.

Выпуклая область может быть ограниченной и неограни­ченной.

Определение 9. Ограниченной называется область, если су­ществует такое число М > 0, что радиус-вектор , соединяю­щий начало координат с любой точкой области, по абсолютной величине меньше М, т. е. || ≤ М.

Для этой области все ее точки находятся на конечном рас­стоянии от начала координат.

Определение 10. Если найдутся точки области, сколь угод­но удаленные от начала координат, то область называется не­ограниченной.

Определение 11. Выпуклая замкнутая ограниченная область, имеющая конечное число угловых точек, называется вы­пуклым п-мерным многогранником.

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

Определение 13. Линейная комбинация S векторов

в которой коэффициенты ti удовлетворяют условиям

называется выпуклой линейной комбинацией.

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

ТЕОРЕМА 1. Пересечение выпуклых областей есть выпуклая область.

ТЕОРЕМА 2. Множество точек выпуклого п-мерного много­гранника совпадает с множеством любых выпуклых линейных комбинаций его угловых точек.

19.2. Решение систем m линейных неравенств с двумя переменными

Дана система т линейных неравенств с двумя переменными

Знаки некоторых или всех неравенств могут быть ≥.

Рассмотрим первое неравенство в системе координат Х1ОХ2. Построим прямую

которая является граничной прямой.

Эта прямая делит плоскость на две полуплоскости 1 и 2 (рис. 19.4).

Полуплоскость 1 содержит начало координат, полуплос­кость 2 не содержит начала координат.

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

Направление полуплоскости на рисунках показываем стрел­кой.

Определение 15. Решением каждого неравенства систе­мы является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее.

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

Определение 17. Область решения системы, удовлетворяю­щая условиям неотрицательности (xj ≥ 0, j = ), называ­ется областью неотрицательных, или допустимых, решений (ОДР).

Если система неравенств совместна, то ОР и ОДР могут быть многогранником, неограниченной многогранной облас­тью или одной точкой.

Если система неравенств несовместна, то ОР и ОДР — пус­тое множество.

Пример 1. Найти ОР и ОДР системы неравенств и опреде­лить координаты угловых точек ОДР

Решение. Найдем ОР первого неравенства: х1 + 3x2 ≥ 3. Построим граничную прямую х1 +3x2 – 3 = 0 (рис. 19.5). Под­ставим координаты точки (0,0) в неравенство: 1∙0 + 3∙0 > 3; так как координаты точки (0,0) не удовлетворяют ему, то решени­ем неравенства (19.1) является полуплоскость, не содержащая точку (0,0).

Аналогично найдем решения остальных неравенств систе­мы. Получим, что ОР и ОДР системы неравенств является выпуклый многогранник ABCD.

Найдем угловые точки многогранника. Точку А определим как точку пересечения прямых

Решая систему, получим А(3/7, 6/7).

Точку В найдем как точку пересечения прямых

Из системы получим B(5/3, 10/3). Аналогично найдем коорди­наты точек С и D: С(11/4; 9/14), D(3/10; 21/10).

Пример 2. Найти ОР и ОДР системы неравенств

Решение. Построим прямые и определим решения не­равенств (19.5)-(19.7). ОР и ОДР являются неограниченные многогранные области ACFM и ABDEKM соответственно (рис. 19.6).

Пример 3. Найти ОР и ОДР системы неравенств

Решение. Найдем решения неравенств (19.8)-(19.10) (рис. 19.7). ОР представляет неограниченную многогранную область ABC; ОДР — точка В.

Пример 4. Найти OP и ОДР системы неравенств

Решение. Построив прямые, найдем решения неравенств системы. ОР и ОДР несовместны (рис. 19.8).

УПРАЖНЕНИЯ

Найти ОР и ОДР систем неравенств

20.1. Постановка задачи

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

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

Для нахождения экстремального значения целевой функ­ции при графическом решении задач ЛП используют вектор L() на плоскости Х1ОХ2, который обозначим . Этот вектор показывает направление наискорейшего изменения це­левой функции, он равен

где е1 и е2 — единичные векторы по осям OX1 и ОX2 соответ­ственно; таким образом, = (∂L/∂х1, ∂L/∂х2). Координатами вектора являются коэффициенты целевой функции L().

20.2. Алгоритм решения задач

1. Находим область допустимых решений системы ограни­чений задачи.

2. Строим вектор .

3. Проводим линию уровня L0, которая перпендикулярна .

4. Линию уровня перемещаем по направлению вектора для задач на максимум и в направлении, противоположном , для задач на минимум.

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

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

где 0 ≤ t ≤ 1, 1 и 2 — оптимальные решения в угловых точках ОДР.

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

5. Находим координаты точки экстремума и значение це­левой функции в ней.

20.3. Выбор оптимального варианта выпуска изделий

Фирма выпускает 2 вида мороженого: сливочное и шоко­ладное. Для изготовления мороженого используются два ис­ходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы даны в табл. 20.1.

Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не бо­лее чем на 100 кг. Кроме того, установлено, что спрос на шо­коладное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого 16 р., шоколадного — 14 р.

Какое количество мороженого каждого вида должна про­изводить фирма, чтобы доход от реализации продукции был максимальным?

Решение. Обозначим: x1 — суточный объем выпуска сли­вочного мороженого, кг; x2 — суточный объем выпуска шоко­ладного мороженого, кг.

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

Целевая функция будет иметь вид

при ограничениях:

OABDEF — область допустимых решений (рис. 20.1). Строим вектор (1, 1). Линия уровня L0 задается уравнением

Перемещаем линию уровня по направлению вектора . Точ­кой выхода L0 из области допустимых решений является точка D, ее координаты определяются как пересечение прямых, за­данных уравнениями:

Решая систему, получим координаты точки D (312,5; 300), в которой и будет оптимальное решение, т. е.

при этом

Таким образом, фирма должна выпускать в сутки 312,5 кг сли­вочного мороженого и 300 кг шоколадного мороженого, при этом доход от реализации составит 9 200 р.

20.4. Экономический анализ задач с использованием графического метода

Проведем экономический анализ рассмотренной выше за­дачи по производству мороженого.

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

при ограничениях:

Согласно найденному оптимальному решению, фирме необ­ходимо выпускать в сутки 312,5 кг сливочного и 300 кг шоко­ладного мороженого, при этом максимально возможный доход составит 9 200 р.

Определим, как влияет на оптимальное решение увеличе­ние или уменьшение запасов исходных продуктов. Для анализа задачи примем, что неравенства системы ограничений могут быть активными или пассивными. Если прямая проходит че­рез точку, в которой находится оптимальное решение, то будем считать, что она представляет активное ограничение. В про­тивном случае прямая относится к пассивному ограничению.

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

Рассмотрим увеличение ресурса правой части ограничения (20.1) по молоку (рис. 20.2). При перемещении параллельно са­мой себе прямой (20.1) вправо до пересечения с прямыми (20.2) и (20.3) в точке М ограничение (20.1) будет оставаться актив­ным. Точку М определим как точку пересечения прямых (20.2) и (20.3):

Откуда получаем М(370,83; 270,3).

Подставляя координаты точки М в уравнение (20.1), полу­чим предельно допустимый суточный запас молока: