Эффективные средства линейного программирования лежат в основе и целочисленного и нелинейного программирования для решения более сложных задач оптимизации. Эти методы, однако, требуют более длительного времени для вычислений.
В последующих лекциях будут подробно разобраны примеры решения типичных задач оптимизации и принятия управленческих решений с помощью надстройки MS Excel " Поиск решения". Задачи, которые лучше всего решаются данным средством, имеют три основных свойства:
- имеется единственная цель, функционально связанная с другими параметрами системы, которую нужно оптимизировать (найти ее максимум, минимум или определенное числовое значение);
- имеются ограничения, выражающиеся, как правило, в виде неравенств (например, объем используемого сырья не может превышать запасов сырья на складе, или время работы станка за сутки не должно быть больше 24 часов минус время на обслуживание);
- имеется набор входных значений-переменных, влияющих на оптимизируемые величины и на ограничения.
Параметры задач ограничиваются такими предельными показателями:
- количество неизвестных – 200;
- количество формульных ограничений на неизвестные – 100;
- количество предельных условий на неизвестные – 400.
Алгоритм поиска оптимальных решений включает в себя несколько этапов:
- подготовительные работы;
- отладка решения;
- анализ решения .
Последовательность необходимых подготовительных работ , выполняемых при решении задач экономико-математического моделирования с помощью MS Excel , приведена на блок-схеме рисунка 1.6 .
Рис.
1.6.
Из приведенных пяти пунктов плана подготовительных работ только пятый пункт является формализуемым. Остальные работы требуют творчества - и разными людьми они могут быть выполнены по -разному. Кратко поясним сущность формулировок пунктов плана.
При постановке задачи известны целевые коэффициенты
и нормированные коэффициенты
.
В предыдущем примере коэффициентами, формирующими целевую функцию, служили значения нормированной прибыли на одну полку типа
(
) и одну полку типа (
). Нормированными коэффициентами
служили нормы расхода
материала и машинного времени на одну полку каждого типа. Матрица
имела следующий вид:
Кроме того, всегда известны значения ресурсов
. В предыдущем примере это был
недельный запас досок и возможности использовать
машинное время: 
, 
. Часто в задачах значения переменных
требуется
ограничить. Поэтому нужно определить нижний и верхний пределы области их изменений.
Таким образом, в диалоговом окне оптимизационной программы " Поиск решения" мы должны задать следующий целевой алгоритм :
Целевая функция равна произведению вектора искомых значений переменных на вектор целевых коэффициентов
Нормированных коэффициентов на вектор искомых значений переменных не должен превышать значения заданного вектора ресурсов
Значения переменной должны находиться в заданных пределах число исходных элементов системы
Число исходных элементов системы
Число заданных видов ресурсов
Отладка решения необходима в случае, когда программа выдает сообщение об отрицательных результатах (рисунок 1.7):
Рис. 1.7.
- если не получено допустимое решение, то выполнить корректировку модели исходных данных;
- если не получено оптимальное решение , то ввести дополнительные ограничения.
Программа выдает оптимальное решение только для модели реальной проблемы, а не решение самой проблемы. При построении модели были сделаны различные упрощающие допущения реальной ситуации. Это позволило формализовать процесс, приближенно отобразив реальные количественные зависимости между параметрами системы и целью. А если реальные параметры будут отличаться от тех, которые заложены в модели, то как изменится решение? Чтобы узнать это, перед принятием управленческого решения проводят анализ решения модели.
Анализ оптимального решения , встроенный в программу, представляет собой заключительный этап математического моделирования экономических процессов. Он позволяет осуществить более глубокую проверку соответствия модели процессу, а также надежности оптимального решения. Он основывается на данных оптимального решения и отчетов, которые выдаются в "Поиске решения". Но он не исключает и не заменяет традиционного анализа плана с экономических позиций перед принятием управленческого решения.
Экономический анализ ставит перед собой следующие цели :
- определение возможных последствий в системе в целом и ее элементах при изменении параметра модели;
- оценка устойчивости оптимального плана к изменению отдельных параметров задачи: если он не устойчив к изменению большинства параметров, снижается гарантия его выполнения и достижения рассчитанного оптимума;
- проведение вариантных расчетов и получение новых вариантов плана без повторного решения задачи от исходного базиса с помощью корректировки.
Возможные методы анализа представлены в схеме на рисунке 1.8 .
После получения оптимального решения проводится его анализ по полученным отчетам. Анализ устойчивости - изучение влияния изменений отдельно взятых параметров модели на показатели оптимального решения. Анализ пределов - анализ допустимых изменений в оптимальном плане, при котором план остается оптимальным.
Учитывая ответственность принятия экономического управленческого решения , руководитель должен убедиться, что полученный оптимальный план является единственно верным. Для этого надо на основе модели получить ответы на следующие вопросы:
- "что будет, если…"
- "что надо, чтобы…"
Анализ с целью ответа на первый вопрос называется вариантным анализом ; анализ с целью ответа на второй вопрос называется решениями по заказу.
Вариантный анализ бывает следующих видов:
- Параметрический - анализ, который заключается в решении задачи при различных значениях некоторого параметра.
- Структурный анализ - когда решение задачи оптимизации ищется при различной структуре ограничений.
- Многокритериальный анализ - это решение задачи по разным целевым функциям.
- Анализ при условных исходных данных - когда исходные данные, используемые при решении задачи, зависят от соблюдения дополнительных условий.
После проведения анализа следует представить результаты в графической форме и составить отчет с рекомендациями о принятии решения с учетом конкретной экономической ситуации.
Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных x1, x2, …, xn, удовлетворяющие m условиям - равенствам
и обращающие в максимум линейную функцию этих переменных
Для простоты предположим, что все условия (1) линейно независимы (r=m), и будем вести рассуждения в этом предположении.
Назовём допустимым решением ОЗЛП всякую совокупность неотрицательных значений x1, x2, …, xn, удовлетворяющую условиям (1).Оптимальным назовём то из допустимых решений, которое обращает в максимум функцию (2). Требуется найти оптимальное решение.
Всегда ли эта задача имеет решение? Нет, не всегда.
ЗЛП неразрешима (не имеет оптимального решения):
Из-за несовместности системы ограничений. Т.е. система не имеет ни одного решения, как показано на рисунке 1.
Рисунок 1 - Несовместность системы ограничений
Из-за неограниченности целевой функции на множестве решений. Другими словами при решении ЗЛП на max значение целевой функции стремится к бесконечности, а в случае ЗЛП на min - к минус бесконечности, как показано на рисунке 2.
Рисунок 2 - Неограниченность целевой функции на множестве решений
ЗЛП разрешима:
Множество решений состоит из одной точки. Она же и является оптимальной, как показано на рисунке 3.
Рисунок 3 - Множество решений состоит из одной точки
Единственное оптимальное решение ЗЛП. Прямая, соответствующая целевой функции в предельном положений пересекается с множеством решений в одной точке, как показано на рисунке 4.
Рисунок 4 - Единственное оптимальное решение
Оптимальное решение ЗЛП не единственно. Вектор N перпендикулярен к одной из сторон множества решений. В этом случае оптимальной является любая точка на отрезке АВ, как показано на рисунке 5.
Рисунок 5 - Оптимальное решение не единственно
Решение задач линейного программирования симплекс-методом
Симплекс-метод - алгоритм решения задачи ЛП, реализующий перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции С. Симплекс-метод является основным в линейном программировании.
Использование этого метода в дипломном проекте для решения задачи ЛП обусловлено следующими факторами:
Метод является универсальным, применимым к любой задаче линейного программирования в канонической форме;
Алгоритмический характер метода позволяет успешно программировать и реализовать его с помощью технических средств.
Экстремум целевой функции всегда достигается в угловых точках области допустимых решений. Прежде всего, находится какое-либо допустимое начальное (опорное) решение, т.е. какая-либо угловая точка области допустимых решений. Процедура метода позволяет ответить на вопрос, является ли это решение оптимальным. Если «да», то задача решена. Если «нет», то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается. Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции .
Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.
Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен, то возможно выбрать неизвестных, которые выражают через остальные неизвестные. Для определенности обычно полагают, что выбраны первые, идущие подряд, неизвестные. Эти неизвестные (переменные) называются базисными, остальные свободными. Количество базисных переменных всегда равно количеству ограничений.
Присваивая определенные значения свободным переменным, и вычисляя значения базисных (выраженных через свободные), получают различные решения системы ограничений. Особый интерес представляют решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Оно соответствует всем ограничениям.
Имея систему ограничений, находят любое базисное решение этой системы. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому допустимому базисному решению.
Симплексный метод гарантирует, что при этом новом решении линейная форма если и не достигнет оптимума, то приблизится к нему. С новым допустимым базисным решением поступают так же, пока не находят решение, которое является оптимальным.
Если первое найденное базисное решение окажется недопустимым, то с помощью симплексного метода осуществляется переход к другим базисным решениям, пока на каком-то шаге решения базисное решение окажется допустимым, либо можно сделать вывод о противоречивости системы ограничений.
Таким образом, применение симплексного метода распадается на два этапа:
Нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности;
Нахождение оптимального решения в случае совместности системы ограничений.
Алгоритм перехода к следующему допустимому решению следующий:
В строке коэффициентов целевой функции выбирается наименьшее отрицательное число при отыскании максимума. Порядковый номер коэффициента - . Если такового нет, то исходное базисное решение является оптимальным;
Среди элементов матрицы с номером столбца (этот столбец называется ведущим, или разрешающим) выбираются положительные элементы. Если таковых нет, то целевая функция неограничена на области допустимых значений переменных и задача решений не имеет;
Среди выбранных элементов ведущего столбца матрицы выбирается тот, для которого величина отношения соответствующего свободного члена к этому элементу минимальна. Этот элемент называется ведущим, а строка, в которой он находится - ведущей;
Базисная переменная, отвечающая строке ведущего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу ведущего элемента, вводится в число базисных. Строится новое решение, содержащее новые номера базисных переменных.
Условие оптимальности плана при решении задачи на максимум: среди коэффициентов целевой функции нет отрицательных элементов .
Задача линейного программирования (ЗЛП) − это задача нахождения наибольшего (или наименьшего) значения линейной функции на выпуклом многогранном множестве.
Симплекс метод − это метод решения задачи линейного программирования. Суть метода заключается в нахождении начального допустимого плана, и в последующем улучшении плана до достижения максимального (или минимального) значения целевой функции в данном выпуклом многогранном множестве или выяснения неразрешимости задачи.
Рассмотрим следующую задачу линейного программирования в канонической форме:
| (1) |
| (2) |
| (3) |
Метод искусственного базиса
Как было паказано выше, для задачи, записанной в канонической форме, если среди векторов столбцов матрицы A есть m единичных и линейно независимых , можно непосредственно указать опорный план. Однако для многих задач линейного программирования, записанных в канонической форме и имеющих опорные планы, среди векторов столбцов матрицы A не всегда есть m единичных и линейно независимых. Рассмотрим такую задачу:
Пусть требуется найти максимум функции
при условиях
где первы n
элементы нули. Переменные 
называются искусственными
. Векторы столбцы
  | (28) |
