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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Завдання № 1 (Симплекс метод рішення задачі лінійного програмування.)

Знайти F _max = 9 x ₁ + 10 x ₂ + 16 x _3, при обмеженнях:

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

F = 9 x ₁ + 10 x ₂ + 16 x ₃ → max

Заповнимо початкову таблицю:

Таблиця 0.

			0	9	10	16	0	0	0	Відношення, θ
i		Базис
1	0		360	18	15	12	1	0	0	30
2	0		192	6	4	8	0	1	0	24
3	0		180	5	3	3	0	0	1	60
	Δ j		0	- 9	- 10	- 16	0	0	0
	Zj		0	0	0	0	0	0	0

Zj обчислюється за формулою

Оцінки (Δj) обчислюються за формулою , Де - Коефіцієнт з першого рядка таблиці.

Вибираємо мінімальну (негативну) оцінку. Вона визначає направляючий стовпець.

Заповнюємо стовпець «θ», за мінімальним значенням визначаємо напрямну рядок.

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

Заповнюємо нову таблицю

Таблиця 1.

			0	9	10	16	0	0	0	Відношення, θ
i		Базис
1	0		72	9	9	0	1		0	8
2	16		24			1	0		0

108

Δ j

384

-2

384

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

Стовпець стає базисним, тобто одиничним.

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

Інші елементи в небазисних шпальтах і в стовпці обчислюємо за правилом трикутника.

Вибираємо мінімальну негативну оцінку. Вона визначає направляючий стовпець.

Заповнюємо стовпець «θ»

За мінімальним значенням визначаємо напрямну рядок.

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

Заповнення другої таблиці здійснюється за аналогією з попередньою.

Таблиця 2.

			0	9	10	16	0	0	0	Відношення, θ
i		Базис
1	10		8	1	1	0		-	0	______
2	16		20		0	1	-		0	______
3	0		96		0	0		-	1	______
	Δ j		400	5	0	0			0
	Zj		400	14	10	16			0

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

Відповідь:

Максимальне значення функції F _max = 400 досягається в точці з координатами:

= 0

= 8

= 20

= 0

= 96

Завдання № 2 (Метод Літтла)

Знайти найкоротший шлях у графі, заданому графічно у вигляді креслення, методом Літтла.

З креслення запишемо матрицю відстаней. (Відстань від т.1 до т.2 одно:

, І т.д.)

∞

18,87

	49,48	51,86	80,51	97,42
2	18,87	∞	32,06	34,48	65,15	84,01
3	49,48	32,06	∞	31,76	61,19	83,20
4	51,86	34,48	31,76	∞	32,14	53,15
5	80,51	65,15	61,19	32,14	∞	22,14
6	97,42	84,01	83,20	53,15	22,14	∞

Припустимо що найкоротший шлях буде таким:

т.1 → т.2 → т.3 → т.4 → т.5 → т.6 → т.1 і складе

Рішення: Перший етап.

Крок 1. Наведемо матрицю відстаней по рядках і стовпцях

(У рядку віднімаємо з кожного елемента мінімальний, потім у стовпцях)

	1	2	3	4	5	6
1	∞	18,87	49,48	51,86	80,51	97,42	18,87
2	18,87	∞	32,06	34,48	65,15	84,01	18,87
3	49,48	32,06	∞	31,76	61,19	83,20	31,76
4	51,86	34,48	31,76	∞	32,14	53,15	31,76
5	80,51	65,15	61,19	32,14	∞	22,14	22,14
6	97,42	84,01	83,20	53,15	22,14	∞	22,14

↓

	1	2	3	4	5	6
1	∞	0	30,61	32,99	61,64	78,55
2	0	∞	13,19	15,61	46,28	65,14
3	17,72	0,30	∞	0	29,43	51,44
4	20,10	2,72	0	∞	0,38	21,39
5	58,37	43,01	39,05	10,00	∞	0
6	75,28	61,87	61,06	31,01	0	∞
	0	0	0	0	0	0

↓

	1	2	3	4	5	6
1	∞	0	30,61	32,99	61,64	78,55
2	0	∞	13,19	15,61	46,28	65,14
3	17,72	0,30	∞	0	29,43	51,44
4	20,10	2,72	0	∞	0,38	21,39
5	58,37	43,01	39,05	10,00	∞	0
6	75,28	61,87	61,06	31,01	0	∞

