Математична модель задачі 10.4

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 3

Позначимо – кількість корму P₁, – кількість корму P₂, – кількість корму P₃, – кількість корму P₄. Тоді отримаємо математичну модель задачі:

(15)

(16)

(17)

Канонічна форма задачі

Домножуємо нерівності (15) і цільову функцію (17) на (-1)

Введемо нові невід’ємні змінні , і додамо їх до лівих частин нерівностей. Отримаємо систему недоозначених рівнянь (3 рівняння, 7 невідомих).

Складаємо симплекс – таблицю 1.

с имплекс - таблиця 1

-оцінка невідомого .

Вибір розв’язуючого елемента

1. Розв’язуючий елемент повинен бути від’ємним!

2. Розв’язуючий рядок – P7 знаходимо з умови min (P0). min (-100;-100;-300) = -300.

3. Розв’язуючий стовпець – P4 знаходимо з умови min (|Dj/aij|), тут i – номер розв’язуючого рядка. min (200/25; 50/80; 70/120; 100/500) = 100/500.

4. Вектор P7 виходить з базису, Вектор P4 входить у базис.

5. Розв’язуючий елемент – число -500 – знаходиться на перетині розв’язуючого рядка P7 і розв’язуючого стовпця P4.

Алгоритм двоїстого симплекс-методу

1. Розв’язуючий рядок P7 ділимо на розв’язуючий елемент – число -500;

2. Базисні стовпці P5, P6 i P7 повинні бути одиничними векторами;

3. Усі інші елементи таблиці (стовпці P0 - P4 крім рядка P7) перераховуються згідно правила прямокутника:

. (18)

Тут розв’язуючий елемент; елемент, який перераховується.

В результаті отримуємо наступну симплекс-таблицю 2.

симплекс - таблиця 2

План, який представлений у цій таблиці не є оптимальним, оскільки серед вільних членів P0 є від’ємні. За описаним вище алгоритмом знаходимо розв’язуючий рядок – P6 та розв’язуючи стовпець – P1. Змінна P6 виходить з базису, змінна P1 входить у базис. Застосовуючи алгоритм двоїстого симплекс-методу отримуємо наступну симплекс-таблицю 3.

симплекс - таблиця 3

5. Оскільки всі P0 ³ 0, отримано оптимальний розв’язок задачі. Оптимальні значення параметрів x1, x4 i x5 знаходимо у стовпчику P0. Невідомі x2, x3, x6 i x7 яких немає у базисі є вільними і дорівнюють нулю.

Відповідь. Оптимальний харчовий раціон має вигляд: x1 = 0.63; x2 = 0; x3 = 0; x4 = 0.57; x5 = 39.8; x6 = 0; x7 = 0. Fmin (сумарна вартість) = 182,61.

Таблиця 4. В а р і а н т и з а в д а н ь д о т е м и 1 0

Тема 11

Задача лінійного програмування: задача про розріз труб

11.1. Завдання. Побудувати математичну модель задачі лінійного програмування (задача на мінімум відходів). Звести задачу до канонічної форми. Розв’язати задачу двоїстим симплекс-методом.

11.2. Постановка задачі:

В обробку поступила партія труб довжиною L = 7.5 м кожна. Необхідно розрізати труби, отримавши N1= 50 заготовок довжиною L1 = 3.5 м, N2= 30 заготовок довжиною L2 = 2.5 м і N3= 40 заготовок довжиною L3 = 2.0 м. Побудувати оптимальний план розрізу при якому сумарна довжина відходів буде мінімальною.

Таблиця 5. Таблиця варіантів розрізу

Математична модель задачі

Позначимо x _і – кількість труб, розрізаних згідно і – го варіанту. Тоді отримаємо математичну модель задачі у наступному вигляді:

(19)

(20)

. (21)

Канонічна форма задачі

Домножимо нерівності (19) і цільову функцію (21) на (-1). Введемо нові невід’ємні змінні і додамо їх до лівих частин нерівностей. Отримаємо систему недоозначених рівнянь (3 рівняння, 10 невідомих).

Задача розв’язується двоїстим симплекс – методом.

Таблиця 6. В а р і а н т и з а в д а н ь д о т е м и 1 1

Тема12

Транспортна задача

Постановка задачі.

Три бригади за тиждень виробляють корми в кількостях a₁, a₂ i a₃ відповідно. Їх необхідно розвезти на 5 ферм, згідно з поданими заявками, у кількостях b₁, b₂, b₃, b₄, b₅. Вартість перевезення вважається пропорційною до кількості завантаженого корму x_ij і відстані від постачальника (бригади) до споживача (ферми) c_ij. Необхідно скласти такий план перевезень кормів, загальна вартість якого буде мінімальною. Необхідні для розрахунку параметри представлені у наступній Таблиці 7.

Таблиця 7. Технологічні параметри транспортної задачі.

Необхідно скласти оптимальний план закріплення бригад за фермами з умовою мінімальної вартості перевезення кормів.

12.2. Математична модель транспортної задачі

Позначимо x_ij – кількість одиниць корму, який планується перевезти від i – го постачальника (сівозміни) до j – го споживача (ферми). Оскільки всі вантажі повинні бути вивезені, то мають місце такі рівності:

(22)

Оскільки всі потреби споживачів повинні бути задоволені, то мають місце такі рівності:

(23)

Оскільки вантажі перевозяться лише в одну сторону, очевидно, що:

(24)

Загальна вартість перевезення вважається пропорційною до кількості перевезених вантажів та відстані від постачальника до споживача і повинна бути мінімальною:

(25)

Якщо виконується умова , задача називається закритою.

12.3. Алгоритм розв’язування ТЗ

Потрібно:

1. скласти початковий опорний план задачі методом північно-західного кута;

