Головна |
алгоритм методу1. Запишемо задачу в формі (5.7), при цьому всі елементи стовпця вільних членів повинні бути невід'ємні , . Рівняння системи (5.5), в яких вільні члени негативні, попередньо потрібно помножити на - 1. 2. Таблицю (5.7) перетворимо кроками Жордана-Гаусса винятків. При цьому на кожному кроці що дозволяє може бути обраний будь-який стовпець, що містить хоча б один позитивний елемент. Рядок цільової функції на вибір дозволяють стовпців вплив не робить. 3. Роздільна рядок визначається за найменшим з відносин вільних членів до елементів дозволяє стовпця. 4. У процесі перетворень викреслюємо рядки, що складаються з одних нулів. 5. Якщо в процесі перетворень зустрічається рядок, все елементи якої нулі, а вільний член відмінний від нуля, то завдання не має рішення. Якщо зустрінеться рядок, в якій, крім вільного члена, інших позитивних елементів немає, то говорять, що завдання не має позитивних рішень. Пояснення. У п.1.1 алгоритму передбачається, що всі елементи стовпця вільних членів невід'ємні. Ця вимога необов'язково. У разі коли в стовпці вільних членів зустрічаються негативні числа, будемо користуватися теоремою. Теорема.Якщо дозволяє елемент вибирати за найменшим позитивного симплекс-відношенню, то після кроку Жордана-Гаусса вільний член в роздільною рядку стає позитивним, а решта членів зберігають свій знак. Вибір дозволяє елемента виробляють інакше, а саме. 1. Переглядають рядок, відповідну будь-якого негативного вільному члену. Вибирають в ній будь-якої негативний елемент - відповідає цьому елементу стовпець буде вирішальним. 2. Вибір дозволяє елемента проводиться за мінімальним позитивного симплекс-відношенню. Якщо завдання можна вирішити, то через кінцеве число кроків отримують перше допустиме рішення і можна застосовувати симплекс-метод. У деяких випадках знайдене таким чином, перше допустиме рішення є також і оптимальним рішенням. Метод штучного базису. | Взаімодвойственние завдання. Ігри, які не містять сідлової точки. Змішані стратегії. | Рішення гри. | Рішення гри. | Рішення матричних ігор. | Лінійне програмування. | Завдання лінійного програмування. | Побудова економіко-математичних моделей задач лінійного програмування. | Графічне рішення задачі лінійного програмування. | Симплекс-метод. | Алгоритм симплекс-методу. | |