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

и ограничения являются линейными

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

допустимым планом задачи

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

оптимальное

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

ввести в задачу дополнительные переменные и свести ограничения вида неравенств к ограничениям – равенствам

Допустимое множество - это множество всех точек плоскости, координаты которых … .

удовлетворяют всем ограничениям системы

Выпуклым многоугольником может быть … .

неограниченный многоугольник

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

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

Линиями уровня функции f(х) называется множество точек х, удовлетворяющих уравнению f(x) = … .

a, a=const

Если с₁,с₂ являются коэффициентами при х₁ и x₂ в уравнении целевой функции f(x₁,x₂)=c₁x₁+c₂x₂, то вектор, соединяющий точку (0,0) и точку (с₁,с₂), называется … .

нормалью

При решении задачи линейного программирования геометрическим способом пересечение допустимой области с линией уровня функции в направлении нормали, когда дальнейшее перемещение дает пустое множество, будет множеством … .

точек максимума

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

минимума

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

не достигает максимального значения

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

не достигает минимального значения

Отметьте верные утверждения … .

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

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

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

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

ограничена

Если векторы А_j, соответствующие отличным от нуля координатам вектора х, линейно-независимы, то ненулевое допустимое решение х = (х₁, …, х_n)^Т называется … .

опорным

Ненулевое опорное решение называется невырожденным, если оно имеет … .

(А - матрица коэффициентов при неизвестных переменных левой части ограничений, m - ранг матрицы А)

«m» положительных координат

Если число положительных координат опорного решения меньше ранга матрицы А, то его называют … .

(А - матрица коэффициентов при неизвестных переменных левой части ограничений)

вырожденным

Ненулевое опорное решение называется …, если оно имеет точно «m» положительных координат.

(А - матрица коэффициентов при неизвестных переменных левой части ограничений, m - ранг матрицы А)

невырожденным

Упорядоченный набор из «m» линейно-независимых векторов А_i, соответствующих положительным координатам опорного решения называется … .

(А - матрица коэффициентов при неизвестных переменных левой части ограничений, m - ранг матрицы А)

базисом

Если ранг матрицы А равен 2, то допустимое решение х = (1, 0, 0, 0) называется … .

(А - матрица коэффициентов при неизвестных переменных левой части ограничений)

вырожденным

Если ранг матрицы А равен 2, то допустимое решение х = (0, 7, 0, 11) называется … .

(А - матрица коэффициентов при неизвестных переменных левой части ограничений)

невырожденным

Вектор х = (х₁, …, х_n) тогда и только тогда является опорным решением задачи линейного программирования, когда … .

(А - матрица коэффициентов при неизвестных переменных левой части ограничений)

все компоненты точки х отличны от нуля

Если среди компонентов вектора оценок а_j в алгоритме решения задачи линейного программирования существуют такие, для которых все х_ij ≤ 0, то … .

необходимо продолжить поиск оптимального решения

При решении задачи линейного программирования в форме симплекс-таблиц значение целевой функции вычисляется как сумма … .

произведений соответствующих коэффициентов при неизвестных из целевой функции и значений опорного решения

В симплекс-таблице ведущим будет столбец, в котором значение α_j … .

(α_j – компонент вектора оценок)

минимально

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

(b – вектор свободных членов ограничений, правых частей ограничений, А - матрица коэффициентов при неизвестных переменных левых частей ограничений)

А ведущего столбца минимально

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

ведущим

При решении задачи линейного программирования с помощью симплекс-таблиц при построении следующей симплекс-таблицы происходит … .

(А - матрица коэффициентов при неизвестных переменных левых частей ограничений)

изменение базиса, путем замены вектора А ведущей строки на вектор А ведущего столбца

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

ведущий элемент

При решении задачи линейного программирования с помощью симплекс-таблиц построение симплекс-таблиц происходит до тех пор, пока все … .

ячейки симплекс таблицы не будут отрицательными

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

теневой

Оптимальной теневой ценой ресурса называется такая, которая … .

минимизирует общую теневую стоимость ресурсов

Выберите верные утверждения … .

Целевая функция исходной задачи задается на максимум, а целевая функция двойственной задачи – на минимум

Число ограничений в двойственной задаче равно числу переменных прямой

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

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

пустой

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

чувствительности

Линейными функциями являются функции … .

x₁+4x₂ = 0

f = 11x₁-11x₂

Линейными функциями являются функции … .

