Крок 0: Використовуючи лінійну модель стандартної форми, визначають НДБР шляхом прирівнювання до нуля n-m (небазисних) змінних.
Крок 1: З числа поточних небазисних змінних вибирається включається в новий базис змінна, збільшення якої забезпечує поліпшення значення цільової функції. Якщо її немає - поточний базисне рішення оптимально, інакше перехід до кроку 2.
Крок 2: З числа змінних поточного базису вибирається исключаемая змінна, яка повинна стати небазисной при введенні до складу базису нової змінної.
Крок 3: Знаходиться нове базисне рішення, відповідне нових складів базисних і небазисних змінних. Перехід до Кроку 1.
(Відповідає точці A Ha) - початкова дозволене рішення.
Стовпець, асоційований з введеної перемінної - провідний стовпець; рядок, що відповідає исключаемой змінної - провідна рядок; на їх перетині - провідний елемент.
Пошук нового базисного рішення здійснюється методом виключення змінних (метод Жордана-Гаусса). Цей процес включає в себе обчислювальні процедури двох типів.
Тип 1. Формування провідного рівняння
Нова ведуча рядок = попередня провідна рядок / провідний елемент
Тип 2. Формування інших рівнянь
Нове рівняння = попереднє рівняння - (коефіцієнт ведучого шпальти попереднього рівняння) * (нова ведуча рядок)
Нова симплекс-таблиця, отримана після проведення розглянутих операцій:
xI - вводиться змінна (тому що коефіцієнт в -уравненіі -1/2). Исключаемая змінна s1, (відношення 4/3 - мінімальне). Знову проведемо обчислення двох типів. Остання симплекс-таблиця відповідає оптимальному вирішенню завдання, тому що в -уравненіі жодна з небазисних змінних не фігурує з негативними коефіцієнтами.
Що стосується мінімізації цільової функції в цьому алгоритмі необхідно змінити тільки умова оптимальності: в якості нової базисної змінної слід вибирати змінну, яка в -уравненіі має найбільший позитивний коефіцієнт. Умови допустимості в обох випадках однакові.
Корисний матеріал? Поділися:
Не знайшли те, що шукали? Google вам на допомогу!
Генерація сторінки за: 0.021 сек.