Задачи по ЭММиМ - файл n1.doc

приобрести
Задачи по ЭММиМ
скачать (88 kb.)
Доступные файлы (1):
n1.doc379kb.20.09.2005 15:38скачать

n1.doc

Задание 1 (07)

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

Требуется:

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

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

Решение:

Пусть х1 - средства (млн. у.е.), размещенные в кредитах; х2 - средства, вложенные в ценные бумаги; Z - общая прибыль банка.

Целевая функция Z, которую требуется максимизировать, принимает вид:



Согласно условию задачи, имеем следующую систему ограничений:



Таким образом получили математическую модель задачи:



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

Для этого строим граничные прямые, соответствующие данным ограничениям-неравенствам.



Строим данные прямые:



Т.о. получили область допустимых решений - множество точек треугольника АВС.

Находим вершины треугольника и значения целевой функции Z в этих точках.

1)

2)

3)

Сравнивая полученные значения целевой функции, получаем, что максимальная прибыль в 21,984 млн. у.е. достигается при размещении 86,4 млн. у.е. в кредитах и 33,6 млн. у.е в ценных бумагах.

Ответ:

Задание 2 (27).

На предприятии имеется возможность выпускать 3 вида продукции Пj (). При ее изготовлении используются ресурсы Рi (). Размеры допустимых затрат ресурсов ограничены соответственно величинами b1, b2, b3. Расход ресурса i-го вида на единицу продукции j-го вида составляет ij)единиц. Цена единицы продукции j-го вида равна сj ден. ед. Требуется:

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

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

  3. Сформулировать в экономических терминах двойственную задачу и составить ее математическую модель.

  4. Используя решение исходной задачи и соответствие между переменным. Найти компоненты оптимального плана двойственной задачидвойственные оценки yi*.

Решение:

Оформим все исходные данные в идее таблицы.

Ресурсы

Выпускаемая продукция

Объем ресурсов

П1

П2

П3

Р1

2

1

0

500

Р2

0

2

1

550

Р3

0

1

0

200

Цена реализации

3

4

1




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

Переменные х1; х2; х3 должны удовлетворять ограничениям, накладываемым на расход имеющихся в расположении предприятия ресурсов. Так, затраты ресурса Р1 на выполнение плана (х1; х2; х3) составят ед., где - затраты ресурса Р1 на выпуск х1 ед. продукции П1; - затраты ресурса Р1 на выпуск х2 ед. продукции П2; затраты ресурса Р1 на выпуск х3 ед. продукции П3 равны нулю. Очевидно, что указанная сумма не может превышать имеющийся запас Р1 в 500 ед., т.е. должно выполняться ограничение:



Аналогично получаем ограничения по расходу ресурсов Р2 и Р3.



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

(1)

Запишем систему (1) в канонической форме:

(2)

Задачу решаем симплексным методом:

Для этого запишем условие системы (2) в симплексную таблицу 1:

таблица 1




























симплексное отношение

БП

СБ

А0

х1

х2

х3

х4

х5

х6

 

3

4

1

0

0

0

 

х4

0

500

2

1

0

1

0

0

500

х5

0

550

0

2

1

0

1

0

275

х6

0

200

0

1

0

0

0

1

200

Z

0

-3

-4

-1

0

0

0

 

План не оптимален, так как в Z-строке есть отрицательные элементы. Наибольший из них по абсолютной величине -4 – соответствует столбцу переменной х2. Этот столбец назначим разрешающим. Для определения разрешающей строки находим минимальное симплексное отношение:



Оно соответствует 3-ей строке, которая и будет разрешающей. На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент: 1

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

таблица 2




























симплексное отношение

БП

СБ

А0

х1

х2

х3

х4

х5

х6




3

4

1

0

0

0




х4

0

300

2

0

0

1

0

-1

150

х5

0

150

0

0

1

0

1

-2




х2

4

200

0

1

0

0

0

1




Z

800

-3

0

-1

0

0

4




