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

Алгоритм симплекс-методу

Теорема. Якщо В>0, задача (2.4) - (2.6) завжди має розв’язок; він може бути отриманий за кінцеве число кроків.

3. Запишемо (2.5) в іншій формі:

x₁ • A₁ + x₂ • A₂ +...+ x_n • A_n = B, (2.7)

де ; ; .... - стовпці матриці А.

Припустимо, що матриця А містить у собі одиничну матрицю порядку m, розташовану в перших m стовпцях А₁, А₂,...А_М.

Тоді початковий план Х₀ має вигляд:

або у вигляді вектора . (2.8)

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

Розв’язок (план) системи (2.5) за умови (2.6) назвемо припустимим.

Ненульовий припустимий розв’язок задачі називається опорним розв’язком (планом), якщо вектори А_j, щовідповідають додатним координатам плану утворюють незалежну лінійну систему. Якщо число векторів у цій системі дорівнює m, план називається не виродженим, якщо менше - виродженим.

План (вектор) X тоді і тільки тоді є опорним розв’язком задачі, коли точка
М(х₁, х₂,...х_n) є вершиною припустимого багатогранника.

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

1. Rete-алгоритм
2. АЛГОРИТМ
3. Алгоритм
4. Алгоритм
5. Алгоритм
6. АЛГОРИТМ
7. Алгоритм 1.
8. Алгоритм 2
9. Алгоритм RLE
10. Алгоритм адресного вибору оптимального безрецептурного вітаміновмісного лікарського препарату, лікарської форми і шляху введення
11. Алгоритм безпосередньої заміни
12. Алгоритм Берлекемпа-Мессі

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