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

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

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

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. Алгоритм Деккера.

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