Учебное пособие разработано в соответствие с программой дисциплины «Математические методы моделирования экономических систем»






НазваниеУчебное пособие разработано в соответствие с программой дисциплины «Математические методы моделирования экономических систем»
страница9/17
Дата публикации05.03.2016
Размер1.91 Mb.
ТипУчебное пособие
e.120-bal.ru > Экономика > Учебное пособие
1   ...   5   6   7   8   9   10   11   12   ...   17

В частном случае, если µ §, то система (3.2) - (3.3) состоит только из линейных неравенств, а если µ §, то ЁC из линейных уравнений.

Если математическая модель задачи линейного программирова­ния имеет вид:

µ § (3.5)

µ § (3.6)

µ §

µ § (3.7)

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

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

Правило приведения задачи линейного программирования к канони­ческому виду состоит в следующем:

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

если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;

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

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

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

Z(X) = c1x1 + c2x2 + ЎK + cnxn Ўж (max) min (3.8)
µ § (3.9)
xjЎЭ0, j = 1,2,ЎK,n
Пример 3.1. Привести к канонической форме задачу линейного программирования:

µ §

Решение

Введем в каждое уравнение системы ограничений выравнивающие переменные x4, x5, x6. Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений пере­вранные x4, x6 вводятся в левую часть со знаком «+», а во второе уравнение вводится со знаком «-».

µ §
Свободные члены в канонической форме должны быть поло­жительными, для этого два последних уравнения умножим на -1:

µ §

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

µ § где µ §

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

µ §
Рассмотрим процесс построения математических моделей задач линейного программирования на примере.

Пример 3.2. Использование мощностей оборудования.

Предприятие имеет m моделей машин различных мощностей. Задан план по времени и номенклатуре: Т ЎЄ время работы каждой машины; продукции j-го вида должно быть выпущено не менее Nj единиц.

Необходимо составить такой план работы оборудования, чтобы обеспечить минимальные затраты на производство, если известны производительность каждой i-й машины по выпуску j-го вида про­дукции µ § и стоимость единицы времени, затрачиваемого i-й ма­шиной на выпуск j-го вида продукции µ §.

Другими словами, задача для предприятия состоит в следую­щем: требуется определить время работы i-й машины по выпуску j-го вида продукции µ §, обеспечивающее минимальные затраты на производство при соблюдении ограничений по общему времени работы машин Т и заданному количеству продукции Nj .

По условию задачи машины работают заданное время T, поэто­му данное ограничение можно представить в следующем виде:

µ §

Ограничение по заданному количеству продукции выглядит следующим образом:

µ §

Задача решается на минимум затрат на производство:

µ §

Необходимо также учесть неотрицательность переменных µ §.

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

µ §

µ §

µ §

µ §

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

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

решения задач с двумя переменными, когда ограничения выра­жены неравенствами;

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

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

Z(X) = c1x1 + c2x2 Ўж (min) max (3.10)
µ § (3.11)
X1 ЎЭ 0, X2 ЎЭ 0 (3.12)
Каждое из неравенств системы ограничений за­дачи геометрически определяет полуплоскость соответственно с граничными прямыми µ § µ §. В том случае, если система неравенств совместна, об­ласть ее решений есть множество точек, принадлежащих всем ука­занным полуплоскостям. Так как множество точек пересечения данных полуплоскостей ЎЄ выпуклое, то областью допустимых ре­шений является выпуклое множество, которое называется много­угольником решений. Стороны этого многоугольника лежат на пря­мых, уравнения которых получаются из исходной системы ограни­чений заменой знаков неравенств на знаки равенств.

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

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

Для нахождения среди допустимых решений оптимального решения используют линии уровня и опорные прямые.

Линией уровня называется прямая, на которой целевая функция задачи принимает постоянное значение. Уравнение линии уровня в общем случае имеет вид c1x1 + c2x2 = l, где l ЁC const. Все линии уровня параллельны между собой. Их нормаль µ §

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

Вектор µ § с координатами с1 и с2, перпендикулярный к этим прямым, указывает направление наискорейшего возраста­ния Z, а противоположный вектор ЁC направление убывания Z.

Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (3.11) - (3.12) и семейство параллельных прямых (3.10), то задача определения максимума функции Z сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z = const, и которая соответствует наибольшему значению параметра Z.

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

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

