Скачать

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

Министерство общего и профессионального образования

Российской Федерации

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ

ИНСТИТУТ ЗАОЧНОГО ОБУЧЕНИЯ

Контрольная работа

по дисциплине «Прикладная математика»

Специальность Бухгалтерский учет и аудит

Курс 2-й

Группа БуиА-6-99/2

Студент

Студенческий билет №

ВАРИАНТ №25

« » мая 2001г.

Проверил:

____________________/ /

«___»_______________2001г.

Москва 2001г.

Задача №1. Линейная производственная задача.

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

4 0 8 7 316

А= 3 2 5 1 В= 216 С=(31, 10, 41, 29)

5 6 3 2 199

Найти производственную программу (х1, х2, х3, х4), максимизирующую прибыль

z=31х₁+10х₂+41х₃+29х₄

Затраты ресурсов 1-го вида на производственную программу

4х₁+0х₂+8х₃+7х₄≤316

Затраты ресурсов 2-го вида на производственную программу

3х₁+2х₂+5х₃+х₄≤216

Затраты ресурсов 3-го вида на производственную программу

5х₁+6х₂+3х₃+2х₄≤199

Имеем

4х₁+0х₂+8х₃+7х₄≤316

3х₁+2х₂+5х₃+х₄≤216 (1)

5х₁+6х₂+3х₃+2х₄≤199

где по смыслу задачи

х₁≥0, х₂≥0, х₃≥0, х₄≥0. (2)

Получена задача на нахождение условного экстремума. Для ее решения систему неравенств (1) при помощи дополнительных неизвестных х5, х6, х7 заменим системой линейных алгебраических уравнений

4х₁+0х₂+8х₃+7х₄+х₅=316 (I)

3х₁+2х₂+5х₃+ х₄+х₆=216 (II) (3)

5х₁+6х₂+3х₃+2х₄+х₇₌199 (III)

где дополнительные переменные имеют смысл остатков соответствующих ресурсов, а именно

х₅ – остаток сырья 1-го вида,

х₆ – остаток сырья 2-го вида,

х₇ – остаток сырья 3-го вида.

Среди всех решений системы уравнений (3), удовлетворяющих условию неотрицательности

х₁≥0, х₂≥0, х₃≥0, х₄≥0, х₅≥0, х₆≥0, х₇≥0 (4)

надо найти то решение, при котором функция

z=31х₁+10х₂+41х₃+29х₄

будет иметь наибольшее значение

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

Из функции z(x) видно, что наиболее выгодно начать производство с 3-го ресурса.

Найдем ведущее уравнение:

b_i 316 216 199 316

min ------- = ----- ----- ----- = -----

a_i3>0 8 5 3 8

Примем I-е уравнение за ведущее. Решаем симплекс методом:

Оптимальная производственная программа:

х₁=23, х₂=0, х₃=28, х₄=0

Остатки ресурсов:

Первого вида – х₅=0;

Второго вида – х₆=7;

Третьего вида – х₇=0

Максимальная прибыль z_max=1861

Обращенный базис Q^-1

10/56 0 -1/7

Q^-1= -4/7 1 -1/7

-6/56 0 2/7

х₅х₆х₇

Базис Q

8 0 4

Q= 5 1 3

3 0 5

х₃ х₆ х₁

Самопроверка.

10/56•8+0•5-1/7•3 10/56•0+0•1-1/7•0 10/56•4+0•3-1/7•5 1 0 0

Q^-1 •Q= -4/7•8+1•5-1/7•3 -4/7•0+1•1-1/7•0 -4/7•4+1•3-1/7•5 = 0 1 0

-6/56•8+0•5+2/7•3 -6/56•0+0•1+2/7•0 -6/56•4+0•3+2/7•5 0 0 1

10/56•316+0•216-1/7•199 28

Q^-1 •B= -4/7•316+1•216-1/7•199 = 7

-6/56•316+0•216+2/7•199 23

Задача №2. Двойственная задача.

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

у₂ за каждую единицу 2-го ресурса

у₃ за каждую единицу 3-го ресурса.

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

4 0 8 7 316

А= 3 2 5 1 В= 216 С=(31, 10, 41, 29)

5 6 3 2 199

для производства единицы продукции 1-го вида мы должны затратить, как видно из матрицы А 4 единицы ресурса 1-го вида, 3 единицы ресурса 2-го вида, 5 единиц ресурса 3-го вида.

В ценах у₁, у₂, у₃ наши затраты составят

4у₁+3у₂+5у₃≥31

Аналогично, во 2-м столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции 2-го вида

2у₂+6у₃≥10

Аналогично, в 3-м столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции 3-го вида

