Дата конвертації25.03.2017
Розмір50.97 Kb.
Типреферат

Скачати 50.97 Kb.

Завдання з теорії прийняття рішень

УНІВЕРСИТЕТ РОСІЙСЬКОЇ АКАДЕМІЇ ОСВІТИ

Факультет: Бізнес, Маркетинг, Комерція

Дисципліна: Теорія прийняття рішень

Тема контрольної роботи: [Завдання по четвертому варіанту]

П.І.Б. студента: Сприжков Ігор Максимович

Курс: 4. Семестр: 7. Номер залікової книжки: 1818.

Дата здачі: _____________________

П.І.Б. викладача: Асташкін С.В.

Оцінка: _________________________ Підпис: _________________________

Дата перевірки: __________________


завдання 1

Умова

Вирішити симплекс-методом задачу, попередньо привівши її до канонічного вигляду:

x 1 - x 2 - x 3 + 7x 4 → max

-x 1 + 2x 2 - x 3 + x 4 ≤ 2

2x 1 + x 2 + x 3 - 2x 4 ≤ 12

2x 1 + 3x 2 + 4x 3 + 2x 4 ≤ 6

x j ≥ 0, j = 1, 2, 3, 4

Рішення

Загальний вигляд задачі лінійного програмування в канонічної формі:

Σa ij = b i, i = 1, 2, ..., n

x j ≥ 0, j = 1, 2, ..., n, n + 1, n + m

Σp j x j → max

Економіко-математична модель даної задачі в канонічній формі матиме вигляд:

-1x 1 + 2x 2 - 1x 3 + 1x 4 + 1x 5 + 0x 6 + 0x 7 = 2

2x 1 + 1x 2 + 1x 3 - 2x 4 + 0x 5 + 1x 6 + 0x 7 = 12

2x 1 + 3x 2 + 4x 3 + 2x 4 + 0x 5 + 0x 6 + 1x 7 = 6

x j ≥ 0, j = 1, 2, ..., 7

x 1 - x 2 - x 3 + 7x 4 + 0x 5 + 0x 6 + 0x 7 → max

Тобто в ній лінійна форма максимізує, всі обмеження є рівностями, всі змінні задовольняють умові незаперечності.

Система рівнянь має бажаний вид: базисними змінними є змінні Х 5, Х 6, Х 7, праві частини невід'ємні. Початкове опорне рішення, що дає координати вихідної кутовий точки, має вигляд Х = (0, 0, 0, 0, 2, 12, 6) т.

Всі інші обчислення і дії зручно виробляє в табличній формі (табл. 1 - 3).

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

У перший рядок першої симплекс-таблиці занесені всі дані першого рівняння, в другу - другого і т.д.

У кожній з таблиць у другому стовпці (Б x) вказані базисні невідомі. Невідомі, які не входять в базис, дорівнюють нулю. Значення базисних невідомих записані в третьому стовпці (X 0). Нижній елемент цього стовпця є значенням критерію оптимальності на даному етапі. У першому стовпці (P j) представлені коефіцієнти при базисних невідомих, взяті з критерію оптимальності. Кожен із стовпців X 1 - X 4 відповідає основним змінним завдання, а стовпців X 5 - X 7 - додатковим змінним завдання. Останні елементи цих стовпців утворюють нижній рядок, що містить елементи Δ J. З їх допомогою визначається, чи досягнуто оптимум, а якщо не досягнуть, то яке небазисной невідоме слід ввести в базис, щоб поліпшити план. Елементи останнього стовпця (θ) дозволяють знайти із колишніх базисних невідомих, яке слід вивести з базису, щоб поліпшити план. Дозволяє елемент, розташований на перетині шпальти, що вводиться в базис невідомого, і рядки невідомого, що виводиться з базису, виділений в кожній таблиці.

Розглянемо першу симплексну таблицю рішення задачі.

План завдання знаходиться в шпальтах Б х і Х 0.

Елементи стовпців Х1 - Х 7 є коефіцієнтами заміщення невідомих. Вони показують, в якому співвідношенні будь-які з невідомих можуть замінити базисні змінні в плані даного кроку.

Елементи нижнього рядка стовпців Х1 - Х 7 показують розмір зменшення значення критерію оптимальності від заміни базисних невідомих Х j.

Показник Δ j розраховується перемножением елемента першого стовпця таблиці (P j) на елемент стовпця Х j з наступним відніманням відповідного елемента P j.