2. скласти початковий опорний план задачі методом мінімального тарифа;

3. вибравши кращий з побудованих початкових планів, виконати його оптимізацію методом потенціалів за такою схемою:

3.1. скласти систему рівнянь (по базисних клітинах) для визначення потенціалів рядків U_i та стовпців V_j та, прийнявши U₁=0, розв’язати отриману систему;

3.1.1. визначити характеристики вільних клітин за формулою

; (26)

3.2. якщо всі характеристики є невід’ємні, завершити розв’язування задачі. Виписати оптимальний план перевезень у вигляді матриці, а також мінімальне значення вартості перевезень F_min;

3.3. якщо не всі характеристики є невід’ємні, необхідно вибрати найбільшу додатну характеристику і побудувати для відповідної вільної клітини таблиці цикл. Позначити вершини циклу умовними знаками “+” (збільшити вантажо-потік) i “-” (зменшити вантажопотік). Початкова вільна вершина позначається знаком “+”, а всі інші – по черзі “-” i “+”; серед всіх вершин, позначених знаком “-”, вибрати найменше перевезення – m. Для всіх вершин, позначених знаком “+”збільшити перевезення на m, для вершин, позначених знаком “-” зменшити перевезення на m. Перейти до пункту 3.1

12.4. Побудова початкового опорного плану ТЗ

Таблиця 8. Метод північно – західного кута

F = 60*4 + 70*3 + 10*2 + 110*8 + 70*4 + 60*7 + 100*2 =

240 + 210 + 20 + 880 + 280 + 420 + 200 = 2250 – вартість перевезень

Таблиця 9. Метод мінімального тарифа

F = 10*2 + 130*2 + 60*1 + 20*4 + 100*1 + 50*7 + 110*3 =

20 + 260 + 60 + 80 + 100 + 350 + 330 = 1200 – вартість перевезень

12.5. Метод потенціалів

За основу виберемо план, складений по методу мінімального тарифа. Оптимізуємо даний план за методом потенціалів. Для кожного i – го рядка та j – го стовпця введемо певну їх ознаку – потенціал. Складаємо систему рівнянь (по базисних клітинках плану) для визначення потенціалів рядків і стовпців, використовуючи наступну формулу .

U₁ + V₃ = 2;

U₁ + V₄ = 2;

U₂ + V₁ = 1;

U₂ + V₂ = 4;

U₂ + V₅ = 1;

U₃ + V₂ = 7;

U₃ + V₃ = 3.

Приймемо U₁ = 0. Тоді отримаємо наступний розв’язок системи:

U₁ =0; V₃ = 2;

U₁ =0; V₄ = 2;

U₂ =-2; V₁ = 3;

U₂ =-2; V₂ = 6;

U₂ =-2; V₅ = 3;

U₃ =1; V₂ = 6;

U₃ =1; V₃ = 2.

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

. (27)

Тут та - потенціали відповідних рядка і стовпця, - тариф даного перевезення. Додатна характеристика вільної клітини свідчить про неоптимальність плану і є підставою для включення даної клітини в новий план. Обчислимо характеристики вільних клітин:

D₁₁ = u₁ + v₁ – c₁₁ = 0 + 3 – 4 = -1;

D₁₂ = u₁ + v₂ – c₁₂ = 0 + 6 – 3 = +3;

D₁₅ = u₁ + v₅ – c₁₅ = 0 + 3 – 4 = -1;

D₂₃ = u₂ + v₃ – c₂₃ = -2 + 2 – 8 = -8;

D₂₄ = u₂ + v₄ – c₂₄ = -2 + 2 – 4 = -4;

D₃₁ = u₃ + v₁ – c₃₁ = 1 + 3 – 9 = -5;

D₃₄ = u₃ + v₄ – c₃₄ = 1 + 2 – 7 = -4;

D₃₅ = u₃ + v₅ – c₃₅ = 1 + 3 – 2 = +2.

Характеристики D₁₂ і D₃₅ є додатніми. Це свідчить про неоптимальність плану. Клітинку A₁B₂ необхідно включити в план. Деяку клітинку необхідно виключити з базису. Для цього складаємо цикл вільної клітини. Клітина A₁B₂ буде початком циклу.

12.6. Перерозподіл вантажопотоків по вершинах циклу - 1

	B1	B2	B3	B4	B5	Запаси
A1		4	+	3	-	2		2		4	140
				10		130
A2		1		4		8		4		1	180
60		20						100
A3		9	-	7	+	3		7		2	160
		50		110
Потреби

Будуємо цикл. Це є ламана лінія, вершини якої розташовані у клітинах таблиці, а ланки – вздовж рядків, чи стовпців. В кожній вершині циклу зустрічається дві ланки, одна з яких знаходиться у рядку, а друга у стовпці. Початковою вершиною завжди виступає вільна клітина. Всі інші вершини – це базисні клітини. Форма циклу – це прямокутник, “чобіт”, або ”вісімка”. Якщо ламана лінія, що утворює цикл перетинається, то точки самоперетину не є вершинами.

Початкову клітину циклу A₁B₂ помічаємо знак “+”. Всі інші кутові вершини циклу по черзі помічаємо знаками “-” i ”+”. В якості перерозподілюваного елемента вибираємо число 10 (мінімальний вантаж серед усіх клітин помічених знаком “-”). До клітинок помічених знаком “+” додаємо число 10, від клітин помічених знаком “-” віднімаємо число 10. Клітина A₁B₂ входить у базис, клітина A₁B₃ виходить з базису. Отримуємо новий план

Види циклів.

прямокутник “чобіт” ”вісімка”

12.7. Метод потенціалів. Другий крок

Познавательные статьи:



Техника прыжка в длину с разбега

Тактические действия в защите

История Олимпийских игр

История развития права интеллектуальной собственности