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

Обобщением понятия отрезка для нескольких точек является их выпуклая линейная комбинация.

Точка Х называетсявыпуклой линейной комбинацией точек , если выполняются условия

Множество точек являетсявыпуклым, если оно вместе с лю­быми своими двумя точками содержит их произвольную выпуклую, линейную комбинацию.

Можно доказать следующую теорему о представлении выпуклого многогран­ника.

Теорема 1.1. Выпуклый п-мерный многогранник является выпук­лой линейной комбинацией своих угловых точек.

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

Свойства задачи линейного программирования. Ранее были рассмотрены различные формы задачи линей­ного программирования и показано, что любая задача линейного программирования может быть представлена в виде общей или канонической задачи.

Для обоснования свойств задачи линейного программирования и методов ее решения целесообразно рассмотреть еще два вида записи канонической задачи.

Матричная форма записи:

Здесь С – матрица-строка, А – матрица системы, Х – матри­ца-столбец переменных, В – матрица-столбец свободных членов:

Векторная форма записи:

где векторы соответствуют столбцам коэффициентов при неизвестных.

Выше была сформулирована, но не доказана в общем виде следующая теорема.

Теорема 1.2. Множество всех допустимых решений системы ог­раничений задачи линейного программирования является выпуклым.

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

и покажем, что она также является допустимым решением систе­мы (1.3). В самом деле

т.e. решение X удовлетворяет системе (1.3). Но так как , то и Х >0, т.е. решение удовлетворяет условию неотрицательности.

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

Ответ на вопрос, в какой точке многогранника решений воз­можно оптимальное решение задачи линейного программирова­ния, дается в следующей фундаментальной теореме.

Теорема 1.3. Если задача линейного программирования имеет оп­тимальное решение, то линейная функция принимает максимальное значение в одной из угловых точек многогранника решений. Если ли­нейная функция принимает максимальное значение более чем в одной угловой точке, то она принимает его в любой точке, являющейся выпуклой линейной комбинацией этих точек.

Доказательство: Будем полагать, что многогранник решений является огра­ниченным. Обозначим его угловые точки через , а оптимальное решение - через X* . Тогда F(X*) ³ F(X) для всех то­чек Х многогранника реше­ний. Если X* – угловая точка, то первая часть тео­ремы доказана.

Предположим, что X* не является угловой точкой, тогда на основании теоре­мы 1.1 X* можно предста­вить как выпуклую линей­ную комбинацию угловых точек многогранника ре­шений, т.е.

Так как F(X) – линейная функция, получаем

В этом разложении среди значений выбе­рем максимальное. Пусть оно соответствует угловой точке X k (1 £ k £ р) ; обозначим его через М, т.е. . Заменим в выражении (1.5) каждое значение этим максимальным значением М. Тогда

По предположению Х * – оптимальное решение, поэтому, с одной стороны, ,но, с другой стороны, доказано, что
F(X*) £ М, следовательно, , где X k – угловая точка. Итак, существует угловая точка X k , в которой линейная функция принимает максимальное значение.

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

Пусть Х – выпуклая линейная комбинация этих угловых точек, т.е.

В этом случае, учитывая, что функция F(X) – линейная, полу­чим

т.е. линейная функция F принимает максимальное значение в произвольной точкеХ , являющейся выпуклой линейной комбинацией угловых точек.

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

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

Следующая теорема посвящена аналитическому методу нахождения угловых точек.

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

Доказательство: Пусть – допустимое базисное решение системы ограничений ЗЛП (1.4), в котором первые т компонент - основные переменные, а остальные п - т компо­нент – неосновные переменные, равные нулю в базисном реше­нии (если это не так, то соответствующие переменные можно перенумеровать). Покажем, что Х

Предположим противное, т.е. что Х не является угловой точ­кой. Тогда точку Х можно представить внутренней точкой отрез­ка, соединяющего две различные, не совпадающие с X, точки

другими словами, – выпуклой линейной комбинацией точек многогранника решений, т.е.

где (полагаем, что , ибо в противном случае точка Х совпадает с точкой Х 1 или Х 2).

