Программа дисциплины (syllabus) (стр. 9 )

Точка (а, b) называется седловой точкой функции Н, если

.

Это неравенство выражает следующее свойство функции Н в точке (а, b): при любом изменении значения переменной а значение функции Н может уменьшиться, а при изменении значения переменной b — увеличиться. Термин “седловая точка” вводится по аналогии с термином “поверхность седла”, которая искривляется вверх в одном направлении и вниз — в другом.

Теорема 1. Для того чтобы в матричной игре (2) существовали седловые точки, необходимо и достаточно, чтобы

. (8)

Теорема 2. Пусть  и  - две седловые точки матричной игры (2). Тогда:

a)  и  являются седловыми точками;

b) .  (11)

Смешанные стратегии

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

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

Пусть задана матричная игра (2). В дальнейшем мы будем называть стратегии  чистыми, чтобы отличать их от смешанных стратегий, определение которых будет дано ниже.

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

Смешанная стратегия игрока I в игре Г есть вектор

,

где  — вероятность выбора им i-й чистой стратегии, , а поскольку одна из m чистых стратегий будет обязательно выбрана, представляет собой вероятность полной группы событий и, следовательно,

.

Аналогично смешанная стратегия игрока II есть вектор

,

где  - вероятность выбора им j-й чистой стратегии,  и .

Чистые стратегии являются частным случаем смешанной стратегии, задаваемой единичным вектором.

Множества смешанных стратегий игроков I и II будем обозначать соответственно через :

Тема 8 Линейные и нелинейные модели.

План

1)Задачи линейного программирования.

2)Транспортная задача и ее модификации.

3)Сетевые модели.

Краткое изложение материала

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления A1, A2, …, Am в n пунктов назначения B1, B2, …, Bn. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через cij тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт назначения, через ai - запасы груза в i-м пункте отправления, через bj - потребности в грузе в j-м пункте назначения, а через xij - количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка транспортной задачи состоит в определении минимального значения функции

при условиях

Поскольку переменные xij (i=1,m; j=1,n) удовлетворяют системам линейных уравнений и условию неотрицательности, обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.

Определение 1. Всякое неотрицательное решение систем линейных уравнений, определяемое матрицей X=(xij) (i=1,m; j=1,n), называется планом транспортной задачи.

Определение 2. План X*=(xij*) (i=1,m; j=1,n), при котором целевая функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записываются в виде таблицы 5.1.

Таблица 5.1

Пункты отправления	Пункты назначения	Запасы
B1	. . .	Bj	. . .	Bn
A1	c11   x11	. . .	c1j   x1j	. . .	c1n   x1n	a1
. . .	. . .	. . .	. . .	. . .	. . .	. . .
Ai	ci1  xi1	. . .	cij   xij	. . .	cin   xin	ai
. . .	. . .	. . .	. . .	. . .	. . .	. . .
Am	cm1   xm1	. . .	cmj   xmj	. . .	cmn   xmn	am
Потребности	b1	. . .	bj	. . .	bn

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна . Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.

=

то модель такой транспортной задачи называется закрытой. Если же указанное условие не выполняется, то модель транспортной задачи называется открытой.

Теорема 1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т. е. чтобы выполнялось равенство.

В случае превышения запаса над потребностью, т. е. при

>, вводят фиктивный (n+1)-й пункт назначения с потребностью bn+1=- и соответствующие тарифы считают равными нулю: cin+1=0 (i=1,m). Полученная задача является транспортной задачей, для которой выполняется равенство закрытости.

Аналогично, при <, вводят фиктивный (m+1)-й пункт отправления с запасом груза am+1=- и соответствующие тарифы считают равными нулю: cm+1j=0 (j=1,n). Этим задача сводится к транспортной задаче с закрытой моделью, из оптимального плана которой получается оптимальный план исходной задачи. Поэтому в дальнейшем мы будем рассматривать только закрытую модель транспортной задачи.

Число переменных xij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системе ограничений равно n+m. Так как предполагается, что выполняется условие закрытости, то число линейно-независимых уравнений равно n+m-1. Следовательно, опорный план транспортной задачи может иметь не более n+m-1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности n+m-1, то план является невырожденным, а если меньше - то вырожденным.

Для определения опорного плана существует несколько методов. Ниже рассматриваются два из них - метод северо-западного угла, метод потенциалов.