15

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

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

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

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

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

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

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

Курс 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₃) – вектор дополнительных объемов ресурсов.