f = 15x₁+8x₂-14x₃

f = x₁

-2x₁+9x₃ = 0

Ограничения в каноническом виде для задачи линейного программирования представлены выражениями … .

13x₂-4*(x₁-x₃)=11

Ограничения в каноническом виде для задачи линейного программирования представлены выражениями … .

2x₁+3x₂-4x₃=3

5x₁-6x₄=8

Задача, состоящая в нахождении наибольшего/наименьшего значения функции f(x)=c₁x₁+c₂x₂+…+ c_nx_n на множестве точек х^т=(х₁,…,х_n), удовлетворяющие системе ограничений вида

называется … .

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

Задачей линейного программирования, записанной в векторной форме, является … .

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

Вектор А₄ равен … .

(А_i - базис)

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

Вектор b равен … .

(b – опорное решение задачи, свободные члены ограничений)

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

Допустимым решением будет значение х = … .

(0, 2, 0, 1)

(2, 1, 1, 0)

Дана задача линейного программирования в общем виде:

Компоненты вектора оценок данной задачи вычисляются по формуле … .

Дана задача линейного программирования в общем виде:

Формулой определяется значение … .

целевой функции

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

Двойственной задачей по отношению к прямой задаче будет … .

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

(f – целевая функция прямой задачи, f* – целевая функция двойственной задачи)

будет иметь оптимальное решение, причем max f = min f^*

Допустимой точкой или допустимым решением (планом) задачи линейного программирования, называется … .

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

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

допустимое множество

Вектор градиента (grad) для функции f = -5x₁ + 7x₂ будет соединять в пространстве координат точки (0,0) и … .

(-5, 7)

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

пересечение допустимой области с линией уровня в направлении нормали, когда дальнейшее перемещение дает пустое множество

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

она не пуста

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

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

Если векторы A_j, соответствующие отличным от нуля координатам вектора х, линейно-независимы, то ненулевое допустимое решение x = (x₁, …, x_n)^Т называется … .

опорным

Опорное решение называется вырожденным, если … .

( - матрица коэффициентов перед переменными x₁, …, x_n в ограничениях задачи линейного программирования, m – количество ограничений)

число положительных координат опорного решения меньше ранга матрицы А

Если ранг матрицы A равен m, то ненулевое опорное решение называется невырожденным, если оно имеет …

( - матрица коэффициентов перед переменными x₁, …, x_n в ограничениях задачи линейного программирования, m – количество ограничений)

«m» положительных координат

Базис – это … .

( - матрица коэффициентов перед переменными x₁, …, x_n в ограничениях задачи линейного программирования, A_j = (a_1j, a_2j, …, a_mn)^T, m – количество ограничений, n – количество переменных)

упорядоченный набор из «m» линейно-независимых векторов A_i , соответствующих положительным координатам опорного решения

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

ведущий элемент

При решении задачи линейного программирования с помощью метода симплекс таблиц ведущая строка в симплекс-таблице выбирается следующим образом: находится отношение координат вектора b к соответствующим … .

( - матрица коэффициентов перед переменными x₁, …, x_n в ограничениях задачи линейного программирования, A_j = (a_1j, a_2j, …, a_mn)^T, m – количество ограничений, n – количество переменных, b –опорное решение)

положительным координатам вектора A и выбирается минимальное из них

Каждый вид ресурса на предприятии обладает «теневой» ценой, которая определяет … .

ценность данного ресурса для предприятия

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

оптимальные теневые цены

Число переменных двойственной задачи … .

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

К задачам линейного программирования относят следующие виды задач … .

планирования выпуска продукции

планирования капитальных вложений

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

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

каждое из ограничений графически задает … .

множество точек, лежащих в определенной полуплоскости от прямой

Множество решений задачи линейного программирования … .

выпукло

Вектор х = (x₁, …, x_n) тогда и только тогда является опорным решением задачи, когда точка х … .

х является вершиной допустимого множества

В формуле пересчета для метода симплекс таблиц , x_rs представляет собой … .

ведущий элемент

Условием нахождения оптимального опорного решения задачи линейного программирования с помощью симплекс-таблиц является выполнение соотношения для вектора оценок … .

α_j > 0

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

в наибольшей степени ограничивают выпуск продукции

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

переменные y_m обозначают … .

теневую цену ресурса

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

свободные члены системы сильных ограничений прямой задачи

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

Матрица системы сильных ограничений двойственной задачи будет равна … .

Если при решении двойственной задачи условные двойственные оценки единицы сырья y_i=0, это означает, что вид сырья … .

не полностью используется при оптимальном плане производства продукции

При анализе чувствительности двойственной задачи изучается … .

воздействие дополнительного количества дефицитного ресурса

воздействие дополнительного количества недефицитного ресурса

воздействие изменений в коэффициентах целевой функции

Общая постановка транспортной задачи состоит … .

в определении оптимального плана перевозок однородного груза из N пунктов отправления в М пунктов потребления

В качестве критерия оптимальности берётся … стоимость перевозок всего груза.

минимальная

Термин «транспортная задача» возник в … годах.

30-х

Транспортная задача относится к классу задач … программирования.

линейного

К способам нахождения опорного плана транспортной задачи можно отнести метод … .

минимального элемента

северо-западного угла

К способам нахождения оптимального опорного плана транспортной задачи можно отнести метод … .

потенциалов

Транспортная задача может быть … .

открытой

закрытой

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

закрытой

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

открытой

Необходимым и достаточным условием разрешимости транспортной задачи является ее … .

закрытость

Расставьте приоритеты в схеме нахождения оптимального решения транспортной задачи:

2. Проверка на оптимальность.

1. Поиск опорного плана.

3. Переход к новому опорному плану, улучшающему целевую функцию в сторону ее оптимальности.

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

вырожденным

невырожденным

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

минимального элемента

северо-западного угла

аппроксимации Фогеля

Расставьте приоритеты в алгоритме нахождения начального опорного плана методом минимального элемента:

4Если наименьший тариф соответствует более чем одной клетке, выбор осуществляется случайным выбором.

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

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

2Производится корректировка оставшихся запасов и потребностей.

Метод потенциалов решения транспортной задачи реализуется для … опорных решений.

невырожденных

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

циклом

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

чувствительность

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

оптимальности

В транспортных задачах в таблицу поставок для каждой пары «поставщик-потребитель» сводятся … .

мощности поставщиков, запросы потребителей и затраты на перевозку единицы груза

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

поставок

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

все пункты потребления были снабжены требуемым количеством сырья

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

стоимость перевозок была минимальной

все перечисленные варианты

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

перевозок

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

(x_ij – количество тонн сырья, c_ij – стоимость перевозки одной тонны сырья, x_i – пункт отправления, y_i – пункт потребления)

Методом линейного программирования одними из первых стали решать задачи … .

транспортные

Транспортная задача – одна из самых первых задач, которую стали решать с помощью методов … программирования.

линейного

В закрытой транспортной задаче сумма запасов … .

равна сумме потребностей

В открытой транспортной задаче … .

сумма потребностей не равна сумме запасов

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

открытой

Если транспортная задача является открытой, то в задачу вводим … .

одного потребителя

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

в таблицу поставок вводим одного поставщика

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

в таблицу поставок вводим одного поставщика

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

поставщика

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

потребителя

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

грузы к новому потребителю отправляться не будут и тарифы на перевозку грузов фиктивного потребителя равны нулю

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

грузы к новому потребителю (фиктивному) отправляться не будут

Транспортная задача является разрешимой, если она является … .

закрытой

В схеме нахождения оптимального решения транспортной задачи не существуют пунктов … .

нахождение начального базиса

построение дополнительного линейного ограничения

Опорный план называется невырожденным, если он содержит … .

(M - количество пунктов потребления, N – количество пунктов отправления)

M+N-1 отличных от нуля значений неизвестных

Опорный план, содержащий (M+N-1) отличных от нуля значений неизвестных, называется … планом.

(M - количество пунктов потребления, N – количество пунктов отправления)

невырожденным

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

метод Гомори

метод равномерного поиска

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

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

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

1В верхнюю левую клетку таблицы поставок записываем наименьшее число из запасов и потребностей.

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

северо-западного угла

Важнейшим условием построения опорного плана является назначение в выбранной клетке … .

наибольшего возможного плана перевозки

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

верхняя левая

Число заполненных клеток в таблице поставок в методе северо-западного угла … .

(M - количество пунктов потребления, N – количество пунктов отправления)

меньше или равно (M+N-1)

Метод потенциалов используется для решения транспортной задачи в следующих случаях … .

после применения метода северо-западного угла

после применения метода минимального элемента

Величина, которая характеризует затраты на поставку от i-го поставщика j-ому потребителю в транспортных задачах равна … .

