Такая задача называется задачей линейного

(11.3)
Такая задача называется задачей линейного программирования (в стандартной форме), общая теория которой рассмотрена, например, в [2].
Прежде чем исследовать задачу (11.1)–(11.3), заметим, что ее можно представить как задачу минимизации целевой функции f(x) =

. на множестве точек (x1,...,xn), удовлетворяющих условиям (11.2) и (11.3). Такое множество называется полиэдром и обозначается Р. Итак, мы имеем экстремальную задачу
f(х) > min, х Î Р .
(11.4)
Выясним, что представляет собой данный полиэдр Р на плоскости x1Ox2 в случае двух продуктов x1 и x2. Из неравенств (11.3) вытекает, что Р
расположен в первом квадранте, а каждое неравенство (11.2) геометрически определяет множество точек, лежащих по одну сторону от прямой

(рис. 11.1), т. е. полиэдр Р представляет собой неограниченное множество в первом квадранте, лежащее вне области, ограниченной многоугольником OABCDEF.

Для удобства введем линии уровня целевой функции, т. е. линии, на которых в плоскости х1Oх2 целевая функция
f(х)=с1x1+с2x2
(11.5)
принимает постоянное значение, например, a, и обозначим ее Za. Очевидно, каждая линия уровня Za={(x1,x2):f(x)=a} является прямой; при этом gradf(x)=

является вектором N,
перпендикулярным линии уровня и направленным (в данном случае) в сторону увеличения a. Таким образом, для нахождения оптимального решения нам следует перемещать линию уровня до касания с многоугольником OABCDE,
при этом оптимальная прямая Z

. коснется либо какой-то вершины (в нашем случае С), либо какого-либо ребра (например, СВ или CD при определенном изменении параметров с1 и с2).
Из приведенной геометрической интерпретации вытекает, что минимум обязательно достигается на одной из вершин многоугольника, поэтому его можно было бы найти методом перебора, сравнивая между собой значения целевой функции во всех вершинах. Конечно, метод перебора в принципе годится и в случае п переменных, однако при больших значениях п он неэффективен.

Содержание Назад Вперед

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий