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

Алгоритм знаходження початкового опорного плану

1.Складаємо початкову жорданову таблицю для задачі (2.6) – (2.8).

			….		….		І
			….		….
			….		….
….	….	….	….	….	….	….	….
			….		….
….	….	….	….	….	….	….	….
			….		….
			….		….

Якщо усі (стовпчик вільних членів) додатні, то опорний план знайдено:

Якщо , то - опорний план

2.Припустимо, що серед вільних членів є від’ємне число . Проглядаємо стрічку з номером . Якщо у цій стрічці всі елементи невід’ємні , то система обмежень визначає пустий многогранник, нерівності несумісні, задача розв’язку немає.

3.Нехай у - ій стрічці елемент ‑ від’ємний. Таких елементів може бути декілька. Проглядаємо елементи стовпчика з номером і елементи стовпчика вільних членів, порівнюючи їх попарно (в одній стрічці). Фіксуємо тільки ті пари, у яких однакові знаки.

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

5.Знаходимо найменше симплексне відношення:

6.В якості розв’язуючого елемента приймаємо - елемент -го стовпчика, що розміщений в рядку з мінімальним симплексним відношенням. З цим елементом робимо один крок модифікованих жорданових перетворень.

7.В сприятливому випадку розв’язуючим елементом може виявитися елемент . Тоді в результаті одного кроку новий вільний член в -ій стрічці виявиться додатнім, а решта збережуть свої знаки. Якщо розв’язуючий елемент виявиться в іншому рядку, то робимо один крок МЖВ і знову звертаємося до -го рядка, оскільки вільний член в ньому залишиться від’ємним. Так продовжуємо роботу з -им рядком до тих пір поки розв’язуючий елемент не виявиться елементом -го рядка.

8.Аналогічно перетворюємо і всі інші від’ємні елементи стовпчика вільних членів. За скінченне число кроків або отримаємо опорний план, або переконаємося, що задача немає розв’язку.

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

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

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