В Z-строке еще есть отрицательные элементы. Наибольший из них по абсолютной величине -3 – соответствует столбцу переменной х1. Этот столбец назначим разрешающим. Для определения разрешающей строки можно найти минимальное симплексное отношение, но мы заметим, что ненулевое значение в первом столбце соответствует лишь первой строке. Значит она и будет разрешающей.

На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент: 2.

В базис вводим переменную х1, а выводим х4. Далее проводя аналогичные преобразования, получаем таблицу 3.

таблица 3




























симплексное отношение

БП

СБ

А0

х1

х2

х3

х4

х5

х6




3

4

1

0

0

0




х1

3

150

1

0

0

1/2

0

- 1/2




х5

0

150

0

0

1

0

1

-2

150

х2

4

200

0

1

0

0

0

1




Z

1250

0

0

-1

1,5

0

2,5




В Z-строке еще есть отрицательный элемент -1 – соответствует столбцу переменной х3. Его назначим разрешающим. Аналогично, заметим, что ненулевое значение в третьем столбце соответствует лишь второй строке. Значит она и будет разрешающей.

На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент: 1.

В базис вводим переменную х3, а выводим х5. Далее проводя аналогичные преобразования, получаем таблицу 4.



БП

СБ

А0

х1

х2

х3

х4

х5

х6

9

10

16

0

0

0

х1

3

150

1

0

0

0,5

0

-0,5

х3

1

150

0

0

1

0

1

-2

х2

4

200

0

1

0

0

0

1

Z

1400

0

0

0

1,5

1

0,5

Т.к. в в Z-строке отрицательных оценок нет, то полученный план:

Х*=(), Z*=z(x*)=1400 оптимален..

Основные переменные х1*=150; х2*=200; х3*=150 показывают, что продукцию П1 надо выпускать в объеме 150 единиц; П2 надо выпускать в объеме 200 единиц; продукцию П3 следует произвести 150 единиц. Дополнительные переменные х5*=0; х4*=0; х6*=0 показывают, что все ресурсы используются полностью и излишков нет.

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

(4)

Соответствие между переменными прямой и двойственной задачи имеет вид:

х1

y4

х2

y5

х3

y6

х4

y1

х5

y2

х6

y3

Учитывая это соответствие, выписываем из Z-строки таблицы 3 компоненты оптимального плана двойственной задачи:

Y*=(1,5; 1; 0,5; 0; 0; 0), f*=f(y*)=1400.

Двойственные переменные показывают меру дефицитности ресурсов, они численно равны изменению целевой функции при изменении соответствующего ресурса на единицу. Следовательно, увеличение 2-го ресурса на единицу ведет к увеличению объема реализации на y*2=1; 1-го – на y*1=1,5; 3-го на y*3=0,5. И так как y*1>y*2>y*3, то 1-ый ресурс более дефицитен, чем остальные. Избыточных ресурсов нет.

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

Раскроем состав двойственных переменных, исходя из полученных данных (во втором столбце) таблицы 4:



Экономически, например, для y*1=1,5, это означает следующее: при увеличении 1-го ресурса на единицу выпуск продукции 1-го вида увеличится на 0,5. Следовательно, значение целевой функции изменится на



Для y*2=1, это означает следующее: при увеличении 2-го ресурса на единицу выпуск продукции 2-го вида увеличится на 1. Следовательно, значение целевой функции изменится на



Для y*3=0,5, это означает следующее: при увеличении 3-го ресурса на единицу выпуск продукции 1-го вида уменьшится на 0,5; выпуск продукции 2-го вида увеличится на 1; выпуск продукции 3-го вида сократится на 2. Следовательно, значение целевой функции изменится на



Таким образом, управление дефицитными ресурсами позволяет варьировать выпуск рентабельной продукции, при этом увеличивая прибыль предприятия.
Ответ: Предприятию надо производить продукцию П1 в объеме 150 единиц; П2 в объеме 200 единиц; продукцию П3 - 150 единиц. При этом прибыль будет максимальна и составит 1400 ден. ед.

Задание 3 (47).

