Экономико-математические методы

5. В вершинах цепи, чередуя проставляются знаки «+» и «-», начиная с выбранной свободной клетки (в нее помещают знак «+»). В клетках со знаком «-» выбирается минимальная поставка (, которая перераспределяется по цепи: там, где стоит знак «+» она прибавляется, а где «-» - отнимается. В результате чего баланс цикла не нарушается. Исходная свободная клетка становится занятой, а клетка в которой выбрана минимальная поставка - свободной (рис.3.1 а, б)

 а) б)

+ - 20 20

40

- + 80

20 60

Рис.3.1

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

а) б)

+ 4 - 3 33

20 20

- + 10 30

30 10

- 2 + 0 60

20 40

Рис.3.2

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

3.5 Пример решения транспортной задачи

На четырех строительных площадках В1, В2, В3, В4 монтируется в день соответственно 20,120,20 60 м3 сборных плит перекрытий. Производство этих плит налажено на трех заводах А1, А2, А3 в размере соответственно 100,70 и 50 м3. Известны стоимости перевозки (табл.2) 1м3 сборных плит из каждого пункта производства в каждый пункт потребления (ден. ед./ м3).

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

РЕШЕНИЕ.

Исходное опорное решение получим по методу «северо-западного угла» (табл.3) и по методу min элемента (табл.4).

Здесь,т.е имеем закрытую модель ТЗ (табл.2 ).

табл.2

Bj Ai	20	120	20	60
100	6	4	2	4
70	1	2	7	2
50	2	4	1	4

табл.3

Bj Ai	20	120	20	60
100	6 20	4 80	2	4
70	1	2 40	7 20	2 10
50	2	4	1	4 50

Транспортные расходы f=

табл.4

Bj Ai	20	120	20	60
100	6	4 100	2	4
70	1 20	2	7	2 50
50	2	4 20	1 20	4 10

f=

Транспортные расходы для опорного плана, построенного по методу min элемента, меньше. Поэтому за исходное решение возьмем то, которое получено по методу min элемента (табл.4).

Количество заполненных клеток в табл.4 равно 6: m+n-1=3+4-1=6.

Следовательно, полученный план невырожденный.

Для определения потенциалов (см. формула 3.8) составляем уравнения:

u1+v2=4, u2+v1=1, u2+v4=2, u3 +v2=4, u3+v3=1, u3+v4=4. Положим u1=0, тогда v2=4, u3=0, v3=1, v4=4, u2=-2, v1=3.

Потенциалы проставлены в табл.5 (последняя строка и последний столбец). Их можно вычислять и непосредственно в таблице не выписывая систему уравнений. Т.к. если известны потенциал и тариф (стоимость перевозки) занятой клетки, то из соотношения ui+vj=cij легко определить неизвестный потенциал (из суммы вычесть известное слагаемое, получим неизвестное слагаемое. Роль суммы в данном равенстве играет тариф cij)

Определим по формуле (3.9) оценки свободных клеток:

s11=6-(0+3)=3>0, s13=2-(0+1)=1>0, s14=4-(0+4)=0

s22=2-(-2+4)=0, s23=7-(-2+1)=8>0, s31=2-(0+3)= -1<0

табл.5 табл.6

Bj Ai	20	120	20	60	ui		Bj Ai	20	120	20	60	ui
100	6	4 100	2	4	0		100	6	4 100	2	4	0
70	- 1 20	2	7	+ 2 50	-2		70	- 1 10	+ 2	7	2 60	-1
50	2 +	4 20	1 20	-- 4 10	0		50	+ 2 10	- 4 20	1 20	4	0
vi	3	4	1	4			vj	2	4	1	3

План неоптимальный, т.к. s31<0. Строим для клетки (3;1) цикл непосредственно в табл.5. В цикл войдут клетки (3;1), (3;4), (2;4), (2;1). Наименьшее количество груза, стоящее в вершинах цикла с отрицательным знаком, В результате смещения по циклу получим новый план (табл.6). Транспортные расходы ( а были равны 660).