Заканчивая рассмотрение геометрической интерпретации зада­чи (3.10) ЎЄ (3.12), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 3.1- 3.4. Рис. 3.1 харак­теризует такой случай, когда целевая функция принимает макси­мальное значение в единственной точке А. Из рис. 3.2 видно, что максимальное значение целевая функция принимает в любой точ­ке отрезка АВ.

На рис. 3.3 изображен случай, когда максимум недостижим, а на рис. 3.4 ЎЄ случай, когда система ограничений задачи несовмест­на. Отметим, что нахождение минимального значения Z при дан­ной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уров­ня Z передвигается не в направлении вектора µ §, а в про­тивоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минималь­ного значения.

B

Zmin

Z=0

0

0

Z=0

C

X1

X1

µ §



Рис. 3.1. Оптимум функции Z достижим в точке А

Рис. 3.3. Оптимум функции Z не достижим

Рис. 3.2. Оптимум функции Z достигается в любой точке µ §

Рис. 3.4. Область допустимых решений ЁC пустая область

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

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

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

Определить многоугольник решений.

Построить вектор µ § .

Построить прямую µ §, проходящую через на­учало координат и перпендикулярную вектору µ §.

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

Определить координаты точки максимума функции и вычислить значение целевой функции в этой точке.
Пример 3.3. Определение оптимального ассортимента продукции.

Предприятие изготавливает два вида продукции - µ § иµ §, ко­торая поступает в оптовую продажу. Для производства продукций используются два вида сырья - А и В. Максимально возможные за­пасы сырья в сутки составляют 9 и 13 единиц соответственно. Рас­ход сырья на единицу продукции вида µ §, и вида µ § дан в табл. 3.1.

Таблица 3.1

Расход сырья продукции
СырьеРасход сырья

на 1 ед. продукции

Запас сырья, ед.µ §µ §А

В2

33

29

13

Опыт работы показал, что суточный спрос на продукцию µ § никогда не превышает спроса на продукцию µ § более чем на 1 ед. Кроме того, известно, что спрос на продукцию µ § никогда не пре­вышает 2 ед. в сутки.

Оптовые цены единицы продукции равны: 3 д. е. ЎЄ для µ § и 4 д. е. для µ §.

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

Решение

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

µ §

Доход от реализацииµ § единиц продукции µ § и µ § единиц продукции µ § составит µ §.

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

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

Построим многоугольник решений (рис. 3.5). Для этого в сис­теме координат Х10Х2 на плоскости изобразим граничные прямые:

µ § µ §

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

Для построения прямой µ § строим вектор-гради­ент µ § и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора µ § . Из рис. 3.5 следует, что по отноше­нию к многоугольнику решений опорной эта прямая становится в точке С, где функция принимает максимальное значение. Точка С лежит на пересечении прямых µ §иµ §. Для определения ее коорди­нат решим систему уравнений:

µ §


Рис. 3.5. Решение задачи (пример 3.3) линейного программирования геометрическим способом
Оптимальный план задачиµ §=2,4; µ §=1,4. Подставляя значе­ния µ §иµ § в линейную функцию, получим:

µ §

Полученное решение означает, что объем производства продук­ции µ § должен быть равен 2,4 ед., а продукции µ § ЎЄ 1,4 ед. Доход, получаемый в этом случае, составит: Z = 12,8 д. е.

Геометрическим способом можно также решать задачи линей­ного программирования с числом переменных более двух. Для это­го исходную задачу преобразуют методом ЖорданаЎЄГаусса.
Пример 3.4. Решить задачу линейного программирования:
µ §

µ §

µ §

Методом Жордана-Гаусса приведем систему уравнений-ограничений задачи к равносильной разрешенной (табл. 3.2). Одновременно исключим разрешенные неизвестные из целевой функции.
Таблица 3.2

x1x2x3x4x5b-1112-341141-830110-4-4-1-11370-1112-34203-1-5-1100-2-1-8-2025440110-4-40033-315100-2-1-800212-12010-1-3-90011-15100-2-1-8000-14-22

