рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Двойственные задачи линейного программирования.

Реферат Курсовая Конспект

Выберите учебное заведение

Двойственные задачи линейного программирования.

Двойственные задачи линейного программирования. - раздел Образование, Принятие решений в условиях неопределенности. (Егорова) Пусть Дана Задача Линейного Программирования F(X) = C1X...

Пусть дана задача линейного программирования

F(x) = c₁x₁ + … + c_mx_n → max

а₁₁х₁+ а₁₂х₂ + … + с_m₁х_n ≤ в₁

а₂₁х₁+ а₂₂х₂ + … + с_m₂х_n ≤ в₂

....а_m₁х₁+ а_m₂х₂ + … + с_mnх_n ≤ в_m

Двойственной задачей является задача

Ζ (Y)= в₁у₁ + в₂у₂ + … + в_mу_m → min

а₁₁у₁+ а₁₂у₂ + … + с_m₁у_n ≥ с₁

а₂₁у₁+ а₂₂у₂ + … + с_m₂у_n ≥ с₂

….

а_n₁у₁+ а_n₂у₂ + … + с_mnу_n ≥ с_m

y_j ≥0, j = 1, 2 … m

y₁, y₂…y_m – неизвестные двойственной задачи

Неизвестных в двойственной задачи столько, сколько ограниченных неравенств в двойственной задачи. Соответствующее число ограниченной двойственной задачи равно числу неизвестной двойственной задачи. Если матрицу обозначить через (А). Если одна из пары двойственной задачи имеет оптимальное решение, то двойственная задача так же имеет оптимальное решение, причём значение целевых функций на оптимальном решении совпадают.

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

Пример: Ζ (x) = 6x₁ + 7х₂ + 9x₃ → min

1х₁+ 2х₂ + 3х₃ ≥ 5

1х₁+ 1х₂ + 1х₃ ≥2

1х₁+ 2х₂ + 6х₃ ≥7

Х₁≥0; Х₂≥0; Х₃≥0

F(Y)= 5у₁ + 2у₂ + 4у₃ → max A = A^T =

1у₁+ 2у₂ + 1у₃ ≤ 6

2у₁+ 1у₂ + … + 2у₃ ≤ 7

3у₁+ 1у₂ + 6у₃ ≤ 9

Формулы вычисления среднего выигрыша

Чтобы найти средние или математические ожидания нужно каждое значение случайной величины умножить на соответствующую вероятность и результат сложить. Значению a_ij соответствующей вероятности р_i , q_j

a_ij соответствующая вероятность р_i , q_j ; Н_А(Р,Q)

Н_А(Р,Q) = (для первого)

Н_B(Р,Q) = (для второго)

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Принятие решений в условиях неопределенности. (Егорова)

При решении социально экономических задач приходиться принимать противоречивые интересы относящиеся к различным лицам и организациям В таких... Теория игр изучает процессы принятия оптимальных решений это раздел... Математическая теория игр была разработана американским уч ным Джордоном Неймоном и Марген Штеймах в году как...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Двойственные задачи линейного программирования.

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Критерий Макси Макса. Максиминный критерий Вальда.
С его помощью определяется стратегия, максимизирующая максимальные выигрыши для каждого состояния природы. Это критерий крайнего оптимизма. Наилучшим признается решение, при котором достигается м

Критерий оптимизма и пессимизма Гурвица.
Согласно критерию Гурвица оптим. стратегия выбирается по след формуле: Она содержит наимен. и наиб выигрыш γ-сте

Критерий Севиджа.
Выбирая 1 из возможных решений останавливается на той стратегии, которая ведет к наименее тяжелым последствиям. За последствия отвечает риск. Элементы матрицы рисков отметим через эл-ты rij

Нижняя и верхняя цена игры. максиминные и минимаксные стратегии.
Рассмотрим парную конечную игру. игроки А и В. А имеет стратегии А1, А2, . . ., Аn В имеет стратегии В1, В2, . . ., Вn Дан

Максиминный принцип.
αi=minαij βj=max βji j i Величина (

Решение матричных игр с седловой точкой.
Если верхняя и нижняя цены совпадают, то эта величина называется ценой игры. Стратегии, соответствующие цене

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

Принцип доминирования. Доминирующие и дублирующие стратегии.
Вектор х=(х1, х2,х3…хn)(упорядочен набор) доминирует вектор у=(у1, у2, у3…уn) если хi ≥ у

Геометрическое решение игры в смешанных стратегиях(2х n)
Для каждой стратегии второго игрока Вi=(i=1,2,…n) проведем прямую у. Если первый игрок применяет свою смешанную стратегию 1, то выигрыш первого игрока, тогда второй игрок применяет стратегию Вi

Алгоритм симплексного метода решения задач линейного программирования
Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее: 1. Привести задачу к каноническому виду 2. Найти начальное опорное решение с &qu

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

Порядок работы с симплекс таблицей
Первая симплекс-таблица подвергается преобразованию, суть которого заключается в переходе к новому опорному решению. Алгоритм перехода к следующей таблице такой:

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

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