Будет ли полученный план оптимальным? План невырожденный.

Определим для него новые потенциалы:

u1+v2=4, u2+v1=1, u2+v4= 2, u3+v1=2, u3+v2=4, u3+v3=1. Положим u1=0, тогда v2=4, u3=0, v1=2, v3=1, u2= -1, v4=3. Проставим значения найденных потенциалов в табл.6.

Определим оценки свободных клеток:

s11=6-(0+2)=4>0, s13=2-(0+1)=1>0, s14=4-(0+3)=1>0

s22=2-(-1+4)=-1<0, s23=7-(-1+1)=7>0, s44=4-(0+3)=1>0.

План (табл.6) неоптимальный, т.к. s22<0. Строим для клетки (2;2) цикл непосредственно в табл.6. В цикл войдут клетки (2;2), (2;1), (3;1), (3;2). Наименьшее количество груза, стоящее в вершинах цикла с отрицательным знаком, В результате смещения по циклу получим новый план (табл.7). План невырожденный. Транспортные расходы

f = (а были равны 650).

Табл.7

Bj Ai	20	120	20	60	ui
100	6	4 100	2	4	0
70	1	2 10	7	2 60	-2
50	2 20	4 10	2444 1 1111 20	4	0
vj	2	4	1	4

Будет ли полученный план оптимальным?

Определим для него новые потенциалы:

u1+v2=4, u2+v2=2, u2+v4=2, u3+v1=2, u3+v2=4, u3+v3=1. Положим u1=0, тогда v2=4, u2=-2, v4=4, u3=0, v1= 2, v3=1. Проставим значения найденных потенциалов в табл.7.

Определим оценки свободных клеток:

s11=6-(0+2)=4>0, s13=2-(0+1)=1>0, s14=4-(0+4)=0

s21=1-(-2+2)=1>0, s23=7-(-2+1)=8>0, s34=4-(0+4)=0

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

x12=100, x22=10, x24=60, x31=20, x32=10, x33=20

Минимальные транспортные расходы для этого плана f=640.

Все оценки свободных клеток равны нулю. Это свидетельствует о неединственности оптимального плана.

ОТВЕТ.

Согласно оптимальному плану, с первого завода A1 нужно поставить 100м3 перекрытый на вторую строительную площадку B2, с завода А2 - 10м3 на строительную площадку В2 и 60м3 на строительную площадку В4, с завода А3 - на 20 м3 на строительную площадку В1, 10 м3 на строительную площадку В2 и 20 м3 на строительную площадку В3.

3.7 Транспортные задачи, имеющие некоторые усложнения в постановке

Транспортная задача с избытком запасов:



Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения Bn+1 с потребностью bn+1 и полагают стоимости перевозок грузов в Bn+1 равными нулю. Полученная новая транспортная задача является закрытой. Найдя оптимальный план xij этой транспортной задачи и отбрасывая в полученной таблице последний столбец, получим оптимальный план исходной транспортной задачи.

Транспортная задача с избытком заявок:

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

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

и «подправив» заявки: получим закрытую модель транспортной задачи.

Если не заботиться о «справедливости» удовлетворения заявок, а по-прежнему интересоваться лишь минимизацией транспортных расходов, то для отыскания оптимального плана вводят фиктивный пункт (m+1)-й отправления Am+1 с запасом груза am+1 и полагают стоимости перевозок грузов из Am+1 равными нулю. Полученная транспортная задача является закрытой. Найдя оптимальный план xij этой транспортной задачи и отбрасывая в полученной таблице последнюю строку, получим оптимальный план исходной транспортной задачи.

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

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

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

Транспортная задача с запретными маршрутами.

Речь идет о задачах, в которых нельзя перевозить груз из некоторых пунктов отправления Ai в некоторые пункты назначения Bj. В этом случае стоимости соответствующих перевозок полагаем равными достаточно большому числу. Тогда при отыскании оптимального плана соответствующие перевозки будут блокированы.

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