образуют так называемый искусственный базис m -мерного векторного пространства.
Так как расширенная задача имеет опорный план, то ее решение можно найти симплекс методом.
Теорема 4.
Если в оптимальном плане 
расширенной задачи (24)−(26) значения искусственных переменных 
, то 
является оптимальным планом задачи (21)−(23).
Таким образом, если в найденном оптимальном плане расширенной задачи, значения искусственных переменных равны нулю, то получен оптимальный план исходной задачи. Остановимся более подробно на нахождении решения расширенной задачи.
Значение целевой функции при опорном плане (27):
Замечаем, что F(X) и состоят из двух независимых частей, одна из которых зависим от M , а другая − нет.
После вычисления F(X) и их значения, а также исходные данные расширенной задачи заносят в симплекс таблицу, как было показано выше. Разность заключается лишь в том, что данная таблица содержит на одну строку больше, чем обычная симплекс таблица. При этом в (m +1)-ю строку помещают коэффициенты, не содержащие M , а в (m +2)-ю строку − коэффициенты при M .
При переходе от одного опорного плана к другому, в базис вводят вектор, соответствующий наибольшему по абсолютной величине отрицательному числу (m +2) строки. Искусственный вектор, исключенный из базиса не имеет смысла вновь ввести в базис. При переходе к другому опорному плану, может случится так, что ни один из искусственных векторов из базиса не будет исключен. Пересчет симплекс таблицы при переходе от одного опорного плана к другому производят по обычным правилам симплекс метода (смотри выше).
Итерационный процесс ведут по m
+2 строке до тех пор, пока элементы m
+2 строки, соответствующие переменным 
не станут неотрицательными. При этом, если искусственные переменные исключены из базиса, то найденный план расширенной задачи отвечает некоторому опорному плану исходной задачи.
m +2 строки, столбца x 0 отрицателен, то исходная задача не имеет решения.
Если же не все искусственные переменные исключены из базиса и элемент m +2 строки, столбца x 0 равен нулю, то опорный план исходной задачи является вырожденным и базис содержит минимум один из векторов искусственного базиса.
Если исходная задача содержит несколько единичных векторов, то их следует включить в искусственный базис.
Если в ходе итераций m +2 строка больше не содержит отрицательных элементов, то итерационный процесс продолжают с m +1 строкой, до тех пор, пока не найден оптимальный план расширенной задачи или не выявлен неразрешимость задачи.
Таким образом, процесс нахождения решения задачи линейного программирования (21)−(23) методом искусственного базиса включает следующие основные этапы:
- Составляют расширенную задачу (24)−(26).
- Находят опорный план расширенной задачи.
- Используя симплекс метод исключают искусственные векторы из базиса. В результате находят опорный план исходной задачи или фиксируют ее неразрешимость.
- Используя найденный опорный план ЗЛП (21)−(23), или находят оптимальный план исходной задачи, или устанавливают ее неразрешимость.
Для решения задач линейного программирования онлайн, пользуйтесь калькулятором
Исследование операций – это комплексная математическая дисциплина, занимающаяся построением, анализом и применением математических моделей принятия оптимальных решений при проведении операций.
Предмет исследования операций - системы организационного управления или организации, которые состоят из большого числа взаимодействующих между собой подразделений не всегда согласующихся между собой и могут быть противоположны.
Цель исследования операций - количественное обоснование принимаемых решений по управлению организациями
Операция – система управляемых действий, объединенная единым замыслом и направленная на достижение определенной цели.
Набор управляющих параметров (переменных) при проведении операции называется решением . Решение называется допустимым , если оно удовлетворяет набору определенных условий. Решение называется оптимальным , если оно допустимо и, по определенным признакам, предпочтительнее других, или, по крайней мере, не хуже.
Признак предпочтения называется критерием оптимальности.
Критерий оптимальности включает в себя целевую функцию направление оптимизации или набор целевых функций и соответствующих направлений оптимизации.
Целевая функция – это количественный показатель предпочтительности или эффективности решений.
Направление оптимизации - это максимум (минимум), если наиболее предпочтительным является наибольшее (наименьшее) значение целевой функции. Например, критерием может быть максимизация прибыли либо минимизация затрат.
Математическая модель задачи ИО включает в себя:
1) описание переменных, которые необходимо найти;
2) описание критериев оптимальности;
3) описание допустимых решений (ограничений, накладываемых на переменные)
Цель ИО – количественно и качественно обосновать принимаемое решение. Окончательное решение принимает ответственное лицо либо группа лиц, называемое ЛПР – лицо, принимающее решение.
Вектор, удовлетворяющий системе ограничений, называется допустимым решением или планом ЗЛП . Множество всех планов называется допустимой областью или областью допустимых решений . План, который доставляет максимум (минимум), целевой функции называется оптимальным планом или оптимальным решением ЗЛП . Таким образом, решить ЗЛП – значит найти ее оптимальный план.
Привести общую ЗЛП к основной очень просто, используя следующие очевидные правила.
Минимизация целевой функции f равносильна максимизации функции g = – f .
Ограничение в виде неравенства равносильно уравнению при условии, что дополнительная переменная.
Если на некоторую переменную x j не накладывается условие неотрицательности, то делают замену переменной,.
Линия уровня функции f , т. е. линию, вдоль которой эта функция принимает одно и то же фиксированное значение с , т. е. f (x 1 , x 2)= c
Множество точек называется выпуклым , если оно вместе с любыми двумя своими точками содержит весь отрезок, соединяющий эти точки.
В случае двух переменных множество решений линейного неравенства (уравнения) представляет собой полуплоскость (прямую).
Пересечение этих полуплоскостей (и прямых, если в системе ограничений есть уравнения) представляет собой допустимую область. Если она не пуста, то является выпуклым множеством и называется многоугольником решений .
В случае трех переменных допустимая область ЗЛП есть пересечение полупространств и, возможно, плоскостей, и называется многогранником решений
Система линейных уравнений называется системой с базисом , если в каждом уравнении содержится неизвестное с коэффициентом, равным 1, отсутствующее в остальных уравнениях системы. Эти неизвестные называются базисными , остальные – свободными .
Систему линейных уравнений будем называть канонической , если она является системой с базисом и все b i ≥ 0. Базисное решение в этом случае оказывается планом, т. к. его компоненты неотрицательны. Назовем его базисным (или опорным ) планом канонической системы.
ОЗЛП будем называть канонической (КЗЛП), если система линейных уравнений этой задачи – каноническая, а целевая функция выражена только через свободные неизвестные.
Т. Если в симплекс-таблице среди коэффициентов при каком-либо свободном неизвестном имеется хотя бы один положительный элемент, то возможен переход к новой канонической задаче, равносильной исходной, в которой указанное свободное неизвестное оказывается базисным (при этом одно из базисных неизвестных переходит в число свободных).
Теорема 2 . (об улучшении базисного плана) j , а в столбце х j имеется хотя бы один положительный элемент, причем ключевое отношение >0, то возможен переход к равносильной канонической задаче с не хужим базисным планом.
Теорема 3 . (достаточное условие оптимальности) . Если все элементы индексной строки симплекс-таблицы задачи максимизации неотрицательны, то базисный план этой задачи является оптимальным, а с 0 есть максимум целевой функции на множестве планов задачи.
Теорема 4 . (случай неограниченности целевой функции) . Если в индексной строке симплекс-таблицы задачи максимизации содержится отрицательный элемент с j , а в столбце неизвестного х j все элементы неположительны, то на множестве планов задачи целевая функция не ограничена сверху.
Симплекс-метод:
Записываем данную КЗЛП в исходную симплекс-таблицу.
Если все элементы индексной строки симплекс-таблицы неотрицательны, то базисный план задачи является оптимальным (теорема 3).
Если в индексной строке содержится отрицательный элемент, над которым в таблице нет ни одного положительного, то целевая функция не ограничена сверху на множестве планов и задача не имеет решений (теорема 4).
Если над каждым отрицательным элементом индексной строки имеется в таблице хотя бы один положительный, то следует перейти к новой симплекс-таблице, для которой базисный план не хуже предыдущего (теорема 2). С этой целью (см. доказательство теоремы 1)
выбираем в таблице ключевой столбец, в основании которого находится какой-либо отрицательный элемент индексной строки;
выделяем ключевое отношение (минимальное из отношений b i к положительным элементам ключевого столбца), знаменатель которого будет ключевым элементом;
составляем новую симплекс-таблицу; для этого делим ключевую строку (строку, в которой находится ключевой элемент) на ключевой элемент, а затем из всех остальных строк (включая индексную) вычитаем полученную строку, умноженную на соответствующий элемент ключевого столбца (чтобы все элементы этого столбца, кроме ключевого, стали равны 0).
При рассмотрении полученной симплекс-таблицы непременно представится один из трех случаев, описанных в пп. 2, 3, 4. Если при этом возникнут ситуации пп. 2 или 3, то процесс решения задачи завершается, если же возникнет ситуация п. 4, то процесс продолжается.
Если учесть, что число различных базисных планов конечно, то возможны два случая:
через конечное число шагов задача будет решена (возникнут ситуации пп. 2 или 3);
начиная с некоторого шага возникает зацикливание (периодическое повторение симплексных таблиц и базисных планов).
Эти задачи называются симметричными двойственными задачами . Отметим следующие особенности, связывающие эти задачи:
Одна из задач является задачей максимизации, а другая – минимизации.
В задаче максимизации все неравенства – ≤, а в задаче минимизации – ≥.
Число неизвестных одной задачи равно числу неравенств другой.
Матрицы коэффициентов при неизвестных в неравенствах обеих задач являются взаимно транспонированными.
Свободные члены неравенств одной из задач равны коэффициентам при соответствующих неизвестных в выражении целевой функции другой задачи.
Алгоритм построения двойственной задачи.
1. Привести все неравенства системы ограничений исходной задачи к одном смыслу – к каноническому виду.
2. Составить расширенную матрицу системы А, в которую включить столбец b i и коэффициенты целевой функции F.
3. Найти транспонированную матрицу А Т.
4. Записать двойственную задачу.
Теорема 5. Значение целевой функции задачи максимизации для любого ее плана не превосходит значения целевой функции двойственной к ней задачи минимизации для любого ее плана, т. е. имеет место неравенство:
f (x ) ≤ g (y ),
называемое основным неравенством двойственности .
Теорема 6. (достаточное условие оптимальности ). Если для некоторых планов двойственных задач значения целевых функций равны, то эти планы являются оптимальными.
Теорема 7. (основная теорема двойственности ). Если ЗЛП имеет конечный оптимум, то двойственная к ней также имеет конечный оптимум, и оптимальные значения целевых функций совпадают. Если целевая функция одной из двойственных задач не ограничена, то условия другой задачи противоречивы.
Теорема 8. (о дополняющей нежесткости ). Для того чтобы допустимые решения и двойственных задач являлись оптимальными, необходимо и достаточно, чтобы выполнялись следующие соотношения:
Ценности ресурсов прямой ЗЛП представляет собой значения переменных в оптимальном решении двойственной задачи.
Компоненты оптимального решения двойственной ЗЛП равны соответствующим элементам индексной строки оптимальной симплекс-таблицы прямой задачи, отвечающим дополнительным переменным.
Теорема 11. (критерий оптимальности плана транспортной задачи). Для того чтобы план перевозок) был оптимальным, необходимо и достаточно, чтобы существовали числа () и (), удовлетворяющие следующим условиям:
а) для всех базисных клеток плана (>0);
б) для всех свободных клеток (=0).
Метод потенциалов
Шаг 1. Проверить является ли данная транспортная задача закрытой. Если да, то перейти ко второму шагу. Если нет, то свести ее к закрытой задаче путем введения либо фиктивного поставщика, либо фиктивного потребителя.
Шаг 2. Найти исходное опорное решение (исходный опорный план) закрытой транспортной задачи.
Шаг 3. Проверить полученное опорное решение на оптимальность:
вычислить для него потенциалы поставщиков u i и потребителей v j
для всех свободных клеток (i , j ) вычислить оценки;
если все оценки неположительны (), то решение задачи окончено: исходный опорный план оптимален. Если среди оценок есть хотя бы одна положительная, то переходим к четвертому шагу.
Шаг 4. Выбрать клетку (i * ,j * ) с наибольшей положительной оценкой и для нее построить замкнутый цикл перераспределения груза. Цикл начинается и заканчивается в выбранной клетке. Получим новое опорное решение, в котором клетка (i * , j * ) окажется занятой. Возвращаемся к третьему шагу.
Через конечное число шагов будет получено оптимальное решение, т. е. оптимальный план перевозок продукции от поставщиков к потребителям.
Точка называется точкой локального максимума , если существует окрестность этой точки такая, что
Необходимые условия оптимальности
Для того, чтобы функция одной переменной имела в точке x * локальный экстремум, необходимо, чтобы производная функции в этой точке была равна нулю,
Для того, чтобы функция имела в точке локальный экстремум, необходимо, чтобы все ее частные производные в этой точке обращались в ноль
Если в точке x * первая производная функции равна нулю, а вторая производная >0, то функция в точке x * имеет локальный минимум, если 2 произв,<0 то функция в точке x * имеет локальный максимум.
Теорема 4. Если функция одной переменной имеет в точке x * производные до (n - 1) порядка, равные нулю, и производная n порялка не равна 0, то тогда,
если n четно, то точка x * является точкой минимума, если,fn(x)>0
точкой максимума, если fn(x)<0.
Если n нечетно, то точка x * – точка перегиба.
Числовая матрица называется матрицей квадратичной формы .
Квадратичная форма (5) называется положительно определенной , если для Q(X) >0 и отрицательно определенной , если для.Q(X)<0
Симметричная матрица A называется положительно определенной , если построенная по ней квадратичная форма (5) положительно определена.
Симметричная матрица называется отрицательно определенной , если построенная по ней квадратичная форма (6) отрицательно определена.
Критерий Сильвестра: матрица является положительно определенной, если все ее угловые миноры больше нуля.
Матрица является отрицательно определенной, если знаки угловых миноров чередуются.
Для того чтобы матрица была положительно определенной, необходимо, чтобы все ее собственные числа были больше нуля.
Собственные числа – корни многочлена .
Достаточное условие оптимальности задается следующей теоремой.
Теорема 5. Если в стационарной точке матрица Гессе положительно определена, то эта точка – точка локального минимума, если матрица Гессе отрицательно определена, то эта точка – точка локального максимума.
Конфликт - это противоречие, вызванное противоположными интересами сторон.
Конфликтная ситуация – ситуация, в которой участвуют стороны, интересы которых полностью или частично противоположны.
Игра - это действительный или формальный конфликт, в котором имеется по крайней мере два участника, каждый из которых стремится к достижению собственных целей
Правилами игры называют допустимые действия каждого из игроков, направленные на достижение некоторой цели.
Платежом называется количественная оценка результатов игры.
Парная игра – игра, в которой участвуют только две стороны (два игрока).
Игра с нулевой суммой или антагонистическая - парная игра, при которой сумма платежа равна нулю, т. е. если проигрыш одного игрока равен выигрышу другого.
Выбор и осуществление одного из действий, предусмотренных правилами, называется ходом игрока . Ходы могут быть личными и случайными.
Личный ход – это сознательный выбор игроком одного из возможных действий (например, ход в шахматной игре).
Случайный ход – это случайно выбранное действие (например, выбор карты из перетасованной колоды).
Стратегия игрока - это однозначный выбор игрока в каждой из возможных ситуаций, когда этот игрок должен сделать личный ход.
Оптимальная стратегия - это такая стратегия игрока, которая при многократном повторении игры обеспечивает ему максимально возможный средний выигрыш или минимально возможный средний проигрыш.
Платежная матрица – полученная матрица A или, иначе, матрица игр ы.
Конечной игрой размерности (m n) называется игра, определенная матрицей А размерности (m n).
Максимином или нижней ценой игры назовем число alpa = max(i)(min aij)(j)
а соответствующая ему стратегия (строка) максиминной .
Минимаксом или верхней ценой игры назовем число Beta = min(j)(max aij)i
а соответствующая ему стратегия (столбец) минимаксной .
Нижняя цена игры всегда не превосходит верхнюю цену игры.
Игрой с седловой точкой называется игра для которой. Alp = beta
Ценой игры называется величина, v если.v = alp = beta
Смешанной стратегией игрока называется вектор, каждая из компонент которого показывает относительную частоту использования игроком соответствующей чистой стратегии.
Теорема 2 . Основная теорема теории матричных игр.
Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.
Т 3
Если один из игроков применяет оптимальную смешанную стратегию, то его выигрыш равен цене игры в не зависимости от того, с какими частотами будет применять второй игрок свои стратегии (в том числе и чистые стратегии).
игрой с природой – игра, в которой мы не обладаем информацией о поведении партнера
Риском r ij игрока при выборе стратегии А i в условиях H j называется разность
r ij = b j - a i ,
где b j - максимальный элемент в j - м столбце.
Графом называется совокупность непустого множества, называемого
множеством вершин графа и множества пар вершин, которые называются
ребрами графа.
Если рассматриваемые пар вершин являются упорядоченными, то граф
называется ориентированным (орграф), в противном случае –
неориентированным. В
Маршрутом (путем) в графе, соединяющем вершины А и В, называется
последовательность ребер, первое из которых выходит из вершины А, начало
последующего совпадает с концом предыдущего, а последнее ребро входит в
вершину В.
Граф называется связным, если для любых двух его вершин существует путь,
их соединяющий. В противном случае граф называется несвязным.
Граф называется конечным, если число его вершин конечно.
Если вершина является началом или концом ребра, то вершина и ребро
называются инцидентными. Степенью (порядком) вершины называется число инцидентных ей ребер
Эйлеров путь (эйлерова цепь) в графе - это путь, проходящий по всем
рѐбрам графа и притом только по одному разу.
Эйлеров цикл - это эйлеров путь, являющийся циклом.
Эйлеров граф - граф, содержащий эйлеров цикл.
Полуэйлеров граф - граф, содержащий эйлеров путь (цепь).
Теорема Эйлера.
Эйлеров цикл существует тогда и только тогда, когда граф связный и в нѐм
отсутствуют вершины нечѐтной степени.
Теорема. Эйлеров путь в графе существует тогда и только тогда, когда граф
связный и число вершин нечѐтной степени равно нулю или двум.
Деревом называется связный граф без циклов, имеющий исходную вершину
(корень) и крайние вершины (степени 1); пути от исходной вершины к крайним вершинам называются ветвями.
Сетью (или сетевым графиком) называется ориентированный конечный
связный граф, имеющий начальную вершину (источник) и конечную вершину (сток).
Весом пути в графе будем называть сумму весов его ребер.
Кратчайшим путем из одной вершины в другую будем называть путь
минимального веса. Вес этого пути будем называть расстоянием между
вершинами.
Работа – это протяженный во времени процесс, требующий затрат ресурсов,
либо логическая зависимость между двумя или несколькими работами
Событие – результат выполнения одной или нескольких работ
Путь – это цепочка следующих друг за другом работ, соединяющих
начальную и конечную вершины.
Продолжительность пути определяется суммой продолжительностей
составляющих его работ.
Правила составления сетевых графиков.
1. В сетевом графике не должно быть тупиковых событий (кроме
завершающего), т. е. таких, за которыми не следует ни одной работы.
2. Не должно быть событий (кроме исходного), которым не предшествует хотя
бы одна работа.
3. В сетевом графике не должно быть циклов.
4. Любые два события связаны не более, чем одной работой.
5. Сетевой график должен быть упорядочен.
Любой путь, начало которого совпадает с исходным событием, а конец – с
завершающим, называется полным путем. Полный путь, имеющий максимальную
продолжительность работ, называется критическим путем
Иерархия есть определенный тип системы, основанный на предположении, что элементы системы могут группироваться в несвязанные множества
Описание метода анализа иерархий
Построение матриц парных сравнений
Находим лямбда макс и решаем систему относительно вектора весов
Синтез локальных приоритетов
Проверка согласованности матриц парных сравнений
Синтез глобальных приоритетов
Оценка согласованности всей иерархии
Тест по дисциплине «Исследование операций»
(верные ответы - первые)
1. Термин "исследование операций” появился …
в годы второй мировой войны
в 50-ые годы XX века
в 60-ые годы XX века
в 70-ые годы XX века
в 90-ые годы XX века
в начале XXI века
2. Под исследованием операций понимают (выберите наиболее подходящий вариант) …
комплекс научных методов для решения задач эффективного управления организационными системами
комплекс мер, предпринимаемых для реализации определенных операций
комплекс методов реализации задуманного плана
научные методы распределения ресурсов при организации производства
3. Упорядочьте этапы, через которые, как правило, проходит любое операционное исследование:
постановка задачи
построение содержательной (вербальной) модели рассматриваемого объекта (процесса)
построение математической модели
решение задач, сформулированных на базе построенной математической модели
проверка полученных результатов на адекватность природе изучаемой системы
реализация полученного решения на практике
4. В исследовании операций под операцией понимают…
всякое мероприятие (систему действий), объединенное единым замыслом и направленное на достижение какой-либо цели
всякое неуправляемое мероприятие
комплекс технических мероприятий, обеспечивающих производство продуктов потребления
5. Решение называют оптимальным, …
если оно по тем или иным признакам предпочтительнее других
если оно рационально
если оно согласовано с начальством
если оно утверждено общим собранием
6. Математическое программирование …
занимается изучением экстремальных задач и разработкой методов их решения
представляет собой процесс создания программ для компьютера под руководством математиков
занимается решением математических задач на компьютере
7. Задача линейного программирования состоит в …
отыскании наибольшего (наименьшего) значения линейной функции при наличии линейных ограничений
создании линейной программы на избранном языке программирования, предназначенной для решения поставленной задачи
описании линейного алгоритма решения заданной задачи
8. В задаче квадратичного программирования…
целевая функция является квадратичной
область допустимых решения является квадратом
ограничения содержат квадратичные функции
9. В задачах целочисленного программирования…
неизвестные могут принимать только целочисленные значения
целевая функция должна обязательно принять целое значение, а неизвестные могут быть любыми
целевой функцией является числовая константа
10. В задачах параметрического программирования…
целевая функция и/или система ограничений содержит параметр(ы)
область допустимых решения является параллелограммом или параллелепипедом
количество переменных может быть только четным
11. В задачах динамического программирования…
процесс нахождения решения является многоэтапным
необходимо рационализировать производство динамита
требуется оптимизировать использование динамиков
12. Поставлена следующая задача линейного программирования:
F (х 1, х 2) = 5х 1 + 6х 2→ mах
0.2х 1 + 0.3х 2 ≤ 1.8,
0.2х 1 + 0.1х 2 ≤ 1.2,
0.3х 1 + 0.3х 2 ≤ 2.4,
х 1 ≥ 0, х 2 ≥ 0.
Выберите задачу, которая эквивалентна этой задаче.
F (х 1, х 2)= 5х 1 + 6х 2 → mах ,
2х 1 + 3х 2 ≤ 18,
2х 1 + х 2 ≤ 12,
х 1 + х 2 ≤ 8,
х 1 ≥ 0,
х 2 ≥ 0.
F (х 1, х 2)= 6х 1 + 5х 2 → min,
2х 1 + 3х 2 ≤ 18,
2х 1 + х 2 ≤ 12,
х 1 + х 2 ≤ 8,
х 1 ≥ 0,
х 2 ≥ 0.
F (х 1, х 2)= 50х 1 + 60х 2 → mах ,
2х 1 + 3х 2 ≤ 18,
2х 1 + х 2 ≤ 12,
х 1 + х 2 ≤ 8,
х 1 ≥ 0,
х 2 ≥ 0.
F (х 1, х 2)= 5х 12 + 6х 22 → mах ,
2х 1 + 3х 2 ≤ 18,
2х 1 + х 2 ≤ 12,
3х 1 + х 2 ≤ 2.4,
х 1 ≥ 0,
х 2 ≥ 0.
13. Целевой функцией задачи линейного программирования может являться функция:
F =12x1 +20x2–3 0x3 →min
F = →min
F
=
→max
F =→max.
14. Системой ограничений задачи линейного программирования может являться система:
15. Симплекс-метод - это:
аналитический метод решения основной задачи линейного программирования
метод отыскания области допустимых решений задачи линейного программирования;
графический метод решения основной задачи линейного программирования;
метод приведения общей задачи линейного программирования к каноническому виду.
16. Задача линейного программирования состоит в:
отыскании наибольшего или наименьшего значения линейной функции при наличии линейных ограничений
разработке линейного алгоритма и реализации его на компьютере
составлении и решении системы линейных уравнений
поиске линейной траектории развития процесса, описываемого заданной системой ограничений.
17. Область допустимых решений задачи линейного программирования не может выглядеть так:
18. Целевой функцией задачи линейного программирования может являться функция:
F =12x1 +20x2–3 0x3 →min
F = →min
F
=→max
F =→max.
19.Системой ограничений задачи линейного программирования может являться система:
20. Область допустимых решений задачи линейного программирования имеет вид:
F (х 1, х 2)= 3х 1 + 5х 2 равно…
21. Область допустимых решений задачи линейного программирования имеет вид:
Тогда максимальное значение функции F (х 1, х 2)= 5х 1 + 3х 2 равно…
22. Область допустимых решений задачи линейного программирования имеет вид:
Тогда максимальное значение функции F (х 1, х 2)= 2х 1 - 2х 2 равно…
23. Область допустимых решений задачи линейного программирования имеет вид:
F (х 1, х 2)= 2х 1 - 2х 2 равно…
24. Область допустимых решений задачи нелинейного программирования имеет вид:
Тогда максимальное значение функции F (х 1, х 2)= х 2 – х 12 равно…
25. Максимальное значение целевой функции F
(х
1, х
2)= 5х
1 + 2х
2 при ограничениях
х
1 + х
2 ≤ 6,
х 1 ≤ 4,
х 1 ≥ 0, х 2 ≥ 0, равно …
26. Малое предприятие производит изделия двух видов. На изготовление одного изделия вида А расходуется 2 кг сырья, на изготовление одного изделия вида В – 1 кг. Всего имеется 60 кг сырья. Требуется составить план производства, обеспечивающий получение наибольшей выручки, если отпускная стоимость одного изделия вида А 3 д. е., вида В - 1 у. е., причем изделий вида А требуется изготовить не более 25, а вида В – не более 30.
Данная задача является …
задачей линейного программирования
задачей, решаемой методом динамического программирования
задачей сетевого планирования.
27. Малое предприятие производит изделия двух видов. На изготовление одного изделия вида А расходуется 2 кг сырья, на изготовление одного изделия вида В – 1 кг. Всего имеется 60 кг сырья. Требуется составить план производства, обеспечивающий получение наибольшей выручки, если отпускная стоимость одного изделия вида А 3 д. е., вида В - 1 у. е., причем изделий вида А требуется изготовить не более 25, а вида В – не более 30.
Целевой функцией данной задачи является функция …
F (x1,x2 )=3x1 +x2 →max
F (x1,x2 )=25x1 +30x2 →max
F (x1,x2 )=2x1 +x2 →max
F (x1,x2 )=60 -2x1 - x2 →min
28. Малое предприятие производит изделия двух видов. На изготовление одного изделия вида А расходуется 2 кг сырья, на изготовление одного изделия вида В – 1 кг. Всего имеется 60 кг сырья. Требуется составить план производства, обеспечивающий получение наибольшей выручки, если отпускная стоимость одного изделия вида А 3 д. е., вида В - 1 у. е., причем изделий вида А требуется изготовить не более 25, а вида В – не более 30
Допустимым планом данной задачи является план:
X= (20, 20)
X= (25, 15)
X= (20, 25)
X= (30, 10)
29. В двух пунктах А1 и А2 имеется соответственно 60 и 160 единиц товара. Весь товар нужно перевезти в пункты В1, В2, В3 в количестве 80, 70 и 70 единиц соответственно. Матрица тарифов такова: . Спланируйте перевозки так, чтобы их стоимость была минимальной.
Данная задача является …
транспортной задачей
задачей нелинейного программирования
задачей коммивояжера
задачей о назначениях
30. В двух пунктах А1 и А2 имеется соответственно 60 и 160 единиц товара. Весь товар нужно перевезти в пункты В1, В2, В3 в количестве 80, 70 и 70 единиц соответственно. Матрица тарифов такова: . Спланируйте перевозки так, чтобы их стоимость была минимальной
Опорным планом данной задачи является план:
;
31. В двух пунктах А1 и А2 имеется соответственно 60 и 160 единиц товара. Весь товар нужно перевезти в пункты В1, В2, В3 в количестве 80, 70 и 70 единиц соответственно. Матрица тарифов такова: . Спланируйте перевозки так, чтобы их стоимость была минимальной.
Целевой функцией данной задачи является функция:
F =4x11 +6x12+ 8x13 +5x21 +8x22 +7x23 →min
F = →min
F =60x1 +160x2+ 80x3 +70x4 +705 →max
F =60x1 +160x2– 80x3– 70x4– 705 →min
32. В двух пунктах А1 и А2 имеется соответственно 60 и 160 единиц товара. Весь товар нужно перевезти в пункты В1, В2, В3 в количестве 80, 70 и 70 единиц соответственно. Матрица тарифов такова: . Спланируйте перевозки так, чтобы их стоимость была минимальной.
Оптимальным планом данной задачи является план:
;
.
;
;
33. Транспортная задача
будет закрытой, если…
34. Транспортная задача
является…
открытой
закрытой
неразрешимой
35. Транспортная задача
является…
закрытой
открытой
неразрешимой
36. Для решения следующей транспортной задачи
необходимо ввести…
фиктивного потребителя
фиктивного поставщика;
эффективный тариф
37. Для решения следующей транспортной задачи
необходимо ввести…
фиктивного поставщика;
фиктивного потребителя
эффективный тариф
эффективную процентную ставку.
38. Среди данных транспортных задач
закрытыми являются…
39. Исходный опорный план транспортной задачи можно составить…
всеми перечисленными методами
методом северо-западного угла
методом минимального тарифа
методом двойного предпочтения
методом аппроксимации Фогеля
40. Если целевая функция задачи линейного программирования задана на максимум, то… целевая функция двойственной задачи задается на минимум
целевая функция в двойственной задаче отсутствует
двойственная задача не имеет решений
двойственная задача имеет бесконечно много решений
41. Дана задача линейного программирования:
F (х 1, х 2)= 2х 1 + 7х 2 → mах ,
2х 1 + 3х 2 ≤ 14,
х 1 + х 2 ≤ 8,
х 1 ≥ 0, х 2 ≥ 0.
Двойственной для этой задачи будет следующая…
F* (y1, y2)= 14y1 + 8y2 → min ,
3y 1 + y2 ³ 7,
y 1 ≥ 0, y2 ≥ 0.
F* (y1, y2)= 2y1 + 7y2 → min ,
2y1 + 3y2 ³ 14,
y 1 + y2 ³ 8,
y 1 £ 0, y2 £ 0.
F* (y1, y2)= 2y1 + 7y2 → min ,
3 y 1 + y2 ³ 7,
y 1 £ 0, y2 £ 0.
F* (y1, y2)= 14y1 + 8y2 → min ,
y 1 + y2 ³ 7,
y 1 ≥ 0, y2 ≥ 0.
42. Если одна из пары двойственных задач имеет оптимальный план, то…
и другая имеет оптимальный план
другая не имеет оптимального плана
другая не имеет допустимых решений
43. Если одна из пары двойственных задач имеет оптимальный план, то…
и другая имеет оптимальный план и значения целевых функций при их оптимальных планах равны между собой
и другая имеет оптимальный план, но значения целевых функций при их оптимальных планах не равны между собой
другая задача может не иметь оптимального плана, но иметь допустимые решения
44. Если целевая функция одной из пары двойственных задач не ограничена (для задачи на максимум – сверху, для задачи на минимум - снизу), то
другая задача не имеет допустимых планов
другая задача имеет допустимые планы, но не имеет оптимального плана
целевая функция другой задачи также не ограничена
45. При решении некоторых задач нелинейного программирования применяется …
метод множителей Лагранжа
метод Гаусса
метод аппроксимации Фогеля
метод Гомори
46. Задана задача нелинейного программирования
F (х 1, х 2)= х 12 + х 22 → mах ,
х 1 + х 2 =6,
х 1 ≥ 0, х 2 ≥ 0.
F (х 1, х 2) …
не достижимо (+ ¥)
47. Задана задача нелинейного программирования
F (х 1, х 2)= х 12 + х 22 → m in ,
х 1 + х 2 =6,
х 1 ≥ 0, х 2 ≥ 0.
F (х 1, х 2) …
48. Задана задача нелинейного программирования
F (х 1, х 2)= х 12 + х 22 → mах ,
х 1 + х 2 =6,
х 1, х 2 - любые.
Наибольшее значение целевой функции F (х 1, х 2) …
не достижимо (+ ¥)
49. Задана задача нелинейного программирования
F (х 1, х 2)= х 12 + х 22 → m in ,
х 1 + х 2 =6,
х 1, х 2 - любые.
Наименьшее значение целевой функции F (х 1, х 2) …
не достижимо (- ¥)
50. Область допустимых решений задачи нелинейного программирования имеет вид:
Тогда максимальное значение функции F (х 1, х 2)= х 12 +х 22 равно…
51. Область допустимых решений задачи нелинейного программирования имеет вид:
Тогда минимальное значение функции F (х 1, х 2)= х 12 +х 22 равно…
52. Для решения транспортной задачи может применяться…
метод потенциалов
метод множителей Лагранжа
метод Гаусса
метод дезориентации
53. В системе ограничений общей задачи линейного программирования …
54. В системе ограничений стандартной (симметричной) задачи линейного программирования …
могут присутствовать только неравенства
могут присутствовать и уравнения, и неравенства
могут присутствовать только уравнения
55. В системе ограничений канонической (основной) задачи линейного программирования …
могут присутствовать только уравнения (при условии неотрицательности переменных)
могут присутствовать только неравенства (при условии неотрицательности переменных)
могут присутствовать и уравнения, и неравенства (при условии неотрицательности переменных)
56. Задача линейного программирования
F (х 1, х 2)= 2х 1 + 7х 2 → mах ,
2х 1 + 3х 2 ≤ 14,
х 1 + х 2 ≤ 8,
х 1 ≥ 0, х 2 ≥ 0.
записана в …
стандартной (симметричной) форме
канонической (основной) форме
словесной форме
57. Для записи задачи
F (х 1, х 2)= 2х 1 + 7х 2 → mах ,
2х 1 + 3х 2 ≤ 14,
х 1 + х 2 ≤ 8,
х 1 ≥ 0, х 2 ≥ 0.
в канонической форме …
58. Для записи задачи
F (х 1, х 2)= 2х 1 + 7х 2 → mах ,
2х 1 + 3х 2 ≤ 14,
х 1 + х 2 ≤ 8,
х 1 + 4х 2 ≥ 10,
х 1 ≥ 0, х 2 ≥ 0.
в канонической форме …
необходимо ввести три дополнительных неотрицательных переменных
необходимо ввести две дополнительных неотрицательных переменных
необходимо ввести четыре дополнительных неотрицательных переменных
59. Для записи задачи
F (х 1, х 2)= 2х 1 + 7х 2 → mах ,
2х 1 + 3х 2 = 14,
х 1 + х 2 ≤ 8,
х 1 + 4х 2 ≥ 10,
х 1 ≥ 0, х 2 ≥ 0.
в канонической форме …
необходимо ввести две дополнительных неотрицательных переменных
необходимо ввести три дополнительных неотрицательных переменных
необходимо ввести четыре дополнительных неотрицательных переменных
необходимо ввести пять дополнительных неотрицательных переменных
60. При решении задач целочисленного программирования может применяться …
метод Гомори
метод множителей Лагранжа
метод Гаусса
метод аппроксимации Фогеля
61. В основе решения задач методом динамического программирования лежит…
принцип «бритва Оккама»
принцип «зуб - за зуб, око - за око»
принцип Гейзенберга
62 . Ситуация, в которой участвуют стороны, интересы которых полностью или частично противоположны, называется …
(конфликтной, конфликтная, конфликт, конфликтом)
63. Действительный или формальный конфликт, в котором имеется по крайней мере два участника (игрока), каждый из которых стремится к достижению собственных целей, называется …
(игра, игрой)
64. Допустимые действия каждого из игроков, направленные на достижение некоторой цели, называются …
(правила игры, правилами игры)
65. Количественная оценка результатов игры называется …
(платежом, платеж, платёж)
66. Если в игре участвует только две стороны (два лица), то игра называется…
(парной, парная, парной игрой, парная игра)
67. Если в парной игре сумма платежей равна нулю, то есть проигрыш одного игрока равен выигрышу другого, то игра называется игрой…
(с нулевой суммой)
68. Однозначное описание выбора игрока в каждой из возможных ситуаций, при которой он должен сделать личный ход, называется..
(стратегией игрока, стратегия игрока, стратегией, стратегия)
69. Если при многократном повторении игры стратегия обеспечивает игроку максимально возможный средний выигрыш (минимально возможный средний проигрыш), то такая стратегия называется…
(оптимальной, оптимальная, оптимальной стратегией, оптимальная стратегия)
70. Пусть a - нижняя цена, а b - верхняя цена парной игры с нулевой суммой. Тогда верно утверждение…
71. Пусть a - нижняя цена, а b - верхняя цена парной игры с нулевой суммой. Если a = b = v, то число v называется …
ценой игры
точкой равновесия
оптимальной стратегией
смешанной стратегией
72. Пусть a - нижняя цена, а b - верхняя цена парной игры с нулевой суммой. Если a = b, то игра называется…
игрой с седловой точкой
неразрешимым конфликтом
игрой без правил
73. Вектор, каждая из компонент которого показывает относительную частоту использования игроком соответствующей чистой стратегии, называется…
смешенной стратегией
направляющим вектором
вектором нормали
градиентом
74. Нижняя цена матричной игры, заданной платежной матрицей , равна…
Больше нижней цены
равна нижней цене
не существует
81. Матричная игра, заданная платежной матрицей , …
имеет седловую точку
не имеет седловой точки
не является парной
82. Цена игры, заданной платежной матрицей , равна…
83. Матричная игра, заданная платежной матрицей , …
является парной
имеет седловую точку
не является парной
84. Парная игра с нулевой суммой, заданная своей платежной матрицей, может быть сведена к …
задаче линейного программирования
задаче нелинейного программирования
целочисленной задаче линейного программирования
классической задаче оптимизации
85. Нижняя цена матричной игры, заданной платежной матрицей , равна…
Больше нижней цены
равна нижней цене
не существует
92. Матричная игра, заданная платежной матрицей , …
не имеет седловой точки
имеет седловую точку
не является парной
93. Цена игры, заданной платежной матрицей , заключена в пределах…
94. Если в потоке событий события следуют одно за другим через заранее заданные и строго определенные промежутки времени, то такой поток называется …
регулярным
организованным
95. Если вероятность попадания любого числа событий на промежуток времени зависит только от длины этого промежутка и не зависит от того, как далеко расположен этот промежуток от начала отсчета времени, то соответствующий поток событий называется:
стационарным
потоком без последствий
простейшим
пуассоновским
96. Если число событий, попадающих на один из произвольно выбранных промежутков времени, не зависит от числа событий, попавших на другой, также произвольно выбранный промежуток времени при условии, что эти промежутки не пересекаются, то соответствующий поток событий называется …
потоком без последствий
регулярным
показательным
нормальным
97. Если вероятность попадания на очень малый отрезок времени сразу двух или более событий пренебрежимо мала по сравнению с вероятностью попадания только одного события, то соответствующий поток событий называется…
ординарным
неординарным
нормальным
пуассоновским
98. Если поток событий одновременно обладает свойствами стационарности, ординарности и отсутствием последствия, то он называется:
простейшим (пуассоновским)
нормальным
99. Одноканальная СМО с отказами представляет собой пост ежедневного обслуживания для мойки автомобилей. Заявка - автомобиль, прибывший в момент, когда пост занят, - получает отказ в обслуживании. Интенсивность потока автомобилей λ=1,0 (автомобиль в час). Средняя продолжительность обслуживания - 1,8 часа. Поток автомобилей и поток обслуживания являются простейшими. Тогда в установившемся режиме относительная пропускная способность q равна…
100. Одноканальная СМО с отказами представляет собой пост ежедневного обслуживания для мойки автомобилей. Заявка - автомобиль, прибывший в момент, когда пост занят, - получает отказ в обслуживании. Интенсивность потока автомобилей λ=1,0 (автомобиль в час). Средняя продолжительность обслуживания - 1,8 часа. Поток автомобилей и поток обслуживания являются простейшими. Тогда в установившемся режиме процент автомобилей, получающих отказ в обслуживании, равен…
