• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Алгоритм відшукання оптимального плану.

1. Після знаходження опорного плану обчислюються значення визначників:

,

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

В стовпчику вільних членів в цьому рядку записуємо значення функціоналу, рівне відношенню F₁ i F₂

В результаті приходимо до таблиці (Табл.3):

Табл.3

	-y 1 -y 2 -x s -x n	1
х1= х2= ym=	b 11 b 12 b 1s b 1n b 21 b 22 b 2s b 2n b m1 b m2 b ms b mn	b 1 b 2 b m
F1= F2=	p 1 p 2 p s p n q 1 q 2 q s q rn	0 0
dj=	d 1 d 2 d s d n

2. При розв’язуванні задачі на максимум функціоналу за розв’язуючий стовпчик вибираємо той, в якому d_j < 0. Коли таких стовпчиків декілька, то за розв’язуючий стовпчик краще брати той, в якому d_j найбільший по абсолютній величині.

3. Розв’язуючи елемент в стовпчику шукається по найменшому симплексному відношенню.

4. Із знайденим b_rs робимо один крок МЖВ при цьому коефіціенти стрічок F₁ і F₂ перетворюються за загальним правилом, а останній рядок не перетворюється і не записується.

5. Далі для кожного стовпчика обчислюємо визначники d_j, а для плану - значення функціоналу F^(k+1). Якщо серед d_j є хоча б один від’ємний, то робимо новий крок МЖВ і т. д.

6. Оптимальний розв’язок буде досягнуто, коли після чергового кроку всі визначники d_j стануть невід’ємними.

7. При розв’язуванні задачі на мінімум, за розв’язуючий приймається стовпчик з d_j > 0. Критерієм оптимальності служить недодатність d_j.

ПРИКЛАД.

Знайти максимум та мінімум функціоналу:

При виконанні обмежень:

РОЗВ’ЯЗАННЯ.

Складаємо початкову жорданову таблицю, заповнюючи коефіцієнтами функціоналу для чисельника та знаменника окремо два рядки F₁ F₂ (Табл.4).

Табл.4

Так як b₃ = -1 < 0, то план х₁ = х₂ = х₃ = 0 не є опорним.

Знайдемо опорний план. Відшукавши такий план, додаємо до таблиці ще один рядок, в який записуємо значення d_j і функціоналу F (Табл.5).

Табл.5

Оскільки всі визначники d_j недодатні, робимо висновок, що функціонал досягає мінімуму у вершині

x₁ = 0, x₂ = 0, x₃ = 1

Для знаходження максимуму вибираємо за розв’язуючий другий стовпчик. Розв’язуючий елемент b_rs = 10. З цим елементом робимо крок МЖВ, перетворюючи всю таблицю, крім останнього рядка d_j. В результаті отримаємо таблицю виду (Табл.6).

Табл.6

Елемент від’ємний – це означає, що максимум ще не досягнуто.

В першому стовпчику вибираємо за розв’язуючий елемент з ним робимо наступний крок МЖВ і отримаємо нову таблицю (Табл.7).

Табл.7

Обчисливши в новій таблиці всі знову знаходимо один від’ємний, а тому робимо ще один крок МЖВ з елементом . В результаті отримали таблицю (Табл.8).

Табл.8

5	-y 2 -y 1 -x 3
x1= x2= y3=	1/5 1/2 -1/10 2/5 3/2 -7/10 0 5/2 -3/2	5/2 11/2 7/2
F1= F2=	4/5 -7/2 -9/10 7/5 0 -11/5	21/2
dj=

В Табл.8 всі визначники d_j невід’ємні. Це свідчить про те, що при значеннях невідомих функціонал досягає максимального значення . Задача розв’язана.

Читайте також:

1. Rete-алгоритм
2. Абстрактна модель оптимального планування виробництва
3. Алгоритм
4. Алгоритм
5. Алгоритм 1.
6. Алгоритм RLE
7. Алгоритм безпосередньої заміни
8. Алгоритм Берлекемпа-Мессі
9. Алгоритм Дейкстри.
10. Алгоритм Деккера.
11. Алгоритм Деккера.

Переглядів: 1485