8у₁+5у₂+3у₃≥41

Аналогично, в 4-м столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции 4-го вида

7у₁+у₂+2у₃≥29

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

316у₁+216у₂+199у₃

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

У=(у₁, у₂, у₃)

Минимизирующий общую оценку всех ресурсов

f=316у₁+216у₂+199у₃

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

4у₁+3у₂+5у₃≥31

2у₂+6у₃≥10

8у₁+5у₂+3у₃≥41

7у₁+у₂+2у₃≥29

При этом оценки ресурсов не могут быть отрицательными

у₁≥0, у₂≥0, у₃≥0

На основании 2-й основной теоремы двойственности

Х=(х₁, х₂, х₃, х₄) и у=(у₁, у₂, у₃)

Необходимо и достаточно выполнения условий

х₁(4у₁+3у₂+5у₃-31)=0

х₂(2у₂+6у₃-10)=0

х₃(8у₁+5у₂+3у₃-41)=0

х₄(7у₁+у₂+2у₃-29)=0

Учитывая, что в решении исходной задачи х₁>0, x₃>0

Поэтому

4у₁+3у₂+5у₃-31=0

8у₁+5у₂+3у₃-41=0

Учтем, что 2-й ресурс был избыточным и, согласно теореме двойственности, его двойственная оценка равна нулю у₂=0

Имеем систему уравнений

4у₁+3у₂+5у₃-31=0

8у₁+5у₂+3у₃-41=0

Решим систему:

4у₁+5у₃=31

у₁=(31-5у₃)/4

8((31-5у₃)/4)+3у₃=41

-7у₃=-21

у₁=(31-15)/4

откуда следует

у₁=4, у₃=3

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

у₁=4, у₂=0, у₃=3

Общая оценка всех ресурсов

f=316у₁+216у₂+199у₃

f=1264+0+597=1861

Задача №2.1. Задача о «расшивке узких мест производства».

При выполнении оптимальной производственной программы 1-й и 3-й ресурсы используются полностью, образуя «узкие места производства». Их необходимо заказать дополнительно.

Пусть Т=(t₁, 0, t₃) – вектор дополнительных объемов ресурсов.

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

Н+ Q^-1Т≥0

Необходимо найти вектор

Т=(t₁, 0, t₃)

максимизирующий суммарный прирост прибыли

w=4t₁+3t₃

28 10/56 0 -1/7 t₁ 0

7 + -4/7 1 -1/7 · 0 ≥ 0

23 -6/56 0 2/7 t₃ 0

Предполагаем, что дополнительно можно получить не более 1/3 первоначального объема ресурса каждого вида

t₁ 316

0 ≤ 1/3 216

t₃ 199

где t₁≥0, t₃≥0

10/56t₁-1/7t₃≥-28

-4/7t₁-1/7t₃≥-7

-6/56t₁+2/7t₃≥-23

-10/56t₁+1/7t₃≤28

4/7t₁+1/7t₃≤7

6/56t₁-2/7t₃≤23

t₁≤316/3, t₃≤199/3

t₁≥0, t₃≥0

Программа расшивки имеет вид

t₁=0, t₂=0, t₃=49

и прирост прибыли составляет

w=4t₁+3t₃=3∙49=147

Сводка результатов приведена в таблице:

Задача №3. Транспортная задача линейного программирования.

Исходные данные:

31 40 41 49

45 4 5 8 6

60 3 2 5 1

65 5 6 3 2

Общий объем производства ∑аi=45+60+65=170 единиц продукции.

Потребителям требуется ∑bi=31+40+41+49=161 единиц продукции.

Так как продукции производится больше на 9 единиц, чем требуется потребителям, то мы имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом 9 единиц. Для нахождения первого базисного допустимого решения используем правило «северо-западного угла».

Θ=9 z(x₁)=31·4+14·5+26·2+34·5+7·3+49·2+9·0=535

Θ=25 z(x₂)=31·4+5·5+35·2+25·5+16·3+49·2+9·0=490

z(x₃)=31·4+5·5+35·2+25·1+41·3+24·2+9·0=415

Задача №4. Динамическое программирование. Распределение капитальных вложений.

Исходные данные:

Для решения используем метод «северо-восточной диагонали».

x₄^*=x₄(700)=0

x₃^*=x₃(700-x₄^*)=x₃(700)=200

x₂^*=x₂(700-x₄^*-x₃^*)=x₂(700-200)=x₂(500)=300

x₁^*=700-x₄^*-x₃^*-x₂^*=700-0-200-300=200

x₁=200

x₂=300

x₃=200

x₄=0

Задача №5. Задача формирования оптимального портфеля ценных бумаг.

Исходные данные: