Главная | Обратная связь | Поможем написать вашу работу!

Основна ідея методу

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

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

Симплексний метод базується на методі повних виключень Жордана-Гаусса для знаходження розв’язку сумісної системи обмежень (рівнянь). Цей метод використовує таку властивість:

– якщо і -й рядок матриці коефіцієнтів помножити (поділити) на одне й те саме число або додати (відняти) відповідні коефіцієнти двох рядків, то таке елементарне перетворення матриці не змінює множину розв’язків цієї системи рівнянь.

Унаслідок такого перетворення обмеження,які складають систему, мають вигляд

де – базисні змінні з коефіцієнтами „+1”(тобто змінні, які утворюють одиничний базис);

– різниця між загальною множиною змінних та множиною базисних змінних .

Таку систему називають зведеною.

Якщо довільно знадавати значення змінним (вільним змінним) та знаходити базисні змінні

то дістанемо множину допустимих розв’язків системи (наприклад, в окремому випадку при = 0 значення ).

Кожна сукупність базисних змінних, які утворюють одиничний базис, відповідає системі рівнянь, яку називають базисом. Розв’язок системи т рівнянь з т базисними змінними (якщо покласти, що всі вільні змінні дорівнюють нулю) називають базисним.

Перехід від одного розв’язку до іншого виконують за допомогою алгебраїчних перетворень, переходячи від однієї системи рівнянь до іншої, яка є еквівалентною. Такий перехід до наступної системи рівнянь (і, цілком зрозуміло, до наступного розв’язку), виконують за допомогою формул перетворення метода Жордана - Гаусса:

для вибраного рядка матриці

для інших елементів матриці

де – розрахунковий елемент, – елемент ведучого рядка чому а не ? , – ведучий елемент перетворення, – елемент ведучої колонки .

Знаходження елементів за наведеними формулами – це жорданове перетворення.

Для розв’язування задач лінійного типу використовується універсальний симплексний метод. Цей метод і ряд його модифікацій є ітераційним процесом, який складається з декількох однотипних кроків обчислення. Такий мМетод називають ітераційним (від лат. iteratio – повторення), якщо в ньому крок за кроком поліпшується початковий розв’язок задачі. Кожний такий крок методу називають ітерацією., Іітераційні методи найбільш зручні для використання ЕОМ оскільки весь процес обчислення можна зобразити у вигляді циклу, що дуже легко піддається автоматизації.

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

Геометрично симплексний метод віддзеркалює упорядкований перехід від однієї вершини многогранника ОДР до іншої суміжної вершини, яка міститься ще ближче до оптимуму.

Таким чином, перехід від початкової точки до оптимальної виконується поступово, послідовно наближаючись до оптимальної точки-вершини.

С (оптимум) На рис.1.11 початковій точці

B пошуку відповідає точка А.

D Потім послідовно розв’язок

поліпшується за допомогою

А (початок)переходу до наступної кутової

точки.

Рис.1.11

Таким чином, траєкторія пошуку це – траєкторія кутових точок ОДР від початкової базисної точки до точки оптимуму.

⇐ Предыдущая 1 2 3 456 7 8 9 10 Следующая ⇒