Главная / Алгоритмы и дискретные структуры /
Введение в математическое программирование / Тест 6
Введение в математическое программирование - тест 6
Упражнение 1:
Номер 1
В отличии от прямого симплекс – метода, двойственный симплекс – метод:
Ответ:
 (1) требует нахождения начального базисного решения 
 (2) не требует нахождения начального базисного решения 
 (3) требует дополнительного исследования начального базисного решения 
Номер 2
Если симплекс – метод не требует нахождения начального базисного решения (опорного плана), то он является:
Ответ:
 (1) прямым 
 (2) двойственным 
 (3) методом полного исключения 
Номер 3
Двойственный симплекс – метод, в отличии от прямого, не требует:
Ответ:
 (1) нахождения начального базисного решения 
 (2) определения вектора, вводимого в базис 
 (3) поиска начального псевдоплана 
Упражнение 2:
Номер 1
Если x'
и y'
– допустимые решения пары двойственных задач и при
этом выполняется равенство
Σcjx'j+Σcj(x'j–x'j+n2) = Σbiy'i + Σbi(y'i–y'i+m2)
,
то x'
и y'
:
Ответ:
 (1) оптимальные решения прямой задачи 
 (2) оптимальные решения двойственной задачи 
 (3) оптимальные решения пары двойственных задач 
Номер 2
Если x'
и y'
– оптимальные решения пары двойственных задач и при
этом выполняется равенство
Σcjx'j+Σcj(x'j–x'j+n2) = Σbiy'i + Σbi(y'i–y'i+m2)
,
то x'
и y'
:
Ответ:
 (1) допустимые решения пары двойственных задач 
 (2) допустимые решения двойственной задачи 
 (3) допустимые решения прямой задачи 
Номер 3
Если x'
и y'
– допустимые решения пары двойственных задач и при этом
они являются оптимальными решениями этих задач, то выполняется условие:
Ответ:
 (1) Σcjx'j+Σcj(x'j–x'j+n2) ≥ Σbiy'i + Σbi(y'i–y'i+m2)
 
 (2) Σcjx'j+Σcj(x'j–x'j+n2) ≤ Σbiy'i + Σbi(y'i–y'i+m2)
 
 (3) Σcjx'j+Σcj(x'j–x'j+n2) = Σbiy'i + Σbi(y'i–y'i+m2)
 
Упражнение 3:
Номер 1
Пусть задача линейного программирования задана в канонической форме:
максимизировать L(x) = Σcjxj, j=1,...,n
при условиях
ΣAjxj = b, j=1,...,n, xj ≥ 0
.
Предположим, что n ≥ m
и ранг матрицы A
равен m
.
Тогда двойственная задача имеет вид:
Ответ:
 
(1)
минимизировать
при условиях
 
 
(2)
максимизировать
при условиях
 
 
(3)
минимизировать
при условиях
 
Номер 2
Пусть двойственная задача линейного программирования имеет вид:
минимизировать
при условиях
и при этом n ≥ m
и ранг матрицы A
равен m
. Тогда задача,
записанная в канонической форме, имеет вид:
Ответ:
 (1)
минимизировать L(x) = Σcjxj, j=1,...,n
при условиях
ΣAjxj = b, j=1,...,n, xj ≥ 0
 
 (2)
максимизировать L(x) = Σcjxj, j=1,...,n
при условиях
ΣAjxj = 0
 
 (3)
максимизировать L(x) = Σcjxj, j=1,...,n
при условиях
ΣAjxj = b, j=1,...,n, xj ≥ 0
 
Номер 3
Задача линейного программирования в канонической форме имеет вид:
максимизировать L(x) = Σcjxj, j=1,...,n
при условиях
ΣAjxj = b, j=1,...,n, xj ≥ 0
.
Двойственная задача к ней задача записана так:
минимизировать
при условиях
Тогда выполняется условие:
Ответ:
 (1) n = m
и ранг матрицы A
равен n
 
 (2) n ≥ m
и ранг матрицы A
равен n
 
 (3) n ≤ m
и ранг матрицы A
равен n
 
Упражнение 4:
Номер 1
Сопряженным базисом называется такая система из m
линейно - независимых векторов матрицы ограничений прямой задачи ,
для которой базисное решение y соответствующей системы линейных уравнений вида
, удовлетворяет ограничениям:
Ответ:
 
(1)
 
 
(2)
 
 
(3)
 
Номер 2
Пусть для некоторой системы, состоящей из m
линейно - независимых векторов
матрицы ограничений прямой задачи , базисное решение y соответствующей
системы линейных уравнений вида , удовлетворяет ограничениям
Тогда данная система носит название:
Ответ:
 (1) базиса прямой задачи 
 (2) базиса обратной задачи 
 (3) сопряженного базиса 
Номер 3
Пусть некоторое базисное решение y системы линейных уравнений вида
, удовлетворяет ограничениям
Тогда вектора матрицы ограничений прямой задачи , составляющие
сопряженный базис, являются:
Ответ:
 (1) линейно – зависимыми 
 (2) линейно – независимыми 
 (3) ортонормированными 