Запишем векторное равенство (1.6) в координатной форме:

Т.к. все переменные и коэффициенты неотрицательны, то из последних п-т равенств следует, что , т.е. в решениях Х 1 , Х 2 и Х системы уравнений (1.4) значения п - т компонент равны в данном случае нулю. Эти компоненты можно считать значениями неосновных переменных. Но значения неосновных переменных однозначно определяют значения основных, следовательно,

Таким образом, все п компонент в решениях Х 1 , Х 2 и Х совпада­ют, и значит, точки Х 1 и Х 2 сливаются, что противоречит допуще­нию. Следовательно, X – угловая точка многогранника решений.

Докажем обратное утверждение. Пусть – угловая точка многогранника решений и первые ее т координат положительны. Покажем, что Х – допустимое базис­ное решение. не является угловой точкой, что противоречит условию. Следовательно, наше допуще­ние неверно, т.е. векторы линейно независимы и Х – допустимое базисное решение задачи (1.4).

Из теорем 1.3 и 1.4 непосредственно вытекает важное следст­вие: если задача линейного программирования имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допусти­мых базисных решений.

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

Составляющие математической модели

Основой для решения экономических задач являются математические модели.

Математической моделью задачи называется совокупность математических соотношений, описывающих суть задачи.

Составление математической модели включает:

• выбор переменных задачи
• составление системы ограничений
• выбор целевой функции

Переменными задачи называются величины Х1, Х2, Хn, которые полностью характеризуют экономический процесс. Обычно их записывают в виде вектора: X=(X1, X2,...,Xn).

Системой ограничений задачи называют совокупность уравнений и неравенств, описывающих ограниченность ресурсов в рассматриваемой задаче.

Целевой функцией задачи называют функцию переменных задачи, которая характеризует качество выполнения задачи и экстремум которой требуется найти.

В общем случае задача линейного программирования может быть записана в таком виде:

Данная запись означает следующее: найти экстремум целевой функции (1) и соответствующие ему переменные X=(X1, X2,...,Xn) при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3).

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X1, X2,...,Xn), удовлетворяющий системе ограничений и условиям неотрицательности.

Множество допустимых решений (планов) задачи образует область допустимых решений (ОДР).

Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение (план) задачи, при котором целевая функция достигает экстремума.

Пример составления математической моделиЗадача использования ресурсов (сырья)

Условие: Для изготовления n видов продукции используется m видов ресурсов. Составить математическую модель.

Известны:

• bi (i = 1,2,3,...,m) - запасы каждого i-го вида ресурса;
• aij (i = 1,2,3,...,m; j=1,2,3,...,n) - затраты каждого i-го вида ресурса на производство единицы объема j-го вида продукции;
• cj (j = 1,2,3,...,n) - прибыль от реализации единицы объема j-го вида продукции.

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

Решение:

Введем вектор переменных X=(X1, X2,...,Xn), где xj (j = 1,2,...,n) - объем производства j-го вида продукции.

Затраты i-го вида ресурса на изготовление данного объема xj продукции равны aijxj, поэтому ограничение на использование ресурсов на производство всех видов продукции имеет вид:
Прибыль от реализации j-го вида продукции равна cjxj, поэтому целевая функция равна:

Ответ - Математическая модель имеет вид:

Каноническая форма задачи линейного программирования

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

В том случае, когда все ограничения являются уравнениями и все переменные удовлетворяют условию неотрицательности, задачу линейного программирования называют канонической.

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

Каноническая задача линейного программирования в координатной записи имеет вид:

Каноническая задача линейного программирования в матричной записи имеет вид:

• А - матрица коэффициентов системы уравнений
• Х - матрица-столбец переменных задачи
• Ао - матрица-столбец правых частей системы ограничений

Нередко используются задачи линейного программирования, называемые симметричными, которые в матричной записи имеют вид:

Приведение общей задачи линейного программирования к канонической форме

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

Это может быть сделано следующим образом:

Возьмем линейное неравенство a1x1+a2x2+...+anxn≤b и прибавим к его левой части некоторую величину xn+1, такую, что неравенство превратилось в равенство a1x1+a2x2+...+anxn+xn+1=b. При этом данная величина xn+1 является неотрицательной.