Після знаходження L 0 і Δ j, перевіряється умов оптимальності (всі Δ j> 0) і нерозв'язності (якщо знайдеться хоча б один Δ j <0 такий, що всі елементи відповідного стовпчика негативні).

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

Як дозволяє стовпця (невідомої) може бути взятий будь стовпець, для якого оціночний коефіцієнт негативний. Однак за дозволяє стовпець зазвичай приймають стовпець, для якого негативний оціночний коефіцієнт приймає найменше значення.

Для визначення невідомого, яке необхідно вивести з базису, використовують показники останнього стовпця θ. Він отриманий шляхом ділення елемента третього стовпчика Х 0 на елемент стовпця невідомого, що вводиться в базис наступного кроку. Параметр θ показує, який ресурс нас лімітує, тому з базису виводиться змінна, відповідна найменшому позитивному значенню θ.

Рядок у новій таблиці, відповідна роздільної, виходить з роздільною рядки розподілом всіх елементів на дозволяючий елемент.

Стовпці, що відповідають базисним невідомим, є поодинокими, причому одиниця стоїть на перетині рядка і стовпця з однаковими змінними.

Після заповнення нової таблиці (будь-яка нова таблиця є новою по відношенню до даної) знову перевіряється виконання умов оптимальності та можливості розв'язання задачі.

У третій симплекс-таблиці виконується умова оптимальності. Рішення завдання припиняється. Максимальне значення лінійної форми: L ГУРТ = 18.

Відповідь: оптимальне рішення х * = (0.5; 0; 0; 2.5), тобто х 1 * = 0.5, х 2 * = 0, х 3 * = 0, х 4 * = 2.5.

Таблиця 1

Симплексна таблиця першого плану завдання

P i

Б x

X 0

X 1

X 2

X 3

X 4

X 5

X 6

X 7

θ

0

X 5

2

-1

2

-1

1

1

0

0

2

0

X 6

12

2

1

1

-2

0

1

0

-

0

X 7

6

2

3

4

2

0

0

1

3

Δ j

0

-1

1

1

-7

0

0

0


Таблиця 2

Симплексна таблиця другого плану завдання

P i

Б x

X 0

X 1

X 2

X 3

X 4

X 5

X 6

X 7

θ

7

X 4

2

-1

2

-1

1

1

0

0

-

0

X 6

18

4

4

5

0

0

1

1

4.5

0

X 7

2

4

-1

6

0

-2

0

1

0.5

Δ j

14

-8

15

-6

0

7

0

0

Таблиця 3

Симплексна таблиця третього плану завдання

P i

Б x

X 0

X 1

X 2

X 3

X 4

X 5

X 6

X 7

7

X 4

2.5

0

1.75

0.5

1

0.5

0

0.25

0

X 6

4

0

1.25

-0.25

0

0.5

0.25

0

1

X 1

0.5

1

-0.25

1.5

0

-0.5

0

0.25

Δ j

18

0

13

6

0

3

0

2

завдання 2

Умова

Вирішити завдання застосувавши симплекс-метод до відповідної двоїстої задачі.

х 1 - х 2 - 6х 3 + 2х 4 + 12х 5 → min

1 - х 2 + х 3 + х 4 + 2х 5 ≥ 3

-x 1 + 2x 2 - 2х 3 + 3х 4 + х 5 ≥ 2

х 1 - х 2 + 3х 3 + х 4 + 3х 5 ≥ 1

Рішення

Запишемо двоїсту задачу:

2y 1 - y 2 + y 3 ≤ 1

-y 1 + 2y 2 - y 3 ≤ -1

y 1 - 2y 2 + 3y 3 ≤ -6

y 1 + 3y 2 + y 3 ≤ 2

2y 1 + y 2 + 3y 3 ≤ 12

max (3y 1 + 2y 2 + y 3) -?

Зведемо задачу до канонічного вигляду:

2y 1 - y 2 + y 3 + y 4 = 1

-y 1 + 2y 2 - y 3 + y 5 = -1

y 1 - 2y 2 + 3y 3 + y 6 = -6

y 1 + 3y 2 + y 3 + y 7 = 2

2y 1 + y 2 + 3y 3 + y 8 = 12

max (3y 1 + 2y 2 + y 3) -?

Всі інші обчислення і дії зручно виробляє в табличній формі (табл. 4 - 6).