(v_j – потенциал j-го потребителя, u_i – потенциал i-го поставщика)

v_j-u_i

При решении транспортной задачи величина v_j-u_i-c_ij называется … .

(v_j – потенциал j-го потребителя, u_i – потенциал i-го поставщика, с_ij – стоимость перевозки одной тонны груза от i-го поставщика j-му потребителю)

теневой ценой по перемещению единицы груза от i-го поставщика j-му потребителю

Если при решении транспортной задачи теневая цена для свободной клетки меньше нуля, то перемещение по маршруту i→j может привести к … .

увеличению затрат

Если при решении транспортной задачи теневая цена для свободной клетки больше нуля, то перемещение по маршруту i→j может привести к … .

уменьшению затрат

Для определения потенциалов для заполненных клеток составляются выражения … .

(v_j – потенциал j-го потребителя, u_i – потенциал i-го поставщика, с_ij – стоимость перевозки одной тонны груза от i-го поставщика j-му потребителю)

v_j-u_i-c_ij=0

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

(v_j – потенциал j-го потребителя, u_i – потенциал i-го поставщика, с_ij – стоимость перевозки одной тонны груза от i-го поставщика j-му потребителю)

v_j-u_i-c_ij≤0

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

(v_j – потенциал j-го потребителя, u_i – потенциал i-го поставщика, с_ij – стоимость перевозки одной тонны груза от i-го поставщика j-му потребителю, x_ij – количество тонн сырья, которое i-го поставщика j-му потребителю)

v_j-u_i-c_ij=0 для клеток с x_ij>0 и v_j-u_i-c_ij≤0 для клеток с x_ij=0

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

(v_j – потенциал j-го потребителя, u_i – потенциал i-го поставщика, с_ij – стоимость перевозки одной тонны груза от i-го поставщика j-му потребителю)

наибольшая разность v_j-u_i-c_ij>0

Цикл перераспределения грузов в транспортных задачах имеет начало и конец … .

в клетке пересчета

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

пересчета

Цикл пересчета в таблице поставок транспортной задаче начинается с … клетки.

«плюсовой»

Цикл пересчета в таблице поставок транспортной задачи начинается с … клетки.

плюсовой

Цикл пересчета в таблице поставок транспортной задаче строится … .

по часовой стрелке

В клетку пересчета при перераспределении груза в транспортной задаче записывается … .

(x_ij – количество тонн сырья, которое i-го поставщика j-му потребителю)

наименьшее из чисел x_ij,стоящих в «минусовых» клетках

В цикле пересчета в транспортной задаче выбранное число из «минусовых» клеток вычитается из … клеток.

«минусовых»

В цикле пересчета в транспортной задаче выбранное число из «минусовых» клеток прибавляется к … клеткам.

«плюсовым»

Метод, который при решении транспортной задачи не учитывает величины тарифов, это метод … .

северо-западного угла

Если минимальное значение среди чисел x_ij в «минусовых» клетках цикла пересчета равно нулю, то … .

(x_ij – количество тонн сырья, которое i-го поставщика j-му потребителю)

задача не имеет решение

необходимо добавить еще одного потребителя

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

найдено оптимальное решение задачи

ХУЙ ЗНАЕТ!

При получении оптимального опорного плана транспортной задачи затраты на перевозку … .

снижаются

При анализе чувствительности можно указать промежутки устойчивости оптимального плана по изменению тарифов для … клеток.

свободных и занятых

К задачам целочисленного линейного программирования относятся задачи … .

о размещениях

о коммивояжёре

о назначениях

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

о коммивояжёре

К методам решения задач целочисленного программирования относятся…

метод ветвей и границ

метод отсечения Гомори

Матрица, которая получается из матрицы расстояний вычитанием из элементов каждой строки …, называется приведённой.

минимального элемента этой строки, а затем вычитанием из элементов каждого столбца минимального элемента этого столбца

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

о назначениях

Задача о размещениях заключается в нахождении такого объема продукции в единицах, который необходимо произвести …

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

Задача о назначениях заключается в нахождении такого распределения оборудования … .

по одному на предприятие, которое обеспечит максимальную производительность

Задача о коммиявожёре заключается в нахождении…

минимального замкнутого и безпетельного маршрута, при условии, что из каждого города коммиявожёр въезжает и выезжает только один раз

Распределите пункты в порядке выполнения алгоритма метода отсечения Гомори:

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