Используя последнюю часть табл. 3.2, запишем задачу линейного программирования в преобразованном виде:

µ §

µ §

µ §

Отбросим в уравнениях-ограничениях неотрицательные разрешенные неизвестные x1, x2, x3 и заменим знаки равенства знаками неравенства, получим вспомогательную задачу линейного программирования с двумя переменными:
µ §

µ §
µ §
Решаем задачу графическим методом (рис. 3.6). Свободный член в целевой функции 22 на отыскание оптимального решения не влияет и учитывается только при вычислении значения целевой функции.


Рис. 3.6. Решение задачи (пример 3.4) линейного программирования геометрическим способом

Находим оптимальное решение вспомогательной задачи µ §
µ §

µ §

µ §

Вычисляем минимальное значение целевой функции Z(X*) = -1*6 + 4*1 + 22 = 20.

Находим оптимальное решение исходной задачи. Для этого используем систему ограничений в разрешенном виде:

µ §
Вычисляем: Х2* = -9 + Х4* + 3 Х5* = -9+6+3*1=0

Х3* = 5 ЁC Х4* + Х5* = 5-6+1 = 0

Х1* = -8 + 2 Х4*+ Х5*= -8+2*6 + 1 = 5

Получаем Х* = (5,0,0,6,1)

Ответ: min Z(X) = 20 при Х* = (5,0,0,6,1)
3.1.3. Симплекс-метод

Симплексный метод основывается на следующем:

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

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

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

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

Основное содержание симплексного метода:

найти начальное опорное решение;
1   ...   5   6   7   8   9   10   11   12   ...   17

Похожие:

Учебное пособие разработано в соответствие с программой дисциплины «Математические методы моделирования экономических систем» iconЛитература: Бережная Е. В., Бережной В. И. Математические методы...
Роль математических методов в принятии оптимальных решений. Классификация методов и область их применения

Учебное пособие разработано в соответствие с программой дисциплины «Математические методы моделирования экономических систем» iconУчебное пособие подготовлено в соответствии с программой курса по...
Учебное пособие предназначено для студентов экономических специальностей

Учебное пособие разработано в соответствие с программой дисциплины «Математические методы моделирования экономических систем» iconВопросы к экзамену “ Экономико-математические модели”
Роль моделирования в развитии экономической науки. Основные свойства экономических систем и роль экономико-математических моделей...

Учебное пособие разработано в соответствие с программой дисциплины «Математические методы моделирования экономических систем» iconУчебно-методический комплекс по дисциплине «Математические методы в исторических исследованиях»
Учебно-методическое пособие предназначено для студентов ннгу, обучающихся по направлению подготовки 030600. 62 «История», изучающих...

Учебное пособие разработано в соответствие с программой дисциплины «Математические методы моделирования экономических систем» iconГраф научных интересов
Методы общей теории систем, математического описания, моделирования, оптимизации, обработки результатов испытаний систем управления...

Учебное пособие разработано в соответствие с программой дисциплины «Математические методы моделирования экономических систем» iconМ. В. Облаухова Математические модели макроэкономики
Учебное пособие предназначено для изучения курсов «Экономическая теория», «Экономико-математические модели», «Макроэкономика. Продвинутый...

Учебное пособие разработано в соответствие с программой дисциплины «Математические методы моделирования экономических систем» icon«Экономико-математическое моделирование воспроизводственных взаимодействий...
Официальный оппонент: Ермолаев Михаил Борисович доктор экономических наук, профессор, профессор кафедры экономики и финансов фгбоу...

Учебное пособие разработано в соответствие с программой дисциплины «Математические методы моделирования экономических систем» iconТема: «Математические расчеты семейного бюджета»
Математическая экономика – теоретическая и прикладная наука, предметом которой являются математические модели экономических объектов...

Учебное пособие разработано в соответствие с программой дисциплины «Математические методы моделирования экономических систем» iconМногоуровневые модели зависимости экономического роста от инвестиций: эконометрический подход
Специальность 08. 00. 13 «Математические и инструментальные методы экономики» (математические методы)

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






При копировании материала укажите ссылку © 2016
контакты
e.120-bal.ru
..На главную