математика

ДОНБАСЬКА ДЕРЖАВНА АКАДЕМІЯ

БУДІВНИЦТВА Й АРХІТЕКТУРИ

КАФЕДРА ВИЩОЇ МАТЕМАТИКИ Й ЕКОНОМЕТРІЇ

КОНСПЕКТ ЛЕКЦІЙ

З ВИЩОЇ МАТЕМАТИКИ

РОЗДІЛ «ДОСЛІДЖЕННЯ ОПЕРАЦІЙ»

ДЛЯ СТУДЕНТІВ ЕКОНОМІЧНИХ СПЕЦІАЛЬНОСТЕЙ ДЕННОГО І ЗАОЧНОГО ВІДДІЛЕНЬ

№ кода 7.050.201 7.050.107

Затверджено на засіданні кафедри “Вища математика” ПРОТОКОЛ №1 від 28.08.2003 р. Зав. каф. Левін В.М.

доцент Савенко С.М. доцент Шурко Г.К.

М. Макіївка

2003р.

2

ЗМ І С Т

1.Предмет і задачі дослідження операцій ________________________3

2.Постановка задачі лінійного програмування____________________3

3.Двоїсті задачі______________________________________________7

4.Транспортна задача_________________________________________9

5.Метод динамічного програмування___________________________13

3

1. Предмет і задачі дослідження операцій

Під терміном «дослідження операцій» розуміється застосування математичних методів для обґрунтування прийняття рішень. Ухвалення рішення зв'язане з вибором з безлічі рішень, що допускаються обставинами справи, деякого одного визначеного рішення. Процес ухвалення рішення може бути описаний функцією, аргументами якої є варіанти рішення. Ця функція називається цільовий. Задача ухвалення рішення зводиться до перебування чи максимуму мінімуму значення цільової функції , про також перебування такого конкретного рішення - аргументу , на якому це рішення досягається. Також рішення називається оптимальним.

Основні класи розгляду задач:

1.Задача керування запасами.

2.Задача розподілу ресурсів.

3.Задача ремонту і заміни устаткування.

4.Задача масового обслуговування.

5.Задача вибору маршруту.

2. Постановка задачі лінійного програмування

Більшість задач розв'язуваних методами дослідження операцій може бути сформульоване в такий спосіб. Потрібно знайти

Si , затрачуваного на виготовлення одиниці продукції Pj (числа ai j часто

4

називають технологічними коефіцієнтами), cj прибуток від реалізації продукції Pj .

Тоді економико - математична модель задачі про використання ресурсів у загальній постановці прийме вид: знайти такий план X (x1,x2,...,xn) випуску продукції, що задовольняє системі

a11x1 a12x2 ... a1nxn b1

a21x1 a22x2 ... a2nxn b2

... ...

am1x1 am2x2 ... amnxn bm

до умови x1 0,x2 0,...,xn 0 при який функція

F c1x1 c2x2 ... cnxn

приймає максимальне рішення.

Приклад. Для виготовлення двох видів продукції P1 і P2 використовують чотири види ресурсів S1,S2,S3,S4. Запаси ресурсів, число одиниць ресурсів, затрачуваних на виготовлення одиниці продукції, приведені в таблиці.

Прибуток, одержуваний від одиниці продукції P1 і P2 складає відповідно 2 і 3 грн. Необхідно скласти такий план виробництва продукції, при якому прибуток від її реалізація буде максимальною.

Рішення.

Складемо економіко-математичну модель задачі.

Позначимо x1, x2 - число одиниць продукції відповідно видів P1 і P2. Для їхнього виготовлення буде потрібно 1x1 3x2 ресурсу S1,

2x1 1x2 ресурсу S2 , 1x2 ресурсу S3, 3x1 ресурсу S4 . Тому що споживання ресурсів не може бути більш їхніх запасів, то можна записати

5

x1 3x2 18, I

2x1 x2 16, II

x2 5, III3x1 21, IV

За змістом перемінні x1,x2 0, (V, VI).

Сумарний прибуток F складе 2x1 грн. від продукції P1 і 3x2 від

продукції P2, тобто F 2x1 3x2 .

Економіко-математична модель: знайти такий план випуску продукції X (x1,x2), що задовольняє системі нерівності, при якому функція F досягає максимального значення.

Вирішимо задачу геометрично. Зобразимо багатокутник рішень:

