Тесты. Линейное программирование

1. В задаче линейного программирования требуется найти:

а) значение целевой функции;

б) значения переменных, удовлетворяющих системе ограничений;

в) значения переменных, обеспечивающих max(min) целевой функции;

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

 

2. Областью допустимых планов ЗЛП называется множество:

а) переменных, удовлетворяющих целевой функции;

б) неотрицательных переменных;

в) угловых точек многогранника решений;

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

3. Критерий прекращения счета в симплекс-методе задачи минимизации ЛП: в индексной строке все элементы

а) неотрицательны; б) отрицательны;

в) не положительны; г) положительны.

4. Задача ЛП max

Ax ,

имеет вид: а) общий; в) стандартный;

б) матричный; г) канонический.

5. Искусственная переменная входит в целевую функцию задачи ЛП максимизации с коэффициентом:

а) + М; б) 1; в) - М; г) 0.

6. Дана симплексная таблица

Баз. пер. Сj баз В
Х5 Х6 Х4 Х3 321,6 6,4 -0,1 -5 0,6 0,35 0,7 -21 0,8 0,55 -0,35 -2,5 0,1 -0,025 1/15 -1/15 0,1
    11,5 34,5 2,75 2,333

 

Оптимальное решение данной задачи ЛП имеет вид:

а) max 600 (0;0;40;50;0;0;0;0);

б) min 600 (321,6;80;70;6,4;0;0;0;0);

в) max 600 (0;0; 321,6;80;70;0;0;0);

г) max 600 (0;0; 6,4;70;321,6;80;0;0).

6. В задаче F(x) = 3x1+5x2+7x3 + 9x4 ® max

при ограничениях:

для ручного симплекс-метода необходимо число дополнительных и искусственных переменных:

а) 2 и 2; б) 1 и 2; в) 1 и 3; г) 2 и 3; д) 2 и 4.

7. Если ресурс использован полностью, то соответствующая ему двойственная оценка:

а) неотрицательна; б) положительна;

в) равна 0; г) любая по знаку.

8. Дана симплексная таблица

Баз. пер. Сi баз В
х1 х2 х3 х4
х4 х2 -2 -1
Z   -8

Математическая модель данной задачи имеет вид:

а) б)

в) г)

9. Искусственная переменная входит в целевую функцию задачи минимизации ЛП с коэффициентом:

а) + М; б) 1; в) - М; г) min Z = 10.

10. Дана симплексная таблица

Баз. пер. Сi баз В
х1 х2 х3 х4
х4 х2 -2 -1
Z   -8

Особенности решения данной задачи линейного программирования:

а) функция Z не ограничена снизу;

б) не ограничена область допустимых решений;

в) не ограничена функция Z сверху и область допустимых решений;

г) система ограничений несовместна.

11. В данной симплексной таблице

 

Баз. пер. Сi баз В
х1 х2 х3 х4
х4 х2 -2 -1
Z   -8

значение целевой функции равно:

а) max Z = 10; б) min Z = ; в) max Z = ; г) min Z = 10.

12. Для того чтобы X и Y были оптимальными планами исходной и двойственной задачи ЛП, необходимо и достаточно, чтобы:

а) все ресурсы были использованы; б) max F (X) = min F (Y);

в) существование допустимого плана; г) max F (X) = min Z(Y).

13. Задача линейного программирования

задана в форме записи:

а) матричной; б) канонической; в) стандартной; г) векторной.

14. В данной симплексной таблице

Баз. пер. Сi баз В
х1 х2 х3 х4
х4 х2 -2 -1
Z   -8

 

опорный план равен:

а) (0,2,0,1); б) (3,1,-2,1); в) не существует; г) (0,3,0,4,).

15. Разрешающий столбец задачи максимизации ЛП определяют по

а) наименьшему из отрицательных элементов в индексной строке;

б) наибольшему из неотрицательных элементов индексной строки;

в) наибольшему модулю отрицательных элементов индексной строки;

г) а, в верно; д) б, в верно.

16. Любую точку многогранника планов задачи ЛП можно представить как линейную комбинацию его:

а) внутренних точек; б) угловых точек;

в) граничных точек; г) допустимых точек.

17. Основная идея симплекс-метода:

а) перебор всех вершин многогранника планов;

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

в) перебор всех опорных планов;

г) кратчайший переход от одной угловой точки к другой;

д) а, б верно; е) б, в верно; ж) б, г верно; з) в, г верно.

18. Для существования оптимального плана любой из пары двойственных задач необходимо и достаточно . . ..