Таблиця 4

Симплексна таблиця першого плану завдання

P i

Б y

y 0

3

2

1

0

0

0

0

0

θ

y 1

y 2

y 3

y 4

y 5

y 6

y 7

y 8

0

y 4

1

2

-1

1

1

0

0

0

0

0.5

0

y 5

-1

-1

2

-1

0

1

0

0

0

1

0

y 6

-6

1

-2

3

0

0

1

0

0

-

0

y 7

2

1

3

1

0

0

0

1

0

2

0

y 8

12

2

1

3

0

0

0

0

1

6

Δ j

0

-3

-2

-1

0

0

0

0

0

Таблиця 5

Симплексна таблиця другого плану завдання

P i

Б y

y 0

3

2

1

0

0

0

0

0

θ

y 1

y 2

y 3

y 4

y 5

y 6

y 7

y 8

3

y 1

0.5

1

-0.5

0.5

0.5

0

0

0

0

-

0

y 5

-7

0

0

2

0

1

1

0

0

0

y 6

-8

0

-5

2

0

0

1

-1

0

1.6

0

y 7

1

0

5

0

0

1

0

1

0

0.2

0

y 8

11

0

2

2

-1

0

0

0

1

5.5

Δ j

1.5

0

-3.5

0.5

1.5

0

0

0

0

Таблиця 6

Симплексна таблиця третього плану завдання

P i

Б y

y 0

3

2

1

0

0

0

0

0

y 1

y 2

y 3

y 4

y 5

y 6

y 7

y 8

3

y 1

0.6

1

0

0.5

0.5

0.1

0

0.1

0

0

y 5

-7

0

0

2

0

1

1

0

0

0

y 6

-7

0

0

2

0

1

1

0

0

2

y 2

0.2

0

1

0

0

0.2

0

0.2

0

0

y 8

10.6

0

0

2

-1

-0.4

0

-0.4

1

Δ j

2.2

0

0

0.5

1.5

0.3

0

0.3

0

y 4 ↔ x 1 x 1 = 1

y 5 ↔ x 2 x 2 = 0

y 6 ↔ x 3 x 3 = 0

y 7 ↔ x 4 x 4 = 1

y 8 ↔ x 5 x 5 = 0

Відповідь: оптимальне рішення х * = (1; 0; 0; 10), тобто х 1 * = 1, х 2 * = 0, х 3 * = 0, х 4 * = 1, х 5 * = 0.

завдання 3

Для риття котловану об'ємом 1440 м 3 будівельники отримали три екскаватора. Потужний екскаватор продуктивністю 22.5 м 3 / год витрачає за годину 10 літрів бензину. Аналогічні характеристики середнього екскаватора - 10 м 3 / год і 10/3 л / год, малого - 5 м 3 і 2 л / год. Екскаватори можуть працювати одночасно, не заважаючи один одному. Запас бензину у будівельників обмежений і дорівнює 580 літрів. Якщо рити котлован тільки малим екскаватором, то бензину свідомо вистачить, але це буде дуже довго. Яким чином слід використовувати наявну техніку, щоб виконати роботу якомога швидше?

Рішення

Нехай екскаватори працювали x 1, x 2, x 3 (годину) відповідно, тоді

22.5x 1 + 10x 2 + 5x 3 = 1440 - обсяг робіт

10x 1 + 10/3 x 2 + 2x 3 ≤ 580 - обмеження по витраті бензину

x 1, x 2, x 3 ≥ 0

α = max (x 1, x 2, x 3) → min

Значення α одно найбільшому із значень x 1, x 2, x 3 і це значення потрібно взяти найменшим.

Вирішимо задачу графічно.

Безліч допустимих значень - фігура ABCD.

Визначимо координати точки A:

22.5x 1 + 10x 2 + 5 · 0 = 1440

10x 1 + 10/3 x 2 + 2 · 0 = 580

30x 1 + 10x 2 = 1740

7.5x 1 = 300

x 1 = 40 (год)

x 2 = (1440 - 22.5 · 40) / 10 = 54 (год)

Визначимо координати точки B:

22.5x 1 + 10 · 0 + 5x 3 = 1440

10x 1 + 10/3 · 0 + 2x 3 = 580

45x 1 + 10x 3 = 2880

50x 1 + 10x 3 = 2900

5x 1 = 20

x 1 = 4