Иногда приходится решать транспортную задачу, в которой дополнительным условием в ограничениях является обязательное обеспечение конкретных перевозок по определенным маршрутам. В этом случае каждую обязательную перевозку xij=dij реализуем условно, уменьшая на dij запасы в Ai и потребности в Bj. Если это не удается сделать, то исходная задача не имеет решения. В противном случае стоимости обязательных поставок полагаем равными достаточно большому числу, решаем полученную задачу и от ее оптимального плана переходим к оптимальному плану исходной задачи.

Транспортная задача с ограничениями снизу.

Пусть требуется решить транспортную задачу, в которой некоторые из перевозок ограничены снизу xijpij. Организуем условные перевозки, уменьшив на pij запасы в Ai и потребности в Bj. Если это сделать не удается, то исходная задача решения не имеет, в противном случае решаем полученную задачу и от ее оптимального плана переходим к оптимальному плану исходной транспортной задачи.

3.8 Экономические задачи, сводящиеся к транспортным моделям

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

оптимальное закрепление за станками операций по обработке деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком;

оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью cij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;

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

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

ПРИМЕР. Выбор оптимального варианта использования производственного оборудования.

На предприятии имеются три группы станков, каждая из которых может выполнять пять операций по обработке деталей (операции могут выполняться в любом порядке). Максимальное время работы каждой группы станков соответственно равно 100, 250, 180 часов. Каждая операция должна выполняться соответственно 100, 120, 70, 130 часов.

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

Производительность каждой группы станков на каждую операцию задана матрицей

3 5 11 10 5

5 10 15 3 2

4 8 6 12 10

Оптимальное распределение оборудования

Оборудование m различных видов нужно распределить между n рабочими участками. Производительность одной единицы оборудования i-го вида на j-м рабочем участке равна pij; Потребность j-го участка в оборудовании составляет bj, Запас оборудования i-го вида равен ai, Найти распределение оборудования на рабочие участки, при котором суммарная производительность максимальная.

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

Обозначим через xij число единиц оборудования i-го вида, выделенное на j-й рабочий участок, Математическая модель задачи имеет следующий вид:

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

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

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

Формирование оптимального штата фирмы.

Фирма набирает штат сотрудников. Она располагает n группами различных должностей по bj вакантных единиц в каждой группе, Кандидаты для занятия должностей проходят тестирование, по результатам которого их разделяют на m групп по ai кандидатов в каждой группе, Для каждого кандидата из i-й группы требуются определенные затраты cij на обучение для занятия j-й должности, (В частности, некоторые cij=0, т.е. кандидат полностью соответствует должности, или cij=, т.е. кандидат вообще не может занять данную должность.) Требуется распределить кандидатов на должности, затратив минимальные средства на их обучение.

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

Обозначим через xij число кандидатов из i-й группы, назначенных на j-ю должность, Математическая модель задачи имеет следующий вид:

Методы решения этой задачи такие же, как и транспортной задачи.

ПРИМЕР 2. Имеется m видов сельскохозяйственных культур и n хозяйств, где их можно выращивать. Из-за различных условий доход, получаемый с 1 га посева одной и той же культуры, в различных хозяйствах неодинаков. Обозначим через cij доход для i-й культуры и j-го хозяйства. Общие площади посева культур ai (i=1,m) и площади пашни в хозяйствах bj (j=1,n) известны. Требуется составить такой план размещения сельскохозяйственных культур по хозяйствам, чтобы общий доход был максимальным.

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

Найти план X=(xij) такой, что

При условиях:

а) план посева по каждой культуре должен быть выполнен

б) пашня в хозяйствах должна быть использована полностью

в)

4. Нелинейное программирование

Во многих экономических моделях исследования операций зависимости между постоянными и переменными факторами лишь в первом приближении можно считать линейными, более детальное рассмотрение позволяет обнаружить их нелинейность. Как правило, такие показатели, как прибыль, себестоимость, капитальные затраты на производство и др., в действительности зависят от объема производства, расхода ресурсов и т.п. нелинейно. В этом случае возникает задача нелинейного программирования (ЗНП).

