Использование линейного программирования для решения задач оптимизации

Рефераты / Экономико-математическое моделирование / Использование линейного программирования для решения задач оптимизации

Ограничениями будут $x_{i1}+x_{i2}+\dots+x_{im}\le a_i$ и

$x_{1j}+x_{2j}+\dots+x_{nj}\ge b_j$ .

Целевая функция имеет вид: $f(x)=x_{11}c_{11}+x_{12}c_{1<p>2}+\dots+x_{nm}c_{nm}$ , которую надо минимизировать.

Игра с нулевой суммой

Есть матрица A размера $n\times m$ . Первый игрок выбирает число от 1 до n, второй — от 1 до m. Затем они сверяют числа и первый игрок получает aij очков, а второй ( − aij) очков (i — число, выбранное первым игроком, j — вторым). Нужно найти оптимальную стратегию первого игрока. Пусть в оптимальной стратегии число i нужно выбирать с вероятностью pi. Тогда оптимальная стратегия является решением следующей задачи линейного программирования: $p_i\ge 0$ , $p_i\le 1$ , $p_1+\dots+p_n=1$ , $a_{1i}p_1+a_{2i}p_2+\dots+a_{ni}p_n\ge c$ ( $i=1,\dots,m$ ), в которой нужно максимизировать функцию $f(p_1,\dots,p_n,c)=c$ . c в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.

1.3 Методы решения задач линейного программирования

Симплекс-метод

Сведём задачу линейного программирования к просмотру крайних точек допустимого множества. Именно направленный перебор крайних точек допустимого множества и осуществляется в симплекс-методе, изложенном ниже.

Рассмотрим связь между геометрическим понятием крайней точки и его аналитической интерпретацией. Для ограниченного множества $X$ , описанного с помощью системы неравенств

$\begin{displaymath}a^ix \leq b_i, i = 1,2,\ldots,m \end{displaymath}$

крайними точками являются решения невырожденных подсистем вида:

$\begin{displaymath}a^ix = b_i, i \in S \quad a^ix < b_i, i \notin S, \end{displaymath}$

(1)

где $S$ - некоторое подмножество индексов

$1,2,\ldots,\vert S \vert \geq n$

$\begin{displaymath}\vert S \vert = \mbox{dim}\,x = n \leq m \end{displaymath}$

и матрица, составленная из строк-векторов аi, неособенная.

Обозначим единственное решение системы (3) через x. Предположим теперь, что существуют $x' \in X$ и $x'' \in X$ такие, что для $0 < \lambda < 1$ $\begin{displaymath}x = \lambda x' + (1 - \lambda)x''. \end{displaymath}$ Поскольку для $i \in S$

$\begin{displaymath}a^ix' = a^ix'' = 0 = \lambda a^ix' + (1 - \lambda)a^ix'', \end{displaymath}$

то, очевидно, $a^ix' = a^ix'' = 0$ . В силу единственности решения (3) $x' = x'' = x$ .

С другой стороны, если $x$ -- крайняя точка, то можно обозначить через $S$ множество равенств

$\begin{displaymath}i \in S \Leftrightarrow a^ix = 0.\end{displaymath}$

Обозначим через $A_S$ матрицу, составленную из строк $a^i, i \in S.$ Если предположить, что $\mid S \mid < n$ , то существует нетривиальное нуль-пространство

$\begin{displaymath}\lbrace z:A_Sz = 0 \rbrace.\end{displaymath}$ 2)

Выбирая $z$ достаточно малым по норме, можно добиться того, что для $x \in X$ вектор $x' = x + z \in X$ или $\begin{displaymath}a^ix' = a^ix = 0 + 0 = 0 \end{displaymath}$

для $i \in S$ и $\begin{displaymath}a^ix' = a^ix + a^ix + a^iz \geq a^ix -\Vert a^i \Vert \Vert z \Vert \geq \delta/2 > 0\end{displaymath}$

для достаточно малых $\Vert z\Vert$ . Аналогично можно показать, что при этом и $x'' = x - z \in X$ . Так как $\begin{displaymath}x = \frac{1}{2}(x + z) + \frac{1}{2}(x - z), \end{displaymath}$ то получаем противоречие с определением крайней точки. Для направленного просмотра крайних точек допустимого многогранника применяют симплекс-метод, предложенный Дж. Данцигом и затем усовершенствованный многочисленными математиками. Основная идея метода заключается в разбиении множества переменных x = x1, x2, . . ., xn на базисные $x^B_i > 0$ и небазисные $x^N_j$ . Не умаляя общности, можно считать, что базисные переменные являются первыми в векторе x, т.е. x = (xB, xN ).

Скачать реферат

Страница: 1 2 3 4 5 6

Использование линейного программирования для решения задач оптимизации

Другие рефераты на тему «Экономико-математическое моделирование»:

Поиск рефератов

Последние рефераты раздела