Як вибрати розв’язуваний елемент?

Перетином напрямного стовпчика та напрямного рядка визначається елемент симплексної таблиці a_lk, який називають розв’язувальним елементом. За допомогою елемента a_lk і методу Жордана—Гаусса розраховують нову симплексну таблицю, що визначатиме наступний опорний план задачі.

 

Чим відрізняється транспортна задача від загальної задачі лінійного програмування?

Транспортна задача є звичайною задачею лінійного програмування і може бути розв’язана симплексним методом, однак особливості побудови математичної моделі транспортної задачі дають змогу розв’язати її простіше. Легко помітити, що всі коефіцієнти при змінних у рівняннях, дорівнюють одиниці, а сама система обмежень задана в канонічній формі. Крім того, система обмежень складається з mn невідомих та m + n рівнянь, які пов’язані між собою співвідношенням .Якщо додати відповідно праві та ліві частини систем рівнянь ;

, то отримаємо два однакових рівняння:

;

.

Наявність у системі обмежень двох однакових рівнянь свідчить про її лінійну залежність. Якщо одне з цих рівнянь відкинути, то в загальному випадку система обмежень буде містити m + n – 1 лінійно незалежне рівняння, отже, їх можна розв’язати відносно m + n – 1 базисних змінних. Назвемо опорним планом транспортної задачі такий допустимий її план, що містить не більш ніж m + n – 1 додатних компонент, а всі інші його компоненти дорівнюють нулю. Такий план є невиродженим. Якщо ж кількість базисних змінних менша ніж m + n – 1, то маємо вироджений опорний план. В задачах же лінійного програмування необхідне дотримання наст. вимог: Допустимий план Х = (х 1, х 2, …, хn) називається опорним планом задачі лінійного програмування, якщо він задовольняє не менше, ніж m лінійно незалежних обмежень системи у вигляді рівностей, а також обмеження щодо невід’ємності змінних.Опорний план Х = (х 1, х 2, …, хn), називається невиродженим, якщо він містить точно m додатних змінних, інакше він вироджений.

 

Які взаємоспряжені задачі називаються симетричними, а які – несиметричними? Чим вони відрізняються?

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