Крок 2. Визначимо оцінки нульових клітин:

Крок 3. Викреслюємо клітку з максимальною оцінкою. Включаємо дану клітку в шлях обходу. (5 - 6)

Крок 4. Переписуємо матрицю відстаней, накладаючи заборону на одну з кліток для виключення передчасного замикання контуру (в клітку 6-5 ставимо ∞).

	1	2	3	4	5
1	∞	0	30,61	32,99	61,64
2	0	∞	13,19	15,61	46,28
3	17,72	0,30	∞	0	29,43
4	20,10	2,72	0	∞	0,38
6	75,28	61,87	61,06	31,01	∞

Далі повторюємо кроки 1 - 4, поки не дійдемо до однієї клітини.

Другий етап.

Крок 1. Наведемо матрицю відстаней по рядках і стовпцях.

	1	2	3	4	5
1	∞	0	30,61	32,99	61,64
2	0	∞	13,19	15,61	46,28
3	17,72	0,30	∞	0	29,43
4	20,10	2,72	0	∞	0,38
6	75,28	61,87	61,06	31,01	∞
	0	0	0	0	0,38

↓

	1	2	3	4	5
1	∞	0	30,61	32,99	61,26
2	0	∞	13,19	15,61	45,90
3	17,72	0,30	∞	0	29,05
4	20,10	2,72	0	∞	0
6	75,28	61,87	61,06	31,01	∞

Крок 2. Визначимо оцінки нульових клітин:

Крок 3. Викреслюємо клітку з максимальною оцінкою. Включаємо дану клітку в шлях обходу. (1 - 2)

Крок 4. Переписуємо матрицю відстаней, накладаючи заборону на одну з кліток для виключення передчасного замикання контуру (в клітку 2 - 1 ставимо ∞).

	1	3	4	5
2	∞	13,19	15,61	45,90
3	17,72	∞	0	29,05
4	20,10	0	∞	0
6	75,28	61,06	31,01	∞

Третій етап.

Крок 1. Наведемо матрицю відстаней по рядках і стовпцях.

	1	3	4	5
2	∞	13,19	15,61	45,90
3	17,72	∞	0	29,05
4	20,10	0	∞	0
6	75,28	61,06	31,01	∞
	17,72	0	0	0

↓

	1	3	4	5
2	∞	13,19	15,61	45,90	13,19
3	0	∞	0	29,05	0
4	2,38	0

	∞	0	0
6	57,56	61,06	31,01	∞	31,01

↓

	1	3	4	5
2	∞	0	2,42	32,71
3	0	∞	0	29,05
4	2,38	0	∞	0
6	26,55	30,05	0	∞

Крок 2. Визначимо оцінки нульових клітин:

Крок 3. Викреслюємо клітку з максимальною оцінкою. Включаємо дану клітку в шлях обходу. (4 - 5)

Крок 4. Переписуємо матрицю відстаней, накладаючи заборону на одну з кліток для виключення передчасного замикання контуру (в клітку 6 - 4 ставимо ∞).

	1	3	4
2	∞	0	2,42
3	0	∞	0
6	26,55	30,05	∞

Четвертий етап.

Крок 1. Наведемо матрицю відстаней по рядках і стовпцях.

	1	3	4
2	∞	0	2,42	0
3	0	∞	0	0
6	26,55	30,05	∞	26,55

↓

	1	3	4
2	∞	0	2,42
3	0	∞	0
6	0	3,50	∞

Крок 2. Визначимо оцінки нульових клітин:

Крок 3. Викреслюємо клітку з максимальною оцінкою. Включаємо дану клітку в шлях обходу. (3 - 4)

Крок 4. Переписуємо матрицю відстаней, накладаючи заборону на одну з кліток для виключення передчасного замикання контуру (в клітку 6 - 3 ставимо ∞).

	1	3
2	∞	0
6	0	∞

П'ятий етап.

Залишилися не задіяними зв'язку 2 - 3 і 6 - 1.

У результаті отримуємо наступний ланцюжок:

1 → 2 → 3 → 4 → 5 → 6 → 1

Довжина шляху становить:

L = 18, 87 +32,06 +31,76 +32,14 +22,14 +97,42 = 234,39

це і є найкоротший шлях.

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Завдання
70.6кб. | скачати