Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах

РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання

ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"

ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ

Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків

Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні

Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах

Гендерна антидискримінаційна експертиза може зробити нас моральними рабами

ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ

ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів


Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






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

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

,

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

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

В результаті приходимо до таблиці (Табл.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. При розв’язуванні задачі на максимум функціоналу за розв’язуючий стовпчик вибираємо той, в якому dj < 0. Коли таких стовпчиків декілька, то за розв’язуючий стовпчик краще брати той, в якому dj найбільший по абсолютній величині.

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

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

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

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

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

ПРИКЛАД.

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

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

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

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

Табл.4

1 -x 1 -х 2 -x 3
y1= y2= y3= -3 6 1 -1 7 2 -2 4 -1 -1
F1= F2= 1 2 -1 3 1 5

 

Так як b3 = -1 < 0, то план х1 = х2 = х3 = 0 не є опорним.


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

Табл.5

2 -x 1 -х 2 -y 3
y1= y2= x3= -5 10 1 -5 15 2 2 -4 -1
F1= F2= -3 2 1 7 -21 -5 -1
dj -8 -11 0 -1/5

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

x1 = 0, x2 = 0, x3 = 1


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

 

Табл.6

3 -x 2 -y 1 -y 3
x2= y2= x3= -1/2 1/10 1/10 5/2 -3/2 ½ 0 2/5 -3/5 1/10 17/2 7/5
F1= F2= -2 -1/5 4/5 -7/2 21/10 -29/10 28/5 7/5
dj= -92/5 11/10 11/5 -12/71

 

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


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

Табл.7

4 -y 2 -y 1 -y 3
x1= x2= x3= 1/5 -1/5 1/5 2/5 -3/5 1/5 0 2/5 -3/5 9/5 17/5 7/5
F1= F2= 4/5 -7/5 6/5 7/5 0 -11/5 28/5 19
dj= 184/25 -133/5 878/25 28/15

 

Обчисливши в новій таблиці всі знову знаходимо один від’ємний, а тому робимо ще один крок МЖВ з елементом . В результаті отримали таблицю (Табл.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 всі визначники dj невід’ємні. Це свідчить про те, що при значеннях невідомих функціонал досягає максимального значення . Задача розв’язана.

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

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



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

<== попередня сторінка | наступна сторінка ==>
Симплек-метод у дробово-лінійному програмуванні. | Вимірювання переміщень.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:
 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.004 сек.