4.1 Общая задача нелинейного программирования

В общем виде ЗНП формулируется следующим образом:

, (4.1)

, (4.2)

, (4.3)

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

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

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

Процесс составления математической модели ЗНП принципиально не отличается от составления модели ЗЛП. Рассмотрим несколько примеров.

Задача 4.1. На m предприятиях выпускается некоторый продукт. Себестоимость единицы этого продукта на каждом из указанных предприятий есть , где - доля себестоимости, не зависящая от объема выпуска продукции, - план выпуска продукта на i-м предприятии.

Предприятия должны обеспечить n потребителей с потребностями , стоимость перевозки из i-го предприятия к j-му потребителю равна .

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

Математическую модель задачи. Пусть - план перевозок от i-го предприятия к j-му потребителю.

Для удобства запишем данные и искомые величины задач в виде таблицы:

Табл.4.1

Потребители Предприятия	1	2	...	n	План выпуска изделий
1	x11	x12	...	x1n	x1
2	x21	x22	...	x2n	x2
...
m	xm1	xm2		xmn	xm
Потребности заказчиков	b1	b2	...	bn

Система ограничений задачи:

(4.4)

Целевая функция f запишется так:

Вместо подставим значения, данные в условии задачи:

(4.5)

Надо найти минимальное значение функции (6.5) на множестве допустимых решений (4.4).

Задача 4.2. На производство некоторого продукта расходуется два вида ресурсов. Определите оптимальное распределение величин затрачиваемых ресурсов, если цена ресурса первого вида 30 рублей, второго - 40 рублей, а всего выделено на производство 120 рублей. Известно, что из количества x1 первого ресурса и x2 второго ресурса можно получить единиц продукта.

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

где - постоянные величины, причем

Функция y выведена в предположении, что существует только два ресурса: x1 - труд, x2 - капитал, где указывает на соответствующую долю использования каждого из этих ресурсов; c - некоторый постоянный коэффициент; y - это количество совокупного продукта, которое при определенных технологических условиях может быть получено из данных продуктов. Функция y простейшая производственная функция, так как рассматривает зависимость между двумя ресурсами и одним продуктом.

Математическая модель задачи. Пусть x1 - количество ресурсов вида 1, x2 - количество ресурсов вида 2. Система ограничений:

(4.6)

Целевая функция:

(4.7)

Требуется найти наибольшее значение функции (4.7) на множестве решений системы (4.6).

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

Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой или она не относится ни к тому, ни к другому классу.

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

Функцию y = f(x) одной переменной будем называть выпуклой, если отрезок, соединяющий две любые точки ее графика, принадлежит графику или расположен выше его. Функция вогнута, если отрезок, соединяющий две любые точки графика, принадлежит ему или расположен ниже его.

Аналогично можно сформулировать определения понятий вогнутой и выпуклой функций нескольких переменных. Говорят, что гиперповерхность z=f(x1,x2,...,xn) выпуклая, если отрезок, соединяющий две ее любые точки, лежит на поверхности или выше ее. Гиперповерхность z=f(x1,x2,...,xn) вогнута, если отрезок, соединяющий две ее любые точки, лежит на поверхности или ниже ее.

Пусть дана функция , определенная на замкнутом множестве Ф. Элементами множества Ф являются точки . Поэтому функцию можно записать так: .

Говорят, что функция , определенная на некотором множестве X, достигает в точке локального максимума (локального минимума), если найдется такое число , что для всех , удовлетворяющих неравенству , выполняется неравенство

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

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

Точка , в которой все частные производные функции равны 0, называется стационарной точкой.

Необходимое условие экстремума. Если в точке функция имеет экстремум, то частные производные функции в этой точке равны нулю:

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



Достаточные условия экстремума:

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

б) если может принимать в зависимости от и и положительные, и отрицательные значения, то в точке экстремума нет;