початок координат (будувати її не обов'язково). Задамо, наприклад, F=6 і побудуємо лінію рівня 2x1 3x2 6. Її розташування вкаже на напрямок зростання лінійної функції (вектор q). Тому що розглянута задача – на відшукання максимуму, то оптимальне рішення – у кутовій крапці З, що знаходиться на перетинанні прямих I і II, тобто координати крапки З визначаються рішенням системи рівнянь:

x1 3x2 18,

2x1 x2 16,

відкіля

x1 6, x2 4 , тобто З(6;4).

Максимальне значення лінійної функції дорівнює

Fmax 2 6 3 4 24 .

тобто максимальний прибуток у 24 грн. може бути досягнута при виробництві 6 одиниць продукції P1 і 4 одиниць продукції P2.

6

Задача складання раціону (задача про дієту, задача про суміші ).

Приклад: мається два види корму I u II , що містять живильні речовини (вітаміни) S1,S2 ,иS3.Зміст числа одиниць живильних речовин у

1 кг. кожного виду і необхідний мінімум живильних речовин приведені в таблиці.

Вартість 1 кг. корму I u II відповідно рівні 4 і 3 грн.

Необхідно зберегти денний раціон , що має мінімальну вартість, у якому зміст кожного виду живильних речовин було не менш установленої межі.

Рішення: Складемо економіко-математичну модель задачі, позначимо x1,x2 кількість корму I u II вхідного в денний раціон. Тоді цей раціон

містить 3x1 x2 S одиниць речовини S1 , x1 2x2 речовини S2, x1 6x2 речовини S3.

Одержимо систему нерівності

Загальна вартість раціону складе (у грн.)

F 4x1 6x2.

Экономико - математична модель: скласти денний раціон X (x1,x2), що задовольняє системі нерівності, при якому цільова функція F приймає мінімальне значення.

7

3. Двоїсті задачі

Розглянемо двох задач Задача I (вихідна)

F c1x1 c2x2 ... cnxn max

при обмеженнях

a11x1 a12x2 ... a1nxn b1

a21x1 a22x2 ... a2nxn b2

... ...

am1x1 am2x2 ... amnxn bm

і умова не заперечності

x1 0, x2 0, ... , xn 0.

Економіко-математична модель: скласти такий план випуску продукції X x1,x2,...,xn при який прибуток (виторг) від реалізації продукції буде максимальної за умови, що споживання ресурсів по кожнім виді продукції не перевершить наявних запасів.

Задача II (двоїста )

b1y1 b2 y2 ... bm ym min

при обмеженнях

a11y1 a12 y2 ... a1m ym c1

a21y1 a22 y2 ... a2m ym c2

... ...

a1n y1 a2n y2 ... amn ym cn

і умовах не заперечності

y1 0,y2 0,...,ym 0

Економіко-математичний зміст : знайти такий набір цін (оцінок) ресурсів y y1, y2,...,ym при який загальні витрати на ресурси будуть мінімальними за умови, що витрати на ресурси при виробництві кожного виду продукції будуть не менш прибутку ( виторгу) від реалізації цієї продукції.

Обидві задачі мають наступні властивості:

1.в одна задача шукають максимум лінійної функції інший мінімум. 2. Коефіцієнти при перемінних у лінійній функції однієї задачі є

вільними членима системи обмежень в іншій. 3.У першої задачі « », в інший « ».

4. Матриці коефіцієнтів при перемінних у системах обмежень обох задач є транспонованими друг до друга:

8

Дві задачі I і II лінійного програмування, що володіють зазначеними властивостями, називаються симетричними взаємно двоїстими задачами.

Приклад 1. Скласти задачу двоїсту наступної

Рішення. Тому що вихідна задача на максимізацію, то приведемо всі нерівності системи обмежень до виду « », для чого обидві частини першої і четвертої нерівності помножимо на -1.

2x1 x2 1

x1 4x2 24x1 x2 3

x1 x2 5

Знайдемо матрицю 1, транспоновану до

10

n

xij ai,i 1,...,n

j 1

m

xij bj , j 1,...,m, xij 0.

i1

План перевезень записується у виді матриці

План, минимизирующий сумарні транспортні витрати,

називається оптимальним чи рішенням транспортної задачі.

Сукупність величин cij записується у виді матриці

Такаючи матриці називається матрицею транспортних витрат.

Теорема. Для можливості розв'язання транспортної задачі необхідно і досить, щоб виконувалася умова балансу:

m n

ai bj,

i 1 j 1

т.е. щоб сумарний обсяг виробництва був дорівнює сумарному обсягу споживання.

Відзначимо, що кількість xij 0 повинна бути рівним n m 1.

Рішення транспортної задачі починається з перебування первісного базисного розподілу постачань. Базисний розподіл виробляється методом північно-західного чи кута методом мінімального елемента. Розглянемо на прикладі ці методи.

Отже, дано: