Тема 2. Математическое программирование в организационном управлении

При изучении темы следует обратить внимание на основные утверждения линейного программирования:

• ограничения задачи образуют выпуклый многогранник, который называется симплексом;
• решение задачи находится в одной из вершин симплекса и представляет собой одно из опорных (базисных) решений;
• в каждой из вершин симплекса не равны нулю столько переменных, сколько ограничений-равенств в стандартной постановке задачи; остальные переменные равны нулю;
• переменные, не равные нулю, называются базисными, а остальные (равные нулю) – небазисными (свободными).

Эти утверждения хорошо иллюстрируются графоаналитическим методом для двух переменных и лежат в основе симплекс-метода.

Следует хорошо уяснить основную идею симплекс-метода: начиная с некоторой угловой точки производится направленный перебор соседних вершин симплекса. При этом перебираются не все, а только ограниченное число вершин, ведущих к улучшению значения целевой функции. Для перехода к соседней вершине одна из свободных переменных вводится в базис, а одна из базисных – выводится из базиса и становится свободной (раной нулю). Координаты новой вершины получают решением системы N линейных уравнений (по числу ограничений-равенств) методом Гаусса-Жордана относительно базисных переменных.

Особое внимание в симплекс-методе следует обратить на условие оптимальности и условие допустимости, из которых вытекают правила для выбора переменной, вводимой в базис, и переменной, выводимой из базиса. Выполнение этих условий гарантирует переход к соседней вершине симплекса с улучшенным значением целевой функции.

Нужно уяснить, что в модифицированном (матричном) симплекс-методе в отличие от обычного на каждой итерации вместо процедуры Гаусса-Жордана используется обращение матрицы коэффициентов ограничений при базисных переменных. Поэтому данный метод имеет второе название – метод обратной матрицы.

Важно знать и понимать, что симплекс-метод начинает работу только с какого-либо базисного решения, которое, как правило, неизвестно. Для получения одного из базисных решений используется метод искусственного базиса, который позволяет запустить симплекс-метод из специально созданной искусственной вершины, удовлетворяющей ограничениям задачи, и в результате получить одну из реальных угловых точек. Таким образом, общая процедура решения задачи содержит два этапа (двухэтапный метод):

• получение допустимого базисного решения методом искусственного базиса;
• уточнение решения до оптимального симплекс-методом.

Очень важное значение имеют задачи целочисленного программирования, в которых фигурируют штучные материальные ресурсы. Математическая постановка таких задач содержит переменные, которые могут принимать только целые значения. Следует помнить, что такие задачи, с одной стороны, не могут быть решены обычными методами оптимизации, а с другой стороны, округление результатов совершенно неприемлемо по теоретическим и практическим соображениям. Для решения таких задач разработаны специальные методы, дополняющие процедуру оптимизации: метод ветвей и границ, метод Гомори и другие. Наиболее универсальным и эффективным в общем случае является метод ветвей и границ, или метод возврата.

Следует хорошо уяснить основные принципы метода ветвей и границ:

1. При получении недопустимого (нецелочисленного) решения задача путём введения искусственных ограничений разбивается на две подзадачи («ветвление»), которые могут иметь целочисленное решение. Для запоминания и хранения подзадач формируется их список в виде дерева.
2. Из списка поочередно выбираются подзадачи и решаются (симплекс-методом или методами НЛП) до получения допустимого целочисленного решения или выявления отсутствия допустимого решения. Если полученное целочисленное решение по значению целевой функции хуже ранее найденного («границы»), то дальнейшее ветвление прекращается («возврат»). В случае получения решения, по значению целевой функции лучшего границы, оно принимается за границу.

Важно знать и понимать, что метод ветвей и границ реализует ограниченный (часто почти полный) перебор допустимых решений и тем самым на несколько порядков увеличивает вычислительную сложность решения. Поэтому при постановке задачи следует придерживаться следующих рекомендаций [1]:

1. По возможности аппроксимировать целочисленные переменные непрерывными.
2. Насколько возможно, сузить интервалы допустимых значений целочисленных переменных.
3. Избегать в модели задачи нелинейных функций.

Особо следует отметить, что метод ветвей и границ применим к задачам как линейного, так и нелинейного программирования.

Очень важное место в организационном управлении занимает булево программирование, к которому приводят задачи оптимизации на графах, задачи комбинаторной оптимизации и многие другие. Следует помнить, что термин «булево программирование» – не совсем точный, так как на самом деле в этих задачах переменные принимают не логические, а арифметические двоичные значения 0 и 1. В частности, это касается пакета Excel.

Задачи булева программирования можно рассматривать как частный случай целочисленных, поэтому к ним применим метод ветвей и границ с той особенностью, что ветвление по каждой переменной происходит по значениям 0 и 1 без введения дополнительных ограничений. Кажущаяся простота таких задач по сравнению с целочисленными привела к разработке многочисленных эвристических методов их решения, которые основаны на специально сконструированных тестах для определения целесообразности дальнейшего ветвления. Однако практика показала, что в большинстве случаев более эффективным оказывается метод ветвей и границ. Кроме того, эвристические методы годятся только для задач линейного программирования.

Метод ветвей и границ используется в MS Excel для решения задач целочисленного и булева программирования. Для подключения метода достаточно в окне «Поиск решения» добавить ограничение на целочисленность или двоичность переменных.

Контрольные вопросы для самопроверки:

1. Перечислите основные утверждения линейного программирования.
2. Какие переменные называются базисными и небазисными (свободными)?
3. Как выразить целевую функцию и ограничения через свободные переменные?
4. Поясните суть условия допустимости в симплекс-методе.
5. В чём состоит условие оптимальности в симплекс-методе?
6. Перечислите и поясните основные шаги симплекс-метода при известном базисном решении.
7. Поясните назначение и суть метода искусственного базиса.
8. В чём особенность математической постановки задачи целочисленного программирования?
9. Поясните принцип ветвления в методе ветвей и границ.
10. Как формируется последовательность подзадач в методе ветвей и границ?
11. Поясните суть термина «граница» в методе ветвей и границ.
12. Перечислите и поясните основные шаги метода ветвей и границ.
13. Почему метод ветвей и границ имеет второе название «метод возврата»?
14. В чём особенность математической постановки задачи булева программирования?
15. Как применить метод ветвей и границ для решения задач булева программирования?
16. В чём особенность решения задач целочисленного и булева программирования в MS Excel?

Дата добавления: 2015-04-29