Архів якісних рефератів

Знайти реферат за назвою:         Розширений пошук

Меню сайту

Головна сторінка » Математика

Задачі з предмету "математичне програмування" (практична робота)

Задача 1.

Розв'язати задачі лінійного програмування графічним методом: :

Рішення:

Дана задача з двома змінними, що дозволяє розв'язати її графічно.

1. Згідно умові х1 > 0, х2 > 2, саме тому область дозволених значень буде знаходитися у першій координатній площині. Приведемо цю систему рівнянь у вигляд, який дозволить нам побудувати прямі, які визначаються цими рівняннями:

Þ Þ

Рівняння прямої типу означає, що пряма лінія відрізує на осі 1 відрізок довжиною а, а на осі 2 - відрізок довжиною b.

2. Відносно кожної прямої визначимо напівплощину, яка відповідає вихідним нерівностям.

 

Нерівність 10х1 + 3х2 ³ 30 визначає напівплощину, яка лежить вище прямої 10х1 + 3х2 = 30.

Нерівність х1 + х2 £ 10 визначає напівплощину, яка лежить нижче прямої х1 + х2 = 10.

Нерівність - х1 + х2 £ 5 визначає напівплощину, яка лежить нижче прямої - х1 + х2 = 5.

Нерівність х2 ³ 2 визначає напівплощину, яка лежить вище прямої х2 = 2.

L1: 10х1 + 3х2 = 30

L3: х1 + х2 = 10

L2: - х1 + х2 = 5

B - max

Q//1


 

A - min


 

Q0 = х1 + 3х2

Q1


 

-1

- 2

- 3

- 4

13

12

11

10

9

8

7

6

5

4

3

2

1

Х2

Х1

Область, де виконуються всі обмеження

L4: х2 = 2

1 2 3 4 5 6 7 8 9 10 11

-6 - 5 - 4 -3 -2 - 1


Графічно це буде мати вигляд (рис. 1):

Q/1


 

Згідно умові задачі, потрібно визначити екстремуми функції:

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

Критерій оптимальності має постійне значення Q0 впродовж лінії Q1, яка визначається рівнянням . Якщо цю лінію переміщати паралельно самої собі, то величини Q0 та Q(х) будуть змінюватися.

Збільшенню критерію оптимальності відповідає переміщення лінії у напрямку, вказаному стрілкою, її мінімальне значення, коли вона проходить через точку А багатокутника області, де виконуються всі обмеження відповідає мінімальному значенню Q(х), та, відповідно, граничне значення, коли вона проходить через точку В багатокутника області, де виконуються всі обмеження відповідає максимальному значенню Q(х).

Відповідь: точка А - min має координати (2,5; 2); точка В – mах має координати (8; 2)

Задача 2.

Розв'язати задачі лінійного програмування симплекс-методом:

хj ³ 0; j =1,3

Рішення:

1. Приводимо задачу к канонічному виду, при цьому всі елементи стовпця вільних членів повинні мати (+) знак.

Для цього в перше рівняння введемо додатні коефіцієнт х4, друге рівняння залишиться незмінним, воно вже є рівністю.

Задача буде мати наступний канонічний вид:

хj ³ 0; j =1,4

2. Знайдемо початковий опірний план, в першій рівності базисною змінною є х4 , у другій рівності базисною змінною є х3 Þ система приведена к (+) одиничному базису. Вільні змінні х1, х2 прирівнюємо до нуля, а базисні змінні - до вільних членів 10 та 3.

Тоді початковий опірний план даної задачі буде мати вигляд:

.

Значення цільової функції у точці z(X0) буде дорівнювати:

3. Цільова функція максимізована наступним чином:

Таким чином:

4. Запишемо цю задачу ЛП у вигляді 0-рівнянь:

хj ³ 0; j =1,4

5. Складемо першу симплекс-таблицю:

Занесемо коефіцієнти цільової функції і системи обмежень у симплексну таблицю в такий спосіб:

• перше обмеження 0 = 10 - х1 - 3х3 – х4 - у перший рядок:

а) у базисний стовпець "Б" - базисну перемінну х4;