В пунктах Аi () производится однородная продукция в количествах аi ед. Себестоимость единицы продукции в i-ом пункте равна сi. Готовая продукция поставляется в пункты Вj (), потребности которых составляют вj ед. Стоимости сij перевозки единицы продукции из пункта Аi в пункт Вj заданы матрицей ij]3х4.

Требуется:

  1. составить экономико-математическую модель задачи, позволяющую найти план перевозки готовой продукции из пункта Аi в пункт Вj потребления при полном удовлетворении спроса на продукцию в этих пунктах, обеспечивающего минимальные суммарные затраты, вызванные производством и доставкой продукции;

  2. найти оптимальный план перевозки продукции при дополнительном условии, что продукция пункта А1 в котором себестоимость ее производства наименьшая, должна быть распределена полностью;

  3. вычислить величину fmin минимальных суммарных затрат на производство и доставку продукции;

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

Решение:

Оформим все исходные данные в виде таблицы

таблица 1

поставщики

потребители

запасы груза

себестоимость

В1

В2

В3

В4

А1

7

4

9

6

180

2

А2

5

10

8

6

220

4

А3

6

4

3

1

260

5

потребность в грузе

240

120

60

1
580
60

660





Заметим, что запасы груза превышают потребность в нем на 660-580=80 единиц. Имеем задачу открытого типа. Введем в рассмотрение «фиктивного потребителя» с нулевыми транспортными затратами, и с потребностью в 80 единицах груза. Причем учитываем, что суммарные затраты = затраты на перевозку + себестоимость продукции. Таким образом, получаем следующую таблицу:


 

В1

В2

В3

В4

ФП




 

240

120

60

160

80




А1

9

6

11

8

0

u1

180
















А2

9

14

12

10

0

u2

220
















А3

11

9

8

6

0

u3

260
















 

v1

v2

v3

v4

v5





Обозначим через хij (, ) количество единиц продукции (поставку), которое планируется к перевозке из пункта Аi производства в пункт Вj; потребления, через f - общие затраты, связанные с выпуском и доставкой всей продукции.

Целевую функцию задачи запишем в следующем виде:

(1)

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

(2)

В то же время спрос на продукцию в каждом пункте Bj потребления должен быть удовлетворен, т.е. сумма поставок xij, направляемых в каждый пункт Вj; потребления из всех пунктов Аi производства, должна равняться спросу на продукцию в этом пункте. Эти требования выразим следующими равенствами:

(3)

Если исключить обратные перевозки, то придется выполнить следующее условие:

хij?0

Соотношения (1)-(4) образуют экономико-математическую модель рассматриваемой задачи.

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

Чтобы учесть дополнительное требование, полного распределения продукции пункта A1 (в нем себестоимость продукции наименьшая), искусственно завысим показатель в клетке (1;5) до величины М?0. В таком случае доставка по маршруту А15 станет заведомо невыгодной, и в одном оптимальном плане пункт А1 будет связан с реальными производителями, т.е. его продукция будет практически распределена.

Заполним все данные в таблицу 2.

таблица 2

 

В1

В2

В3

В4

ФП




 

240

120

60

160

80




А1

9

6

11

8

М

u1

180

60

120

-

-

-

А2

9

14

12

10

0

u2

220

140

-

-

-

80

А3

11

9

8

6

0

u3

260

40

-

60

160

-

 

v1

v2

v3

v4

v5




Строим опорный план методом минимального элемента. Находим в таблице клетку с минимальными затратами – у нас это клетка, например (2;5) с нулевыми затратами – ее загружаем полностью поставкой . Столбец ФП закрыт. Далее в таблице находим клетку со следующими по величине затратами – это клетка (1;2). Ее загружаем поставкой . Столбец В2 закрыт полностью. Следующей загружаем клетку (3;4) поставкой . Столбец В4 закрыт полностью. Далее загружаем следующую по величине затрат клетку (3;3) поставкой . Столбец В3 закрыт полностью. Загружаем следующую по величине затрат клетку (2;1) поставкой . Строка А2 заполнена. Далее загружаем клетку (1;1) поставкой . Строка А1 заполнена и осталось заполнить клетку (3;1) поставкой .

