лгоритму. На кожному кроці ми будемо міняти безлічі простих і непростих векторів (рухатися по ребрах), і матриця буде мати наступний вигляд:
(2)
де cB - коефіцієнти вектора c відповідні простим змінним (змінним xs відповідають 0), B - стовпці АЕ, відповідні простим змінним. Матрицю, утворену залишилися стовпцями позначимо D. Чому матриця буде мати такий вигляд пояснимо в описі кроків алгоритму. p> Перший крок
Вибираємо початкове допустиме значення, як зазначено вище. На першому кроці B - одинична матриця, так як простими змінними є xs. cB - нульовий вектор з тих же причин.
Другий крок
Покажемо, що у виразі тільки непрості змінні мають ненульовий коефіцієнт. Зауважимо, що з виразу Ax + xs = b прості змінні однозначно виражаються через непрості, так як число простих змінних дорівнює числу рівнянь. Нехай x '- прості, а x' '- непрості змінні на даній ітерації. Рівняння Ax + xs = b можна переписати, як Bx '+ Dx' '= b. Помножимо його на ліворуч:. + = p> Таким чином ми висловили прості змінні через непрості, і у виразі, еквівалентному лівій частині рівності, всі прості змінні мають одиничні коефіцієнти. Тому, якщо додати до рівності рівність, то в отриманому рівність всі прості змінні будуть мати нульовий коефіцієнт - всі прості змінні виду x скоротяться, а прості змінні виду xs не ввійдуть у вираз. p> Виберемо ребро, по якому ми будемо переміщатися. Оскільки ми хочемо максимізувати Z, то необхідно вибрати змінну, яка буде більш всіх зменшувати вираз
В
Для цього виберемо змінну, яка має найбільший по модулю негативний коефіцієнт. Якщо таких змінних немає, тобто всі коефіцієнти цього виразу невід'ємні, то ми прийшли в шукану вершину і знайшли оптимальне рішення. В іншому випадку почнемо збільшувати цю непросту змінну, тобто переміщатися по відповідному їй ребру. Цю змінну назвемо входить. p> Третій крок
Тепер необхідно зрозуміти, яка проста мінлива першої звернеться в нуль у міру збільшення вхідної змінної. Для цього достатньо розглянути систему:
В
При фіксованих значеннях непростих змінних система однозначно розв'язана відносно простих, тому ми можемо визначити, яка з простих змінних першої досягне нуля при збільшенні вхідної. Цю змінну назвемо виходить. Це означатиме, що ми натрапили на нову вершину. Тепер вхідну і вихідну змінну поміняємо місцями - входить В«увійдеВ» в просту, а що виходить з них В«вийдеВ» у непрості. Тепер перепишемо матрицю B і вектор cB у відповідності з новими наборами простих і непростих змінних, після чого повернемося до другого кроку. p> Оскільки число вершин звичайно, то алгоритм одного разу закінчиться. Знайдена вершина буде оптимальним рішенням. br/>
2. Використання симплексного методу
Підприємство випускає швидкопсувну продукцію, яку відразу можна доставити споживачу (А1 стратегія). p align="justify"> Н...
