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

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) = 3x₁+5x₂+7x₃ + 9x₄ ® 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, х₂ …, х_n называется точка

X = λ₁x₁ + λ₂x₂ + … + λ_nx_n, где

а) λ_j ≥ 0, j = ; б) x_j ≥ 0, j = ;

в) λ₁ + λ₂ + … + λ_n = 1; г) λ_j ≥ 0; .

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

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

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

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

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

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

F(x) = 3x₁+5x₂+7x₃ + 9x₄ ® max

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

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

 

а) y₁ ≥ 0; y₂ ≥ 0; y₃ ≥ 0; y₄ ≥ 0;

б) y₁ ≥ 0; y₂ = 0;y₃ = 0; y₄ ≥ 0;

в) y₁ ≥ 0; y₂ и y₃ любые по знаку; y₄ ≥ 0;

г) y₁ ≥ 0; y₂ ≤ 0; y₃ ≤ 0; y₄ ≥ 0;

 

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

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

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

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

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

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

 

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

Max Z = 2x₁ + 7x₂ +4x₃ при

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

а) б)

в) г)

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

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

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

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

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

При строительстве одного филиала указанной мощности потребляется различное количество капитальных вложений каждого вида (табл.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