інійного програмування.
2. Побудова сімплексної табліці. p> 3. Перевірка опорного плану на оптімальність помощью оцінок. Если ВСІ ОЦІНКИ задовольняють умову оптімальності, то визначеня опорний план є оптимальним планом задачі. Если хочай б одна з оцінок НЕ задовольняє умову оптімальності, то переходять до нового опорного плану або встановлюються, что оптимального плану задачі НЕ існує.
4. Перехід до нового опорного плану задачі віконується визначеня розв'язувального елемента та розрахунки Нової сімплексної табліці.
5. Повторення Дій починаючі з п. 3. Розглянемо докладніше Кожний з етапів алгоритму.
1. Визначення Першого опорного плану почінають Із записами задачі лінійного програмування в канонічній ФОРМІ, тоб у вігляді обмежень-рівнянь з невід'ємнімі правих Частинами. Если в умові задачі Присутні обмеження-нерівності, то Перетворення їх на рівняння віконується помощью Додатковий змінніх, Які вводяться до лівої Частини обмежень типом В«<В» Зі знаком В«+В», а до обмежень типу В«>В» - Зі знаком В«-В». У цільовій Функції задачі додаткові змінні мают коефіцієнт нуль.
После зведення задачі до канонічного вигляд ее запісують у векторній ФОРМІ. За зазначену опорного плану задачі лінійного програмування его утворюють т одінічніх лінійно незалежних векторів, Які становляит базис w-вімірного простору (де m - кількість обмежень у задачі лінійного програмування).
На цьом етапі розв'язування задачі Можливі Такі випадка:
после записами задачі у векторній ФОРМІ в Системі обмежень є Необхідна кількість одінічніх векторів. Тоді початковий опорний план візначається безпосередно без Додатковий Дій;
у Системі обмежень немає необхідної кількості одінічніх незалежних векторів. Тоді для побудова Першого опорного плану застосовують метод штучного базису. Ідея его Полягає в тому, что відсутні одінічні вектора можна дістаті, увівші до відповідніх обмежень деякі змінні з коефіцієнтом +1, Які назіваються штучний. У цільовій Функції задачі лінійного програмування штучні змінні мают коефіцієнт + М (для задачі на min) або-М (для задачі на max), де М-й достатньо ровері додатне число.
Візначені одінічні лінійно незалежні Вектори утворюють базис, и змінні задачі, что відповідають їм, назівають базисних, а ВСІ Інші змінні - вільнімі, їх прірівнюють до нуля та з шкірного обмеження задачі візначають значення базисних змінніх. У такий способ отримуються початковий опорний план задачі лінійного програмування.
2. Подалі обчислювальний процес та перевірку опорного планом на оптімальність подаються у вігляді сімплексної табліці.
У первом стовпчік табліці - В«БазисВ» - запісують базісні змінні опорного плану, причому в тій послідовності, в якій смороду розміщуються в Системі обмежень задачі.
Наступний стовпчік сімплексної табліці - В«З баз В» - КОЕФІЦІЄНТИ при базисному змінніх у цільовій Функції задачі.
У третини стовпчік - В«ПланВ»...
