Полная версия

Главная arrow Психология arrow Искусство решать сложные задачи. Системный подход

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Линейное программирование

  • 1. Область применения. Используется для решения однокритериальных задач оптимизации, целевая функция которых отвечает условиям детерминированности и линейности, а на значения переменных накладываются линейные ограничения. Линейность предполагает наличие двух свойств: пропорциональности и аддитивности. Пропорциональность означает, что вклад каждой переменной в целевую функцию прямо пропорционален величине этой переменной, а аддитивность заключается в представлении целевой функции в виде суммы вкладов от различных переменных.
  • 2. Сущность. Задачу линейною программирования можно представить следующим образом: минимизировать (либо максимизировать) целевую функцию Y=F(X) при ограничениях на ее переменные в виде А * Х< В либо А * X = В, то есть возможны как равенства, так и неравенства. В канонической (классической) форме это можно записать:

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

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

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

Методы линейного программирования работают надёжно при корректно сформулированных ограничениях и целевой функции. Если они составлены неправильно, то возможны две ситуации: либо отсутствие допустимых решений (когда ограничения противоречат друг другу), либо появление неограниченного числа решений (при не учёте некоторых ограничений или неправильном представлении постоянных коэффициентов в учитываемых ограничениях).

4. Наиболее употребительные методы. Основным методом решения задач линейного программирования является симплекс- метод. Существует множество его модификаций, ориентированных на особенности решаемых задач. Литература, посвящённая линейному программированию, достаточно обширна, для изучения и практического использования можно порекомендовать /58, 59, 5/.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>