19. Выпуклой линейной комбинацией точек х1, х2 …, хnназывается точка

X = λ1x1 + λ2x2 + … + λnxn, где

а) λj ≥ 0, j = ; б) xj ≥ 0, j = ;

в) λ1 + λ2 + … + λn = 1; г) λj ≥ 0; .

20. Если в индексной строке последней симплексной таблицы (содержащей оптимальный план) имеется хотя бы одна нулевая оценка, соответствующая свободной переменной, то ЗЛП имеет:

а) бесконечное множество оптимальных планов;

б) единственный оптимальный план;

в) альтернативный оптимум;

г) а, в верно; д) б, в верно.

21. В задаче линейного программирования:

F(x) = 3x1+5x2+7x3 + 9x4 ® max

при ограничениях:

знаки двойственных оценок:

 

а) y1 ≥ 0; y2 ≥ 0; y3 ≥ 0; y4 ≥ 0;

б) y1 ≥ 0; y2 = 0;y3 = 0; y4 ≥ 0;

в) y1 ≥ 0; y2 и y3 любые по знаку; y4 ≥ 0;

г) y1 ≥ 0; y2 ≤ 0; y3 ≤ 0; y4 ≥ 0;

 

22. Если в оптимальном плане М-задачи не все искусственные переменные

равны нулю, то задача имеет:

а) бесконечное множество оптимальных планов;

б) единственный оптимальный план;

в) система ограничений исходной задачи несовместна;

г) целевая функция не ограничена.

 

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

Max Z = 2x1 + 7x2 +4x3 при

двойственная задача имеет вид:

а) б)

в) г )

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

 

а) значения целевой функции в них равны;

б) имеем альтернативный оптимум;

в) бесконечное множество оптимальных планов;

г) все ответы верны.

 

25. Двойственная оценка численно равна изменению:

а) ресурсов;

б) целевой функции при изменении соответствующего ресурса на единицу;

в) приращению функции цели, вызванным малым изменением свободного члена соответствующего ограничения ЗЛП;

г) б, в верно,

д) а, в верно.

 

ПРАКТИКУМ

ЗАДАНИЕ 1.Определение оптимального варианта строительства скважин в УБР на планируемый год

В УБР запланировано строительство скважин нескольких категорий:

I категории - не более H1

II категории - не более H2

III категории - не менее (не более) H3

При строительстве скважин используются разные материально-технические ресурсы, наличие которых в УБР ограничено следующим количеством (в тоннах): обсадные трубы - В1, химреагенты - В2, глина и глинопорошок - В3, талевый канат - В4, ГСМ - В5. При строительстве скважин разной категории потребляется различное количество ресурсов каждого вида. Расход материально - технических ресурсов в расчете на 1 скважину каждой категории задан табл.4.4.

Таблица 4.4

Виды ресурсов   Категории скважин Обсадные трубы Хим. реагенты Глина и глино-порошок Талевый канат ГСМ
В1 В2 В3 В4 В5
I
II
III

 

Экономический эффект при строительстве скважины j категории определен Эjтыс. рублей. Требуется:

1. Определить оптимальный план строительства скважин, при котором в пределах ограниченного объема ресурсов (табл. 4.5.) достигается максимальный экономический эффект.

2.Определить двойственные оценки ресурсов и их устойчивость, дефицитность ресурсов.

3.Провести всесторонний анализ полученных оптимальных решений.

Таблица 4.5

Варианты заданий

№ вар. H1 H2 H3 Э1 Э2 Э3 В1 В2 В3 В4 В5
не более 7
не более 8
не бол. 6
не более 5
не бол. 6

продолжение таблицы 4.5

не более 6
не бол. 7
не менее 13
не менее 12
не менее 10
не мен. 7
не менее 8
не менее 9
не более 13
не менее 6
не менее 8
не менее 9
не менее 8
не менее 9
не менее 9
не менее 9
не менее 9
не менее 7
не мен. 9
не менее 7
не мен. 9
не менее 8
не менее 8
не менее 10
не менее 7

ЗАДАНИЕ 2. Определение оптимального варианта строительства автотранспортных предприятий Тюменского нефтегазовогорегиона

Предприятие автомобильного транспорта планирует строительство своих филиалов следующих мощностей:

П-I до 2000 ремонтов в год - не менее H1

П-II от 2000 - 4000 ремонтов в год - не менее H2

П-III от 4000 - 6000 ремонтов в год - не более H3

П-IV от 6000 - 8000 ремонтов в год - не более H4