Упражнение 5:
Номер 1
n
–мерный вектор x
, для которого
xi=xi0
при i є Iδ
, и xj=0
при i ∉ Iδ
является псевдопланом тогда и только тогда, когда:
Ответ:
 (1) Δj = 0, j=1,...,n;
 
 (2) Δj ≥ 0, j=1,...,n;
 
 (3) Δj ≤ 0, j=1,...,n;
 
Номер 2
Пусть n
– мерный вектор x
является псевдопланом, для которого
выполняются условия: Δj ≥ 0, j=1,...,n;
. Тогда справедливы равенства:
Ответ:
 (1) xi=xi0
при i є Iδ
,
и xj=0
при i ∉ Iδ
 
 (2) xi=xi0
при i ∉ Iδ
,
и xj=0
при i є Iδ
 
 (3) xi=xj
при i є Iδ
,
и xj0=0
при i ∉ Iδ
 
Номер 3
n
– мерный вектор x
, для которого
xi=xi0
при i є Iδ
,
и xj=0
при i ∉ Iδ
, и при этом выполняются условия:
Δj ≥ 0, j=1,...,n;
, называется:
Ответ:
 (1) сопряженным базисом 
 (2) ортонормированным базисом 
 (3) псевдопланом 
Упражнение 6:
Номер 1
Если среди базисных компонентов псевдоплана x
нет отрицательных,
то псевдоплан x={xi0}
является:
Ответ:
 (1) оптимальным решением прямой задачи 
 (2) допустимым решением прямой задачи 
 (3) оптимальным решением двойственной задачи 
Номер 2
Псевдоплан x={xi0}
является оптимальным решением
прямой задачи, если среди его базисных компонентов:
Ответ:
 (1) нет положительных 
 (2) нет отрицательных 
 (3) имеются отрицательные 
Номер 3
Псевдоплан x={xi0}
, среди базисных компонентов которого
нет отрицательных, является оптимальным решением:
Ответ:
 (1) двойственной задачи 
 (2) прямой задачи 
 (3) обратной задачи 
Упражнение 7:
Номер 1
Пусть известен некоторый сопряженный базис ,
которому соответствует псевдоплан x
, базисные компоненты которого
xi = xi0≥0
для всех i є Iδ
. При этом
Тогда:
Ответ:
 (1) задача неразрешима 
 (2) псевдоплан x
– оптимальное решение 
 (3) псевдоплан x
– допустимое решение 
Номер 2
Пусть известен некоторый сопряженный базис ,
которому соответствует псевдоплан x
. При этом псевдоплан x
является оптимальным
решением и
Тогда для базисных компонентов справедливо условие:
Ответ:
 (1) xi = xi0≥0
для всех i є Iδ
 
 (2) xi = xi0≤0
для всех i є Iδ
 
 (3) xi = xi0=0
для всех i є Iδ
 
Номер 3
Пусть известен некоторый сопряженный базис ,
которому соответствует псевдоплан x
. Базисные компоненты псевдоплана удовлетворяют условиям
xi = xi0≥0
для всех i є Iδ
. При этом псевдоплан
x
является оптимальным решением. Тогда справедливы соотношения:
Ответ:
 (1)
Aj≥ΣAixij; A0≥ΣAixi, i є Iδ
;
 
 (2)
Aj≤ΣAixij; A0≤ΣAixi, i є Iδ
;
 
 (3)
Aj=ΣAixij; A0=ΣAixi, i є Iδ
.
 
Упражнение 8:
Номер 1
Пусть некоторому сопряженному базису соответствует
псевдоплан x
. Очевидно,
Aj=ΣAixij; A0=ΣAixi, i є Iδ
.
Известно, что среди базисных компонентов xi
имеются отрицательные, причем для некоторого
i: xi < 0
, а все
xij ≥ 0, j=1,...,n
. Это значит, что:
Ответ:
 (1) можно перейти к новому псевдоплану 
 (2) задача неразрешима 
 (3) псевдоплан x
– оптимальное решение 
Номер 2
Пусть задан некоторый сопряженный базис
Ему соответствует псевдоплан x
. При этом
Aj=ΣAixij; A0=ΣAixi, i є Iδ
.
Известно, что задача неразрешима. Это значит, что базисные компоненты удовлетворяют условиям:
Ответ:
 (1) xi = xi0≥0
для всех i є Iδ
 
 (2) псевдоплан x
содержит отрицательные компоненты
xi0 < 0
, но для каждой из них среди элементов
{xij}, j=1,...,n
, имеются отрицательные 
 (3) среди xi
имеются отрицательные, причем для
некоторого i: xi < 0
, а все xij ≥ 0, j=1,...,n
 
Номер 3
Пусть некоторому сопряженному базису соответствует
псевдоплан x
. Среди базисных компонентов xi
имеются отрицательные,
причем для некоторого i: xi < 0
, а все xij ≥ 0, j=1,...,n
.
Это значит, что задача неразрешима. Следовательно, справедливы соотношения:
Ответ:
 (1)
Aj=ΣAixij; A0=ΣAixi, i є Iδ
;
 
 (2)
Aj≤ΣAixij; A0≤ΣAixi, i є Iδ
;
 
 (3)
Aj≥ΣAixij; A0≥ΣAixi, i є Iδ
.