Рассмотрим все на примере.

Пример 26.1

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

Решение:
Перейдем к задаче на отыскивание максимума целевой функции.
Для этого изменим знаки коэффициентов целевой функции.
Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x4 x5 (на математической модели эта операция отмечена буквой Д).
Переменная х4 вводится в левую часть второго неравенства со знаком "+", так как неравенство имеет вид "≤".
Переменная x5 вводится в левую часть третьего неравенства со знаком "-", так как неравенство имеет вид "≥".
В целевую функцию переменные x4 x5 вводятся с коэффициентом. равным нулю.
Записываем задачу в каноническом виде:

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

Таким образом, общая задача линейного программирования (ЗЛП) может быть сформулирована следующим образом.

Найти такие значения действительных переменных , для которых целевая функция

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

Как известно, упорядоченная совокупность значений n переменных , , … представляется точкой n-мерного пространства . В дальнейшем эту точку будем обозначать Х =( , , … ).

В матричном виде задачу линейного программирования можно сформулировать так:

, A – матрица размера ,

Точка Х =( , , … ), удовлетворяющая всем условиям, называется допустимой точкой . Множество всех допустимых точек называется допустимой областью .

Оптимальным решением (оптимальным планом) задачи линейного программирования называется решение Х =( , , … ), принадлежащее допустимой области и при котором линейная функция Q принимает оптимальное (максимальное или минимальное) значение.

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

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

Точка Х называется выпуклой линейной комбинацией точек если выполняются условия

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

Теорема . Если ЗЛП имеет оптимальное решение, то целевая функция принимает максимальное (минимальное) значение в одной из вершин многогранника решений. Если целевая функция принимает максимальное (минимальное) значение более чем в одной точке, то она принимает это значение в любой точке, являющейся выпуклой линейной комбинацией этих точек.

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

Базисным решением системы m линейных уравнений с n переменными называется решение, в котором все n-m неосновных переменных равны нулю. В задачах линейного программирования такие решения называют допустимыми базисными решениями (опорными планами).

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

Из приведенных теорем вытекает важное следствие:

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

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

Определение . Любое решение системы ограничений называется допустимым решением ЗЛП.
Определение . Допустимое решение, в котором целевая функция достигает максимального или минимального значения, называется оптимальным решением.

В силу этих определений задача ЛП может быть сформулирована следующим образом: среди всех точек выпуклой области, являющейся решением системы ограничений, выбрать такую, координаты которой минимизируют (максимизируют) линейную функцию F = с 1 x + с 2 y .
Заметим, что переменные x , y в ЗЛП принимают, как правило, неотрицательные значения (x ≥ 0, y ≥ 0), поэтому область расположена в I четверти координатной плоскости.

Рассмотрим линейную функцию F = с 1 x + с 2 y и зафиксируем какое-нибудь ее значение F . Пусть, к примеру, F = 0, т.е. с 1 x + с 2 y = 0. Графиком этого уравнения будет прямая, проходящая через начало координат (0;0) (рис.).
Рисунок
При изменении этого фиксированного значения F = d , прямая с 1 x + с 2 y = d будет смещаться параллельно и «зачертит» всю плоскость. Пусть D – многоугольник – область решения системы ограничений. При изменении d прямая с 1 x + с 2 y = d , при некотором значении d = d 1 достигнет многоугольника D , назовем эту точку А «точкой входа», и затем, пройдя многоугольник, при некотором значении d = d 2 будем иметь с ним последнюю общую точку В , назовем В «точкой выхода».
Очевидно, что своего наименьшего и наибольшего значения целевая функция F =с 1 x + с 2 y достигнет в точках «входа» А и «выхода» В .
Учитывая, что оптимальное значение на множестве допустимых решений целевая функция принимает в вершинах области D , можно предложить следующий план решения ЗЛП:

1. построить область решений системы ограничений;
2. построить прямую, соответствующую целевой функции, и параллельным переносом этой прямой найти точку «входа» или «выхода» (в зависимости от требования минимизировать или максимизировать целевую функцию);
3. определить координаты этой точки, вычислить в них значение целевой функции.