При строительстве этих филиалов капитальные вложения (в д. ед.) направляются на следующие цели:

- строительно - монтажные работы в количестве В1;

- монтаж оборудования в количестве В2;

- транспортирование стройматериалов и оборудования в количестве В3.

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

Таблица 4.6

Расход ресурсов

Вид ресурса   Мощность предприятия Стротельно - монтажные работы Монтаж оборудования Транспортирование стройматериалов и оборудования
П-I 0,66 0,39 0,15
П-II 0,5 0,3 0,2
П-III 0,43 0,27 0,25
П-IV 0,4 0,25 0,30

 

В табл.4.6. приведен расход i ресурса в расчете на филиал j-той мощности. Экономический эффект от строительства филиала j- той мощности определен в размере Эj д. единиц. Требуется:

1. Найти такой план строительства филиалов, при котором в пределах выделенного объема капитальных вложений (табл.4.7) достигается максимальный суммарный экономический эффект.

2.Решив исходную задачу С - методом, проверить справедливость равенства АjАj-I = Е, где матрица Аj-I - матрица из последней симплексной таблицы.

3. Составить двойственную модель задачи и найти решение двойственной задачи, используя равенство У* = С*jбазАj-I.

4.Сравнить полученные результаты исходной и двойственной задачи. Объяснить экономический смысл значений переменных оптимального плана исходной и двойственной модели, связь между ними.

5.Проверить взаимность двойственной пары.

6.Оценить интервалы устойчивости двойственных оценок.

Таблица 4.7

Варианты заданий

 

№ Вар.     H1   H2   H3   H4   Э1   Э2   Э3   Э4   В1   В2   В3   В2   В3
не мен 15 не мен 10 не бол 8 не бол 4 0,5 0,6 0,6 0,7
не мен 14 не мен 11 не бол 8 не бол 2 0,4 0,5 0,7 0,6
не бол 10 не бол 7 не бол 6 не бол 4 0,5 0,4 0,6 0,8
не бол 11 не бол 10 не мен 4 не бол 2 0,5 0,6 0,7 0,8
не бол 13 не бол 11 не мен 5 не мен 2 0,5 0,6 0,7 0,8
не мен 11 не мен 10 не бол 4 не бол 2 0,5 0,6 0,7 0,7
не бол 11 не бол 9 не мен 6 не мен 5 0,5 0,6 0,7 0,8
не мен 10 не мен 8 не бол 5 не бол 4 0,6 0,7 0,5 0,6
не мен 12 не мен 8 не бол 5 не бол 3 0,5 0,6 0,7 0,8
не мен 12 не мен 5 не бол 4 не бол 2 0,5 0,6 0,6 0,8
не мен 11 не мен 8 не бол 4 не бол 3 0,5 0,6 0,7 0,8
не мен 15 не мен 9 не бол 5 не бол 2 0,5 0,6 0,6 0,7
не мен 14 не мен 8 не бол 5 не бол 3 0,5 0,6 0,7 0,8
не мен 10 не мен 8 не бол 6 не бол 3 0,5 0,5 0,6 0,7
не мен 13 не мен 8 не бол 4 не бол 3 0,5 0,6 0,7 0,8
не мен 12 не мен 6 не бол 8 не бол 2 0,4 0,5 0,6 0.8
не мен 14 не мен 9 не бол 4 не бол 2 0,5 0,6 0,7 0.8
не мен 12 не мен 5 не бол 5 не бол 1 0,5 0,6 0,7 0,6
не мен 13 не мен 7 не бол 5 не бол 2 0,5 0,6 0,7 0,8
не мен 13 не мен 6 не бол 6 не бол 2 0,5 0,6 0,7 0.7
не мен 14 не мен 4 не бол 8 не бол 2 0,5 0,6 0,6 0,8
не мен 15 не мен 7 не бол 9 не бол 3 0.5 0,6 0,7 0,8
не мен 16 не мен 8 не бол 6 не бол 3 0,5 0,6 0,5 0.6
не мен 14 не мен 9 не бол 6 не бол 2 0,5 0,6 0,7 0,8
не мен 14 не мен 11 не бол 8 не бол 3 0,5 0,6 0,6 0,7
не мен 12 не мен 11 не бол 5 не бол 2 0,5 0,6 0,7 0,8
не мен 13 не мен 10 не бол 9 не бол 3 0,5 0,5 0,6 0,7
не мен 12 не мен 10 не бол 8 не бол 2 0.5 0,6 0,7 0.8
не мен 13 не мен 9 не бол 6 не бол 4 0,5 0,6 0.7 0,8