x 3 = (1440 - 22.5 · 4) / 5 = 270

Отже, визначені координати всіх точок:

A (40; 54; 0)

B (4; 0; 270)

C (64; 0; 0)

D (58; 0; 0)

Шукане рішення задачі - точка A.

Відповідь: оптимальний режим роботи екскаваторів: Потужний екскаватор - 40часов, Середній екскаватор - 54 години, Малий екскаватор - не використовується.

завдання 4

У пекарні для випічки чотирьох видів хліба використовується борошно двох сортів, маргарин і яйця. Наявне обладнання, виробничі площі та поставки продуктів такі, що в добу можна переробити не більше 290 кг борошна першого сорту, 150 кг борошна другого сорту, 50 кг маргарину, 1280 шт. яєць. У таблиці наведено норми витрати продуктів, а також прибуток від продажу 1 кг хліба кожного виду:

Таблиця 7

Найменування продукту

Норми витрати на 1 кг хліба (за видами)

1

2

3

4

борошно 1 сорту, кг

0.5

0.5

0

0

борошно 2 сорту, кг

0

0

0.5

0.5

маргарин, кг

0.125

0

0

0.125

яйце, шт.

2

1

1

1

прибуток, за 1 кг

14

12

5

6

Потрібно визначити добовий план випічки хліба, який максимізує прибуток.

Рішення

0.5x 1 + 0.5x 2 + 0 · x 3 + 0 · x 4 ≤ 290

0 · x 1 + 0 · x 2 + 0.5x 3 + 0.5x 4 ≤ 150

0.125x 1 + 0 · x 2 + 0 · x 3 + 0.125x 4 ≤ 50

2x 1 + 1x 1 + 1x 3 + 1x 4 ≤ 1280

14x 1 + 12x 2 + 5x 3 + 6x 4 → max

Всі інші обчислення і дії зручно виробляє в табличній формі (табл. 8 - 11).


Таблиця 8

Симплексна таблиця першого плану завдання

P i

Б x

X 0

14

12

5

6

0

0

0

0

θ

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

0

x 5

290

0.5

0.5

0

0

1

0

0

0

580

0

x 6

150

0

0

0.5

0.5

0

1

0

0

0

x 7

50

0.125

0

0

0.125

0

0

1

0

400

0

x 8

1280

2

1

1

1

0

0

0

1

640

Δ j

0

-14

-12

-5

-6

0

0

0

0

Таблиця 9

Симплексна таблиця другого плану завдання

P i

Б x

X 0

14

12

5

6

0

0

0

0

θ

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

0

x 5

90

0

0.5

0

-0.5

1

0

-4

0

180

0

x 6

150

0

0

0.5

0.5

0

1

0

0

14

x 1

400

1

0

0

1

0

0

8

0

0

x 8

120

0

-1

1

1

-4

0

0

1

-

Δ j

5600

0

-12

-5

-8

0

0

112

0

Таблиця 10

Симплексна таблиця третього плану завдання

P i

Б x

X 0

14

12

5

6

0

0

0

0

θ

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

12

x 2

180

0

1

0

-1

2

0

-8

0

0

x 6

150

0

0

0.5

0.5

0

1

0

0

300

14

x 1

400

1

0

0

1

0

0

8

0

0

x 8

300

0

0

1

0

-2

0

-8

1

300

Δ j

7760

0

0

-5

-4

24

0

16

0


Таблиця 11

Симплексна таблиця четвертого плану завдання

P i

Б x

X 0

14

12

5

6

0

0

0

0

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

12

x 2

180

0

1

0

-1

2

0

-8

0

5

x 3

300

0

0

1

1

0

2

0

0

14

x 1

400

1

0

0

1

0

0

8

0

0

x 8

300

0

0

0

-1

-2

-2

-8

1

Δ j

9260

0

0

0

1

12

10

16

0

Відповідь: добовий план випуску продукції: хліб 1-го виду - 400 кг, 2-го виду - 180 кг 3-го виду - 300 кг, 4-го виду - 0 кг.

Список використаних джерел

· Зубков М.Я. Математичні структури та математичне моделювання економіки: Навчальний посібник. Вип. 3в. Математичне програмування. - М .: Изд-во УРАО, 1996. - 68 с.

· Альошина І.Ф. Аналіз і оцінка господарських рішень: Методичні вказівки до вивчення курсу. - М .: Изд-во РОУ, 1996. - 28 с.