в) если может обращаться в нуль не только при нулевых приращениях и , то вопрос об экстремуме остается открытым.

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

Найдем значения частных производных второго порядка в стационарной точке :

Обозначим через определитель, составленный из

(6.8)

Тогда достаточные условия экстремума функции двух переменных имеют вид:

а) если >0 и a11<0 (a22<0), то в точке функция имеет максимум; если >0 и a11>0 (a22>0), то в точке функция имеет минимум;

б) если <0, то экстремума нет;

в) если , то вопрос об экстремуме остается открытым.

Если область Ф замкнута и ограничена, то дифференцируемая функция достигает в этой области своих наибольшего и наименьшего значений или в стационарной точке, или в граничной точке области.

Таким образом, чтобы найти наибольшее (наименьшее) значение функции в области Ф, нужно:

найти все стационарные точки внутри области Ф и вычислить значения функции в них:

исследовать функцию на экстремум на границе области Ф;

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

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

Условный экстремум. Пусть необходимо найти экстремум функции при условии, что переменные удовлетворяют уравнениям:

)=0, (6.9)

Предполагается, что функции и имеют непрерывные частные производные по всем переменным. Уравнения (6.9) называются уравнениями связи.

Говорят, что в точке , удовлетворяющей уравнениям связи (6.9), функция имеет условный максимум (минимум), если неравенство имеет место для всех точек , координаты которых удовлетворяют уравнениям связи.

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

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

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

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

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

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

4.4 Метод множителей Лагранжа

Среди задач (4.1)-(4.3) особое место занимают задачи типа

(6.10)

, (6.11)

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

Можно указать следующий порядок решения задачи (6.10)-(6.11) методом множителей Лагранжа:

составить функцию Лагранжа:

L (6.12)

здесь - множители Лагранжа;

2)Найти частные производные функции Лагранжа по всем переменным и приравнять их нулю. Тем самым получим систему:

(6.13)

Эта система состоит из m + n уравнений. Решить эту систему (если это окажется возможным) и найти таким образом все стационарные точки функции Лагранжа;