б) у стовпець значень (базисної змінної) "3" - значення вільного члена, яке дорівнює 10;

в) у стовпці коефіцієнтів "-X" - коефіцієнти при X, які дорівнюють 1, 0, 3, 1 відповідно;

• друге обмеження 0 = 3 + х1 - х2 - х3 - у другий рядок відповідно:

а) у базисний стовпець "Б" - базисну перемінну х3;

б) у стовпець значень (базисної змінної) "3" - значення вільного члена, яке дорівнює 3;

в) у стовпці коефіцієнтів "-X" - коефіцієнти при X, які дорівнюють –1, 1, 1, 0 відповідно;

• цільову функцію: - у f -рядок:

а) у стовпець значень (базисної змінної) "3" - значення вільного члена, яке дорівнює 9;

б) у стовпці коефіцієнтів "-X" - коефіцієнти при X, які дорівнюють -4, 4, 0, 0 відповідно.

Б3/B3

З

-X1¯

-X2

-X3

-X4

Б

0 =

10

1

0

3

1

Х4®

0 =

3

-1

1

1

0

Х3

f =

9

-4

4

0

0

f

У f - рядку є елемент, якій має (-) знак: х1. Отже, початковий опорний план не є оптимальним.

Перший рядок є ведучим. Бачимо, що серед елементів ведучого стовпця 1" є позитивни1 елемент (1), то існує новий опорний план, більш близький до оптимального. 4" вийде з базису .

Проведемо одну ітерацію методу заміщення (базисних елементів) Жордана-Гаусса. Стовпець 3" залишається базисним й у другій симплексі-таблиці, а стовпець 1" варто зробити "одиничним". Нові дані у другу симплекс-таблицю заносимо за наступним алгоритмом:

1. Ведучий елемент робимо рівним 1. Для цього ведучий рядок поділимо на ведучий елемент. У нашому випадку ведучий елемент дорівнює 1. Виходить: "З" = 10; "х1" = 1; "х2" = 0; "х3" = 3; "х4" = 1 - осталася старою, без змін. Перепишемо її у другу симплекс-таблицю і назвемо рядком, отриманим з ведучого.

2. Інші елементи ведучого стовпця 1" робимо нульовими:

- щоб у 2-му рядку замість (-1) одержати 0, необхідно кожен елемент рядка, отриманого з ведучого, помножити на 1 і додати до 2-го рядка:

"З"=10´1+3=13; "х1"=1´1-1=0; "х2"=1; "х3"=1´3+1=4; "х4"=1

- щоб у f - рядку замість (-4) одержати 0, необхідно рядок, отриманий з ведучого, помножити на 4 і додати до f - рядка:

"З"=10´4+9=49; "х1"=4´1-4=0; "х2"=4; "х3"=4´3=12; "х4"=0

Отримані результати занесемо у другу симплекс-таблицю:

Б3/B3

З

-X1

-X2

-X3

-X4

Б

0 =

10

1

0

3

1

Х1

0 =

13

0

1

4

1

Х3

f =

49

0

4

12

0

f

Саме тому, що в f - рядку другої симплекс-таблиці всі елементи більше чи дорівнюють нулю, то знайдений оптимальний план:

Він є єдиний, тому що не існують інші нульові елементи f - рядку, які відповідають вільним перемінним.

Відповідь: маємо один оптимальний план:

Задача 3.

Розв'язати транспортну задачу методом потенціалів (Аі - пункти постачання, Вj - пункти споживання).

 

В1

В2

В3

В4

Аі

А1

2

1

2

3

10

А2

5

3

2

1

15

А3

6

2

4

2

40

А4

5

1

5

3

10

Bj

30

25

10

10

 

Рішення:

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

 

Згідно умові задачі відома матриця транспортних витрат на доставку 1 т товару:

Використовуючи умовні дані, маємо наступну таблицю:

П. споживання

П. постачання

В1

В2

В3

В4

Наявність товару (Аі), т

А1

2

1

2

3

10

А2

5

3

2

1

15

А3

6

2

4

2

40

А4

5

1

5

3

10

Потреба у товарі (Bj), т

30

25

10