У нас загружено m+n-1=4+4-1=7 клеток. Так что план невырожденный.

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



Пусть , тогда

.

Теперь определим оценки свободных клеток по формуле:

Таким образом, получаем:



План не оптимален так как, оценка . Улучшим наш план, загружая клетку (3;5) поставкой .

Таким образом получаем таблицу:

 

В1

В2

В3

В4

ФП




 

240

120

60

160

80




А1

9

6

11

8

М

u1

180

60

120

-

-

-

А2

9

14

12

10

0

u2

220

180

-

-

-

40

А3

11

9

8

6

0

u3

260

-

-

60

160

40

 

v1

v2

v3

v4

v5




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



Пусть , тогда

.

Теперь определим оценки свободных клеток по формуле:

Таким образом, получаем:



Так как все оценки положительны, то план, найденный в последней таблице, оптимальный. Таким образом:



Итак, по оптимальному плану из 180 единиц продукции, произведенных в пункте А1 производства, 60 попадут в пункт потребления В1, и 120 будет направлено в пункт потребления В2. При этом дополнительное требование, полного распределения продукции пункта A1 - выполнено.

Пункт производства А2 произведет 220 единиц продукции: 180 единиц направит в первый пункт потребления и 40 единиц останется нераспределенными, так как они приходятся на фиктивного потребителя.

Пункт производства А3 60 единиц произведенной продукции отправит в пункт В3 и 160 единиц продукции направит в В4 и также 40 единиц останется нераспределенными, так как они приходятся на фиктивного потребителя.

При этом затраты минимизируются и составят:

fmin=60·9+120·6+180·9+60·8+160·6=540+720+1620+480+960=4320 ден. ед.

Задание 4 (107)

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



Требуется:

1. Методом динамического программирования найти на сети самый короткий маршрут из пункта 1 в пункт 10;

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

Тариф

С12

С13

С14

С25

С27

С35

С36

С37

С45

С46

С47

С58

С59

С68

С69

С79

С810

С910




3

5

4

1

6

2

7

4

6

8

3

7

2

9

2

8

1

3

Сijстоимость перевозки единицы груза из пункта i в пункт j.

Решение:

Все множество вершин сети разобьем на подмножества. В первое подмножество включим вершину 1, во второе вершины, в которые входят дуги, выходящие из вершины 1. В третье – вершины, в которые входят дуги, выходящие из вершин второго подмножества и т.д. Таким образом получаем 5 подмножеств:

{1}, {2,3,4}, {5,6,7}, {8,9}, {10}.

Решение задачи разобьем на 4 этапа. На первом необходимо определить, через какой пункт, принадлежащий второму подмножеству, надо доставлять груз из пункту 1. На втором этапе надо определить, через какой пункт третьего подмножества везти груз из пункта, принадлежащего второму подмножеству и т.д.

Перенумеруем этапы от конечной вершины сети к начальной и введем обозначения:

n – номер шага ()

fn(S) – минимальные затраты на перевозку груза от пункта S до конечного пункта, если до пункта 10 осталось n шагов

jn(S) – номер города, через который нужно двигаться из пункта S, чтобы достичь fn(S)

Csj – стоимость перевозки из пункта S в пункт j.


n=4 n=3 n=2 n=1

Предположим, что груз доставлен в пункт 10, следовательно, число оставшихся шагов равно нулю (n=0) и fn(S)=f0(10)=0, так как из пункта 10 груз везти никуда не надо.

n=1

В пункт 10 груз может быть доставлен или из пункта 8 или пункту 9. Затраты на перевозку составят:

f1(8)=C8,10+f0(10)=1+0=1; S=8; j1(8)=10

f1(9)=C9,10+f0(10)=3+0=9; S=3; j1(9)=10.

Результаты занесем в таблицу:

таблица 1




10

f1(S)

j1(S)

8

1+0

1

10

9

3+0

3

10

n=2