Заметим, что вектор (с 1 , с 2), перпендикулярный прямой, показывает направление роста целевой функции.

При графическом решении ЗЛП возможны два случая, которые требуют особого обсуждения.

Случай 1
Рисунок 6
При перемещении прямой с 1 x + с 2 y = d «вход» или «выход» (как на рисунке) произойдет по стороне многоугольника. Это случится, если в многоугольнике есть стороны, параллельные прямой с 1 х + с 2 у = d .
В этом случае точек «выхода» (« входа») бесчисленное множество, а именно – любая точка отрезка АВ . Это означает, что целевая функция принимает максимальное(минимальное) значение не в одной точке, а во всех точках, лежащих на соответствующей стороне многоугольника D .

Случай 2
Рассмотрим случай, когда область допустимых значений неограниченна.
В случае неограниченной области целевая функция может быть задана таким образом, что соответствующая ей прямая не имеет точки «выхода» (или «входа»). Тогда максимальное значение функции (минимальное) не достигается никогда – говорят, что функция не ограничена.
Рисунок
Необходимо найти максимальное значение целевой функции F = 4x + 6y → max , при системе ограничений
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами.
x + y = 18

x	12	9
y	6	9

0,5x + y = 12

x	12	18
y	6	3

x = 12 – параллельна оси OY ;
y = 9 – параллельна оси OX ;
x = 0 – ось OY ;
y = 0 – ось OX ;
x OY ;
y ≥ 0 – полуплоскость выше оси OX ;
y ≤ 9 – полуплоскость ниже y = 9;
x ≤ 12 – полуплоскость левее x = 12;
0,5x + y x + y = 12;
x + y x + y = 18.
Рисунок
Пересечением всех этих полуплоскостей является очевидно, пятиугольник ОАВСД , с вершинами в точках О (0; 0), А (0; 9), В (6; 9), С (12; 6), Д (12; 0). Этот пятиугольник и образует область допустимых решений задачи.

F = 4x + 6y → max.

x	3	0
y	–2	0

F = 0: 4x + 6y x + 6y С (12; 6). Именно в ней F = 4x + 6y
Значит, при x = 12, y = 6 функция F F = 4 ∙ 12 + 6 ∙ 6 = 84, равного 84. Точка с координатами (12; 6) удовлетворяет всем неравенствам системы ограничений, и в ней значение целевой функции оптимально F * = 84 (оптимальное значение будем обозначать «*»).
Задача решена. Итак, необходимо выпустить 12 изделий I вида и 6 изделий II вида, при этом прибыль составит 84 тыс. руб.

Графический метод применяется для решения задач, которые имели в системе ограничений только две переменные. Этот метод может применяться и для систем неравенств, имеющих три переменных. Геометрически ситуация будет иная, роль прямых будут играть плоскости в трехмерном пространстве, а решением неравенства от трех переменных будет являться полупространство, находящееся по одну сторону от плоскости. Роль областей будут играть многогранники, являющиеся пересечением полупространств.

Пример №2 . Шахта разрабатывает два пласта. Выход штыба по первому пласту составляет а1 %; по второму - а2 %. Максимальная производительность очистного забоя по первому пласту составляет В1 тыс.тонн в год, по второму пласту - В2 тыс.тонн в год. По технологии работ добыча со второго пласта не может превышать добычу с первого пласта. Выход штыба по шахте не должен превышать С1 тыс.тонн в год. Общая нагрузка по двум пластам за год должна быть не меньше С2 тыс.тонн в год. Составить математическую модель и построить множество допустимых значений нагрузки по первому и второму пластам за год.

Пример №3 . Магазин продает 2 вида безалкогольных напитков: Колу и лимонад. Доход от одной банки колы составляет 5 центов, тогда как доход от одной банки лимонада 7 центов. В среднем магазин за день продает не более 500 банок обоих напитков. Несмотря на то, что колу выпускает известная торговая марка, покупатели предпочитают лимонад, поскольку он значительно дешевле. Подсчитано, что объем продаж колы и лимонада должны соотноситься не менее 2:1 кроме того, известно что магазин продает не менее 100 банок колы в день. Сколько банок каждого напитка должен иметь магазин в начале рабочего дня для максимизации дохода?