10

 

 

Загальні витрати можливо визначити наступною функцією:

, де хij (j=1,4; i=1,4) - кількість тон товару, який перевозиться і-постачальником j-споживачу; cij(j=1,4; i=1,4) - вартість перевезення 1 тони товару від і-постачальника j-споживачу.

або

Згідно умові, потрібно спланувати перевезення товару таким чином, щоб весь товар був вивезений з пунктів постачання (від кожного пункту постачання до конкретного пункту споживання).

Необхідна умова: кількість перевезеного товару від кожного пункту постачання не повинна перевищувати загальну кількість товару. Саме тому змінні yij потрібно обмежувати згідно запасів:

 

Друга необхідна умова - потреби усіх споживачів повинні бути повністю задоволені. Потреба усіх магазинів т , наявність товару т, саме тому потреба всіх споживачів буде повністю задоволена. Виникає обмеження за потребами - обмеження yij згідно потреб:

Таким чином, задача є закритою, збалансованою

Розв'язання цієї задачі за допомогою методу потенціалів проведемо за наступною схемою:

1. Запишемо умову у виді транспортної таблиці та побудуємо початковий опорний план перевезень.

Для цього виконаємо наступне:

- у стовпець аі - запаси товару і-го постачальника, і = 1,4;

- у рядок bj - потреби j-го споживача, j = 1,4;

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

Побудуємо початковий опорний план цієї задачі за методом "мінімального елемента".

Знаходимо найменший елемент матриці тарифів серед споживачів та постачальників, це клітини (1, 2), (4, 2), (2, 4): .

Спочатку з цих клітин виберемо клітину (1,2).

Таким чином, буде завантажуватися клітина .

, виключаємо рядок із номером 1 (постачальник, запаси якого витрачені повністю). Нове значення:

Виберемо клітину (2,4).

Буде завантажуватися клітина .

, виключаємо стовпець із номером 4 (споживач, попит якого повністю задоволено). Нове значення:

Виберемо клітину (4,2).

Буде завантажуватися клітина .

, виключаємо рядок із номером 4 (постачальник, запаси якого витрачені повністю). Нове значення:

Аналогічно розрахуємо інші складові таблиці.

 

30 (В1)

25 (В2)

10 (В3)

10 (В4)

Споживач

10 (А1)

-

10

-

-

І постачальник забезпечив потреби ІІ споживача

2

1

2

3

15 (А2)

-

5

0

10

ІІ постачальник забезпечив потреби ІІ та IV споживача

5

3

2

1

40 (А3)

30

-

10

-

ІІІ постачальник забезпечив потреби І та ІІІ споживача

6

2

4

2

10 (А4)

-

10

-

-

IV постачальник забезпечив потреби ІІ споживача

5

1

5

3

Постачальник

І споживач повністю забезпечен за рахунок поставок І постачальника

ІІ споживач забезпечен за рахунок поставок І, ІІ та IV постачальника

ІІІ споживач повністю забезпечен за рахунок поставок ІІІ постачальника

IV споживач повністю забезпечен за рахунок поставок ІІ постачальника

 

2. Перевіримо умову для базисних кліток (їх повинно бути m+n-1).

У нашому випадку заповнено 6 клітинок: с12, с22, с24, с31, с33, с42

У зв'язку з тим, що умова не виконується: 6 < 7, у клітину з найменшим тарифом, наприклад с23 , вписуємо нуль, вона також є базисною.

Значення цільової функції буде дорівнювати:

3. Розрахуємо потенціали ui, vj. Кожному постачальнику (кожному рядку) призначимо ui – потенціал постачальника Аі (і = 1,4), кожному споживачу призначимо (кожному стовпцю) vj – потенціал споживача Вj (j = 1,4).

Запишемо у другий стовпець В2, який має найбільшу кількість заповнених клітин, нульовий потенціал v2 =0.

Використовуючи рівняння для базисних (заповнених) клітин знайдемо інші потенціали ui, vj інших рядків та стовпців.

4. По формулі розрахуємо значення небазисних клітин (у таблиці - це ліві нижні кутки небазисних клітин).

Споживач