из стационарных точек, взятых без координат выбрать точки, в которых функция f(имеет условные локальные экстремумы при наличии ограничений (6.11). Этот выбор осуществляется, например, с применением достаточных условий локального экстремума. Часто исследование упрощается, если использовать конкретные условия задачи.

В основе метода Лагранжа решения классической задачи оптимизации (6.10)-(6.11) лежит утверждение, что если в точке имеет экстремум, то существует такой вектор , что точка

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

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

Пример 6.4. По плану производства продукции предприятию необходимо изготовить 200 изделий. Эти изделия могут быть изготовлены двумя технологическими способами. Производственные затраты на изготовление n изделий первым способом равны 4n+n2, а для второго способа - 8n+n2. Сколько изделий надо изготовить каждым способом, чтобы общие затраты на производство продукции были бы минимальными.

Решение.

Обозначим число изделий, изготовленных первым способом через х1, вторым способом - х2. Тогда суммарные затраты на изготовление продукции по плану составят:

f (x1,x2)=4x1+x12+8x2+x22

При этом общее число изделий должно быть равно 200, т.е.

x1+x2=200

Получим математическую модель задачи:

f(x1,x2)=4x1+x12+8x2+x22

x1+x2=200

x1x2

Для ее расчета применим метод множителей Лагранжа.

Составим функцию Лагранжа

L(x1,x2,)=4x1+x12+8x2+x22+(200-x1-x2)

Найдем частные производные функции L по x1,x2, и приравняем их к нулю:



имеем систему:

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

Таким образом, по необходимому условию экстремума дифференцируемой функции получим стационарную точку М(101,99) возможного условного экстремума функции f(x1,x2).

Дальнейшее исследование этой точки будем проводить как и в случае безусловного экстремума.

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

Для рассматриваемого примера производные постоянны и не зависят от значений х1 и х2. Поэтому a11=2, a12=a21=0, a22=2 (см. 6.8). Вычислим определитель

Так как определитель больше нуля и a11=2>0, следовательно, в точке М(101,99) функция f(x1,x2) имеет минимум:

(ед.)

Ответ. При изготовлении 101 детали первым способом и 99 деталей вторым способом затраты на производство будут минимальными и равными 21198 денежным единицам.

Литература

Исследование операций в экономике. Под редакцией проф. Н.Ш. Кремера. М., «Банки и биржи», ЮНИТИ, 1997.

Хэмди А. Таха. Введение в исследование операций. Издательский дом «Вильямс»,М., С-П, Киев, 2001.

Акулич И.Л. Математическое программирование в примерах и задачах. М., 1986.

Эддоус М., Стэнфилд Р. Методы принятия решений. М., ЮНИТИ, 1997.

Банди Б. Основы линейного программирования. М., 1989.

Фомин Г.П. математические методы и модели в коммерческой деятельности. М., Финансы и статистика, 2001.

Вентцель Е.С. Исследование операций. М., Наука, 1980.

Контрольные вопросы

Цель и задачи исследования операций.

Модели и моделирование. Экономико-математические модели.

Математическое программирование. Модель задачи математического программирования.

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

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

Какое решение называется допустимым и какое оптимальным?

Приведите примеры экономических задач.

Симметричная форма записи. Как от общей ЗЛП перейти к симметричной задаче?

Запишите закрытую модель транспортной задачи.

Запишите открытую модель транспортной задачи.

Дайте определение цикла свободной клетки. Сколько циклов существует у одной свободной клетки?

Что называется оценкой свободной клетки?

В каком случае план можно улучшать и как это сделать?

Как свести открытую модель транспортной задачи к закрытой?

В каком случае план транспортной задачи считается вырожденным? Как с этим бороться?

Как можно построить начальное опорное решение транспортной задачи?

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

Приведите примеры экономических задач, сводящихся к транспортным моделям.

Как решаются транспортные задачи, имеющие некоторые усложнения в постановке?

Контрольная работа по экономико - математическим методам

ТАБЛИЦА

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

Последняя цифра номера зачетной книжки

1 2 3 4 5 6 7 8 9 0

11 12 13 14 15 16 17 18 19 20

1 36 37 38 39 40 21 22 23 24 25

60 41 42 43 44 45 46 47 48 49

П

р 01 02 03 04 05 06 07 08 09 10

е 2 26 27 28 29 30 31 32 33 34 35

д 50 51 52 53 54 55 56 57 58 59

п

о 01 02 03 04 05 06 07 08 09 10

с 3 27 28 29 30 31 32 33 34 35 36

л 52 53 54 55 56 57 58 59 60 41

е

д 11 12 13 14 15 16 17 18 19 20

н 4 37 38 39 40 21 22 23 24 25 26

я 42 43 44 45 46 47 48 49 50 51

я

01 02 03 04 05 06 07 08 09 10

5 28 29 30 31 32 33 34 35 36 37

54 55 56 57 58 59 60 41 42 43

11 12 13 14 15 16 17 18 19 20

ц 6 38 39 40 21 22 23 24 25 26 27

и 44 45 46 47 48 49 50 51 52 53

ф

р 01 02 03 04 05 06 07 08 09 10

а 7 23 24 25 26 27 28 29 30 31 32

45 46 47 48 49 50 51 52 53 54

11 12 13 14 15 16 17 18 19 20

8 25 26 27 28 29 30 31 32 33 34

60 41 42 43 44 45 46 47 48 49

01 02 03 04 05 06 07 08 09 10

9 35 36 37 38 39 40 21 22 23 24

50 51 52 53 54 55 56 57 58 59

11 12 13 14 15 16 17 18 19 20

0 26 27 28 29 30 31 32 33 34 35

42 43 44 45 46 47 48 49 50 51

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

Например, для студента, имеющего зачетную книжку с номером 87128, на пересечении горизонтальной колонки 2 и столбца 8 таблицы указаны следующие номера задач его индивидуального задания контрольной работы: 08, 33, 57.

Задачи контрольной работы

Задачи 01 - 10

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

Значения параметров a, b, c приведены в таблице 1.

Задачи 11 - 20

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

Значения параметров a, b, c приведены в таблице 1.

Табл. 1

№№ задач	a	b	c	№№ задач	a	b	c
01	1	5	9	11	2	4	2
02	5/4	4	6	12	4	2	3
03	1/2	7	8	13	3/2	3	3
04	7/4	8	7	14	5/2	2	4
05	7/2	6	9	15	5/2	3	4
06	1/2	7	6	16	7/2	3	2
07	2/3	8	8	17	4	2	2
08	5/2	4	7	18	7/2	4	4
09	3/4	5	8	19	3/2	4	5
10	2	6	7	20	2	4	3

Задачи № 21 - 40

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

Табл. 2

Потребители Поставщики	b1	b2	b3
a1	c11	c12	c13
a2	c21	c22	c23
a3	c31	c32	c33

Задача 21 Задача 22 Задача 23

Bj Ai	90	25	85		Bj Ai	45	50	105		Bj Ai	60	90	50
50	5	9	3		30	3	7	1		30	4	3	5
45	6	1	2		80	7	1	2		70	7	8	8
105	5	4	7		90	3	4	1		100	3	1	2

Задача 24 Задача 25 Задача 26

Bj Ai	45	105	50		Bj Ai	100	30	70		Bj Ai	80	90	30
25	4	8	2		110	1	2	3		105	8	4	1
85	7	1	2		40	8	5	4		45	2	1	7
90	4	3	6		50	3	1	6		50	4	1	3

Задача 27 Задача 28 Задача 29

Bj Ai	35	60	15		Bj Ai	50	110	40		Bj Ai	40	60	40
40	3	5	7		30	3	2	1		45	1	4	5
30	8	1	3		70	4	5	8		65	3	4	9
40	1	5	8		100	6	1	3		30	2	1	8

Задача 30 Задача 31 Задача 32

Bj Ai	30	45	65		Bj Ai	35	75	90		Bj Ai	95	80	25
40	9	4	1		25	7	2	4		90	2	7	4
40	1	5	2		95	2	1	5		35	1	2	5
60	2	8	8		80	1	8	3		75	8	1	3

Задача 33 Задача 34 Задача 35

Bj Ai	100	10	90		Bj Ai	70	50	70		Bj Ai	70	80	50
50	4	3	7		60	4	3	1		100	6	1	1
70	1	1	5		40	2	1	4		90	3	1	8
80	1	8	3		90	2	4	8		10	4	5	3

Задача 36 Задача 37 Задача 38

Bj Ai	60	90	40		Bj Ai	40	30	40		Bj Ai	35	15	60
50	3	4	1		35	4	5	8		40	4	5	8
70	4	1	3		15	8	1	3		40	8	1	3
70	2	2	4		60	2	6	7		30	2	6	7

Задача 39 Задача 40

Bj Ai	100	160	70		Bj Ai	80	140	110
80	6	2	5		100	4	3	5
110	8	1	3		160	10	1	2
140	3	10	4		70	3	8	6

Задачи № 41 - 60

По плану производства продукции предприятию необходимо изготовить d изделий. Эти изделия могут быть изготовлены двумя технологическими способами. Производственные затраты на изготовление n изделий первым способом равны , а для второго способа - . Сколько изделий надо изготовить каждым способом, чтобы общие затраты на производство продукции были бы минимальными? Исходные данные приведены в таблице 3.

Табл. 3

№№ задач	a	b	d		№№ задач	a	b	d
41	2	10	100		51	13	9	122
42	12	4	98		52	2	14	118
43	3	11	102		53	5	1	80
44	6	2	110		54	7	3	82
45	3	7	108		55	9	5	78
46	13	5	112		56	14	2	150
47	9	1	90		57	15	3	152
48	2	10	92		58	4	16	148
49	11	7	88		59	5	13	140
50	8	12	120		60	17	5	142

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