Пример №4 . Решить задачу линейного программирования приближенно графическим способом с последующим вычислением точного значения и мах(min) значения целевой функции.

Пример №5 . Туристской фирме требуется не более а трехтонных автобусов и не более в пятитонных автобусов. Отпускная цена автобусов первой марки 20000 у.е., второй марки 40000 у.е. Туристская фирма может выделить для приобретения автобусов не более с у.е. Сколько следует приобрести автобусов каждой марки в отдельности, чтобы их общая (суммарная) грузоподъёмность была максимальной. Решить задачу графическим методом.

Пример №6 . Используя графический метод, найдите оптимальный производственный план в задаче, заданной таблицей.

Пример №7 . Решить графическим методом задачу линейного программирования, подвергнув систему ограничений задачи преобразованиям Жордано-Гаусса. Система ограничений задачи имеет вид:
a 11 x 1 + a 12 x 2 + a 13 x 3 + a 14 x 4 + a 15 x 5 = b 1
a 21 x 1 + a 22 x 2 + a 23 x 3 + a 24 x 4 + a 25 x 5 = b 2
a 31 x 1 + a 32 x 2 + a 33 x 3 + a 34 x 4 + a 35 x 5 = b 3
Методические рекомендации . Преобразования Жордано-Гаусса можно выполнить с помощью этого сервиса или через исследование СЛАУ .

Пример №8 . Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов. На изготовление единицы изделия А требуется затратить сырья каждого вида а1, а2, а3 кг соответственно, а для единицы изделия В - в1, в2, в3 кг. Производство обеспечено сырьем каждого вида в количестве Р1, Р2, Р3 кг, соответственно. Стоимость единицы изделия А составляет С1 руб., а единицы изделия В - С2 руб. Требуется составить план производства изделий А и В, обеспечивающий максимальную стоимость готовой продукции.

Пример №2 . Необходимо найти максимальное значение целевой функции F = 4x + 6y → max, при системе ограничений:

Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого выбираем количество ограничений равное 4 (рисунок 1).
Рисунок 1

Затем заполняем коэффициенты при переменных и сами ограничения (рисунок 2).
Рисунок 2

Рисунок 3
x = 12 – параллельна оси OY ;
y = 9 – параллельна оси OX ;
x > = 0 – ось OY
y = 0 – ось OX ;
x ≥ 0 – полуплоскость правее оси OY ;
y ≥0 – полуплоскость выше оси OX ;
y ≤ 9 – полуплоскость ниже y = 9;
x ≤ 12 – полуплоскость левее x = 12;
0,5x + y ≤ 12 – полуплоскость ниже прямой 0,5x + y = 12;
x + y ≤ 18 – полуплоскость ниже прямой x + y = 18.

Пересечением всех этих полуплоскостей является пятиугольник ABCDE , с вершинами в точках A (0; 0), B (0;9), C (6; 9), D (12;6), E (12;0). Этот пятиугольник и образует область допустимых решений задачи.

Рассмотрим целевую функцию задачи F = 4x + 6y → max.

x	3	0
y	–2	0

Построим прямую, отвечающую значению функции F = 0: 4x + 6y = 0. Будем двигать эту прямую параллельным образом. Из всего семейства прямых 4x + 6y = const последней вершиной, через которую пройдет прямая при выходе за границу многоугольника, будет вершина С (12; 6). Именно в ней F = 4x + 6y достигнет своего максимального значения.

Значит, при x = 12, y = 6 функция F достигает своего максимального значения F = 4 ∙ 12 + 6 ∙ 6 = 84, равного 84. Точка с координатами (12;6) удовлетворяет всем неравенствам системы ограничений, и в ней значение целевой функции оптимально F * = 84.

Тест по дисциплине «Исследование операций»

(верные ответы - первые)

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 часа. Поток автомобилей и поток обслуживания являются простейшими. Тогда в установившемся режиме процент автомобилей, получающих отказ в обслуживании, равен…