30 (В1)

25 (В2)

10 (В3)

10 (В4)

uі¯

Постачальник

10 (А1)

 

10

 

 

1

0

2

1

2

2

4

3

15 (А2)

 

-

5

+

0

10

3

1

5

3

2

1

40 (А3)

30

+

 

 

-

10

 

5

6

-3

2

4

-1

2

10 (А4)

 

10

 

 

1

3

5

1

5

5

4

3

vі®

1

0

-1

-2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5. Проведемо аналіз Dij. Ми маємо два (-) значення - D32; D34 - даний план не є оптимальним.

Будуємо інший опорний план. Змінну х22 включаємо у базис. Будуємо цикл по завантаженим клітинам із началом у клітині (3,2): (3,2) ® (2,2) ® (2,3) ® (3,3). Вершинам призначимо знаки черговані (-) та (+), при цьому базову клітину (3,2) визначимо як (+).

Серед (-) клітин виберемо клітину з найменшим вантажем, це клітина (2,2) з вантажем w = x22 = 5. Зробимо перерозподіл таким чином, щоб баланс циклу зостався незмінним. Для цього вантаж w = x22 = 5 добавимо до вантажів у клітинах (+) та віднімемо з вантажів у клітинах (-).

Інші значення перевезень остаються незмінними.

Таким чином, клітина (2,2) виключається з базису, замість неї буде клітина (3,2).

Отримаємо новий опорний план. Розрахуємо його аналогічно попередньому.

Нульовий потенціал v2 =0, отже:

Значення небазисних клітин:

; ;

;

; ;

Новий опорний план має вигляд:

Споживач

30 (В1)

25 (В2)

10 (В3)

10 (В4)

uі¯

Постачальник

10 (А1)

+

-

10

 

 

1

-3

2

1

-1

2

1

3

15 (А2)

 

5

10

0

1

5

3

3

2

1

40 (А3)

-

30

+

5

5

 

2

6

2

4

 

2

10 (А4)

 

10

 

 

1

0

5

1

2

5

1

3

vі®

4

0

2

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Як бачимо, цей план також не є оптимальним. Ми також маємо дві клітини, які мають (-) значення: х11; х13.

Доведеться розраховувати інший опорний план.

Беремо х11 - як базисну. Цикл по завантаженим клітинам із началом у клітині (1,1): (1,1) ® (1,2) ® (3,2) ® (3,1). Вершинам призначимо знаки черговані (-) та (+), при цьому базову клітину (1,1) визначимо як (+).

w = x12 = 10.

Інші значення перевезень остаються незмінними.

Таким чином, клітина (1,2) виключається з базису, замість неї буде клітина (1,1).

Новий опорний план має вигляд:

Споживач

30 (В1)

25 (В2)

10 (В3)

10 (В4)

uі¯

Постачальник

10 (А1)

10

 

 

 

0

2

3

1

2

2

4

3

15 (А2)

 

5

10

2

1

5

3

3

2

1

40 (А3)

20

15

5

 

4

6

2

4

1

2

10 (А4)

 

10

 

 

3

0

5

1

2

5

1

3

vі®

2

-2

0

-1

 

Отриманий план є оптимальним, тому що серед визначених оцінок Dij немає (-) значень.

Значення цільової функції буде дорівнювати:

Таким чином, отриманий опорний план дає економію витрат на транспортування в 45 гр. од. (самий перший план - 265 гр. од).

Отриманий план має вигляд:

,

Відповідь: Для того, щоб перевезти товар з мінімальними витратами 220 гр. од. необхідно:

- від першого постачальника до першого споживача перевезти 10 т товарів;

- від другого постачальника до четвертого споживача перевезти 10 т товарів;

- від третього постачальника: до першого споживача - 20 т, до другого споживача - 15 т, до третього споживача - 5 т товарів;

- від четвертого постачальника до другого споживача перевезти 10 т товарів.





Реферат на тему: Задачі з предмету "математичне програмування" (практична робота)


Схожі реферати



5ka.at.ua © 2010 - 2016. Всі права застережені. При використанні матеріалів активне посилання на сайт обов'язкове.    
.