Читайте также:
|
Функция n переменных x 1, x 2,... x n
.
называется линейной функцией, если она представима в виде линейной комбинации переменных, то есть в виде суммы переменных с постоянными коэффициентами
.
Задачей линейного программирования называется задача, состоящая в нахождении экстремального (максимального или минимального) значения линейной функции
при условии, что переменные удовлетворяют системе линейных равенств и неравенств:
Функция, экстремальное значение которой требуется отыскать, называется целевой функцией. Система равенств и неравенств называется системой ограничений.
Всякий набор значений переменных, то есть вектор X значений,
называется планом задачи. План называется допустимым планом, если он удовлетворяет системе ограничений. Обычно (но не всегда) множество допустимых планов бесконечно. На разных планах целевая функция принимает различные значения. Задача линейного программирования требует, чтобы среди всех допустимых планов был найден тот план, на котором целевая функция достигает искомого экстремального значения (максимального и минимального, в зависимости от конкретной задачи). Такой план называется оптимальным планом. Значение целевой функции на оптимальном плане называется оптимумом.
Решить задачу линейного программирования - значит найти ее оптимальный план и оптимум.
7.Теорема о связи решений прямой и двойственной задачи.
(I)
(I)это стандартная форма записи задачи ЛП (прямая задача)
Составим Двойственную задачу (II) к задаче (I)
-компоненты(координаты) вектора y.
Ограничения двойственности
……………………………………
(II)
(II)
(II) называют двойственной задачей задачи (I)
(I) (II)
Замечание. Количество компонент (координат) вектора y в (II) совпадает с количеством 
столбцов 
.
8. Метод северо-западного угла
Согласно этому методу запасы очередного Поставщика используются для обеспечения запросов очередных Потребителей до тех пор, пока не будут исчерпаны полностью. После чего используются запасы следующего по номеру Поставщика.
Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного Поставщика и запросов очередного Потребителя заполняется только одна клетка и соответственно исключается из рассмотрения один Поставщик или Потребитель.
Во избежании ошибок после построения начального базисного (опорного) решения необходимо проверить, что число занятых клеток равно m+n-1.т
9. Метод потенциалов
Если допустимое решение Х =(
) i=1, 2,…m, j=1,2,…n транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков 
(i=1, 2,…m) и потребителей 
(j=1,2,…n), удовлетворяющие следующим условиям
Группа равенств (1) используется как система уравнений
для нахождения потенциалов.
Так как число неизвестных системы на единицу больше числа уравнений,
то одной из них можно задать значение произвольно, а остальные найти
из системы.
Группа неравенств (2) используется для проверки оптимальности опорного решения. Эти неравенства удобнее представить в следующем виде
Числа 
называются оценками для свободных клеток таблицы (векторов условий) транспортной задачи.
11.Пример игры с 2 пальцами.
Два игрока показывают 1 или 2 пальца, при этом предполагают – какое кол-во пальцев укажет противник.
I II
1 2
предположение предположение
II 1 I 2
Рассмотрим все возможные стратегии(конечное число).
(I, II): 1) (1,1)
2) (1,2)
3) (2,1)
4) (2,2)
Аналогично рассматриваются 2 игрока А 4х4
а11 а12 а13 а14
а21 а22 а23 а24
А = а31 а32 а33 а34
а41 а42 а43 а44
а 11 – выигрыш I игрока, при условии, что I принимает 1) и II принимает 1) стратегии
а 12 – выигрыш I игрока, при условии, что I применит 1) стратегию, а II – 2) стратегию.
I II
1 2
II 1 I 1
Выигрыш II игрока 1+2=3
а13 = выигрыш I игрока.
15.Смешанные стратегии.
Смешанными стратегиями игрока наз. перечень вероятностей, с кот. игрок применит свои чистые стратегии.
Пусть 1й игрок имеет m чистых стратегий: 1,2,3,…,m
х-смешан.стратегия 1го игрока
х=(х1,х2,..., хm)
хi ≥0 ∑ х1 =1 i=1,m
Пусть 2й игрок имеет n чистых стратегий: 1,2,3,..,n
у- смешан.стратегия 2го игрока
у=(у1, у2,…, yn)
y≥0 ∑yj=1 j=1,n
14.Позиционные игры и их нормальные формы.
Позиционная игра является расширенным понятием матричной игры(два игрока, конечная игра, нулевая сумма) допуская увеличение количества игроков более 2 (обязательно конечное число игроков) и количество возможных ходов для игроков увеличивается, но обязательное условие сохранение конечности.
Позиционная игра может быть сведена к матричной игре. Процесс сведения позиционной игры к матричной игре называют нормализующей, а полученную матричную игру, игрой в нормальной форме.
Определение. Позиционную игру, называют игрой с полной информацией, если в ∀ (.) партии игрок делающий ход владеет информацией о прежних ходах.
Примеры позиционных игр с полной информацией: шашки, шахматы и т.д.
Не все карточные игры являются позиционными играми с полной информацией.
Замечание. Особенностью позиционной игры с полной информацией является то, что существует седловая (.) матрицы выигрыша 1-го игрока (игра разрешима в оптимальных чистых стратегиях).
Определение. Игру называют игрой с идеальной памятью, если каждый из игроков помнит предшествующие ходы и всю ту информацию, которую он знал раньше.
Дата добавления: 2015-04-11; просмотров: 90 | Поможем написать вашу работу | Нарушение авторских прав |
|