поддержка
проекта:
разместите на своей странице нашу кнопку!И мы
разместим на нашей странице Вашу кнопку или ссылку. Заявку прислать на
e-mail
код нашей кнопки:
Линейное программирование
Линейное программирование - раздел математического программирования.
Основная задача линейного программирования - найти экстремум (максимум
или минимум) функции.
причем переменные функции должны удовлетворять ограничениям:
Возможны видоизменения условий (2): вместо некоторых неравенств
возможны равенства, вместо знака > может использоваться знак < ; однако
в теории линейного программирования доказывается, что любые такие
видоизменения можно привести к виду (2). Задачи линейного
программирования широко используются в задачах математической экономики
и других прикладных областях. Некоторые
примеры приведены в статье "Математике программирование".
Функция f называется целевой, а наборы
значений <х1, ..., хn) (точки
n-мерного пространства) удовлетворяющие
ограничениям (2), называй допустимыми решениями.
Теория линейного программирования хор изучена. В случае, когда все
ограничения являютсянеравенствами, область допустимых решений
представляет собой либо обычный (ограниченный) многоранник в
n-мерном пространстве (на рис. 1 заштрихован),
либо многогранник, бесконечны некоторых направлениях (рис. 2). Каждая
грань кой фигуры образована (n - 1) -мерной
плоскостью (для двумерного пространства - прямой), которой соответствует
одному из линейных ограниченны случае, если некоторые ограничения
являются равенствами, размерность многогранника уменьшается. Например,
если в двумерном пространстве ( задачи с двумя переменными Х1, Х2 одно
из oграничений (2) имеет вид: ai1X1 +ai2Х2 = Bi
(т. е. является уравнением прямой), то область допустимых решений
представляет собой отрезок э прямой (одномерный многогранник).
Любому допустимому значению d целей функции (1) соответствует
плоскость в n-мерном пространстве (задаваемая
уравнением f(x1,...,хn) = d,
пересекающая многогранник. Для двумерном пространства на рис. 1 и 2 -
это прямая с уравнением c1х1 + с2х2=d. С
изменением d эта прямая перемещается параллельно самой себе. Доказано,
что экстремум целевой функции достигается обязательно в вершине
многогранника. Правда, может случиться так, что плоскость целевой
функции вообще ни при каком ее значении не пересекает многогранник
допустимых решений. Это означает, что решения данной задачи не
существует. Может случиться и так, что многогранник "пуст", т. е. не
содержит ни одной точки. Это означает, что ограничения противоречивы.
Геометрический смысл задачи линейного программирования, как видно из
рисунков, вполне ясен; но объем вычислений при ее решении может
оказаться довольно большим. Дело в том, что хорошая геометрическая
"картинка" получается только на двумерной плоскости, когда число
переменных равно двум. Реальные же задачи содержат большое число
(десятки и сотни) переменных и ограничений. Поэтому вершины
многогранника и значения переменных в них приходится определять
алгебраическими методами с помощью ЭВМ. К настоящему времени для задач
линейного программирования разработаны стандартные программы для ЭВМ