В пункты 8 и 9 груз может быть доставлен или из пункта 5, или из пункта 6, или – 7.

f2(5)=min(C58+f1(8); C59+f1(9))=min(7+1;2+3)=min(8;5)=5; S=5; j2(5)=9

f2(6)=min(C68+f1(8); C69+f1(9))=min(9+1;2+3)=min(10;5)=5; S=6; j2(6)=9

f2(7)=C79+f1(9)=8+3=11; S=7; j2(7)=9

таблица 2




8

9

f2(S)

j2(S)

5

7+1

2+3

5

9

6

9+1

2+3

5

9

7

-

8+3

11

9


n=3

В пункты 5, 6 и 7 груз может быть доставлен или из пункта 4, или из пункта 3, или из 2.

f3(2)=min(C25+f2(5); C27+f2(7))=min(1+5;6+11)=min(6;17)=6; S=2; j3(2)=5

f3(3)=min(С35+f2(5); С36+f2(6); С37+f2(7))=min(2+5;7+5;4+11)=min(7;12;15)=7; S=3; j3(3)=5

f3(4)=min(С45+f2(5);С46+f2(6);С47+f2(7))=min(6+5;8+5;3+11)=min(11;13;14)=11; S=4; j3(4)=5.

таблица 3




5

6

7

f3(S)

j3(S)

2

1+5

-

6+11

6

5

3

2+5

7+5

4+11

7

5

4

6+5

8+5

3+11

11

5

n=4

В пункты 2, 3 и 4 груз может быть доставлен из пункта1.

f4(1)=min(С12+f3(2); С13+f3(3); С14+f3(4))=min(3+6;5+7;4+11)=min(9;12;15)=9; S=1; j4(1)=2

таблица 4




2

3

4

f4(S)

j4(S)

1

3+6

5+7

4+11

9

2

Из таблицы видно, что минимальные затраты на перевозку груза f4(1)=9 денежных единиц и оптимальный маршрут проходит через пункт 2, так как j4(1)=2. Далее из таблицы 3 при S=2 следует, что оптимальный маршрут проходит через п. 5, т.к. j3(2)=5. Далее для n=2 определяем, что оптимальный маршрут проходит через п. 9, т.к. j2(5)=9. И из пункта 9 груз доставляется в конечный пункт 10. Таким образом, двигаясь от последней таблицы к первой, мы определили оптимальный маршрут ?=(1-2-5-9-10) затраты на перевозку груза по нему составляют fmin=9 денежных единиц.

Оптимальный маршрут перевозки груза из всех остальных пунктов в пункт 10.

Пункт

Оптимальный маршрут

Минимальные затраты (ден. ед.)

9

9-10

3

8

8-10

1

7

7-9-10

11

6

6-9-10

5

5

5-9-10

5

4

4-5-9-10

11

3

3-5-9-10

7

2

2-5-9-10

6

1

1-2-5-9-10

9

Ответ: ?=(1-2-5-9-10); fmin=9 ден. ед.

Литература



  1. Акулич И.Л., Велесько Е.И., Ройш П., Стрельчонок В.Ф. Экономико-математические методы и модели. - Мн.: БГЭУ, 2003

  2. Красс М.С., Чупрынов Б.П. Математика для экономистов. – СПб.: Питер, 2004 г.

  3. Кузнецов А.В. и др. Высшая математика: Мат. программирование.:Учеб. пособие / А.В.Кузнецов, В.А. Сакович, Н.И.Холод, Л.С.Костевич; Под общ. ред. А.В.Кузнецова. – Мн., Выш. шк., - 2001.

  4. Кузнецов А.В. и др. Руководство к решению задач по математическому программированию: Учеб. пособие / А.В.Кузнецов, Н.И.Холод, Л.С.Костевич; Под общ. ред. А.В.Кузнецова. – 2-е изд., - Мн., Выш. шк., - 2001.

  5. Сборник задач и упражнений по высшей математике: Мат. программирование: Учеб. пособие / А.В.Кузнецов и др. – Мн., Выш. шк. – 2002.








Задание 1 (07)
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации