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

Вопрос 24. Что такое оптимальный план задачи линейного программирования?

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

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

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

Вопрос 27. В каком случае точка на отрезке между оптимальными планами задачи линейного программирования тоже будет оптимальным планом (задача не целочисленная)?

1. всегда 2. никогда 3. если задача на максимум

Вопрос 28. Сколько допустимых планов может иметь задача линейного программирования (не целочисленная)?

1. 0 или 1 2. всегда 1 3. 0, 1 или бесконечное множество

Вопрос 29. Что такое неограниченная область допустимых планов задачи линейного программирования?

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

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

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

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

1. всегда 2. другое 3. никогда

Вопрос 32. В каком направлении сдвигают линию уровня целевой функции при решении задачи линейного программирования на максимум?

1. вверх 2. в направлении антиградиента 3. в направлении градиента

Вопрос 33. Сколько оптимальных планов может иметь задача линейного программирования (не целочисленная)?

1. 0 или 1 2. всегда 1 3. 0, 1 или бесконечное множество

Вопрос 34. Каким образом можно избавиться от не ограниченных по знаку переменных в системе ограничений?

1. исключить эти переменные из рассмотрения 2. заменить неограниченную по знаку переменную на разность двух неотрицательных 3. наложить на них ограничения неотрицательности

Вопрос 35. Какое из приведенных ниже утверждений о разрешимости сопряженных задач является НЕ верным?

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

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

Вопрос 37. В чем заключается критерий допустимости симплексной таблицы?

1. все коэффициенты в критериальном ограничении должны быть неотрицательными (или неположительными) 2. все свободные члены должны быть неотрицательными (или неположительными) 3. все свободные члены должны быть неотрицательными

Вопрос 38. При построении двойственной задачи к задаче линейного программирования в стандартной форме строится столько ограничений, сколько в прямой задаче.

1. основных переменных 2. другое 3. ограничений

Вопрос 39. Каким образом строится целевая функция расширенной задачи при использовании двухэтапного симплекс-метода?

1. суммируются дополнительные переменные 2. другое 3. суммируются искусственные переменные

Вопрос 40. Какая переменная входит в базис при преобразовании симплексной таблицы?

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

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

МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Выше мы рассмотрели математические модели задачи оптимального использования ресурсов и транспортной задачи. Все рассмотренные модели обладают свойствами, позволяющими включить их в широкий и важный класс — класс задач линейного программирования. Задачи линейного программирования, охватывают самые разнообразные управленческие ситуации, требующие расчета оптимальных решений. Наряду с различными моделями производственных ситуаций, они содержат задачи, возникающие из других экономических проблем. Единый подход к моделированию разнообразных задач позволяет разработать единые методы их решения и анализа, дает возможность увидеть существенные общие черты в проблемах, различных по экономическому содержанию и источникам возникновения. Дадим необходимые определения.

Функция n переменных x ₁, x ₂, . x _n

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

Иногда линейной называют также функцию вида

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

а также неравенства

называются линейным равенством и линейными неравенствами , если функция

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

при условии, что переменные удовлетворяют системе линейных равенств и неравенств:

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

Всякий набор значений переменных, то есть вектор X значений,

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

Решить задачу линейного программирования — значит найти ее оптимальный план и оптимум.

Вопрос 1. Каким образом вводятся переменные двойственной задачи, соответствующие ограничениям-уравнениям прямой задачи?

Вопрос 2. Каким образом можно избавиться от уравнений в системе ограничений?

1. ввести дополнительные переменные 2. ограничение уравнение можно заменить на два неравенства 3. в каждом из них заменить знак «=» на знак неравенства

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

1. другое 2. основных переменных 3. ограничений

Вопрос 4. Какая переменная выходит из базиса при преобразовании симплексной таблицы?

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

Вопрос 5. Что такое критерий эффективности операции?

1. показатель управляемости операции 2. оценка прибыли, полученной в результате операции 3. показатель того, насколько результат операции соответствует ее целям

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

Вопрос 7. В матричной форме можно записать.

1. задачу линейного программирования, предварительно приведенную к стандартной или канонической форме 2. только задачу линейного программирования, предварительно приведенную к канонической форме 3. задачу линейного программирования в смешанной форме

Вопрос 8. Что показывают «теневые цены» (основные переменные двойственной задачи) в линейной задаче производственного планирования?

1. цены, по которым можно продать произведенную продукцию 2. изменение оптимальной выручки при изменении запаса соответствующего ресурса на единицу 3. затраты на производство продукции

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

1. должны быть только дробными числами 2. могут быть как целыми, так и дробными числами 3. должны быть только целыми числами Вопрос 10. Если в разрешающем столбце симплексной таблицы нет положительных коэффициентов, это означает, что . 1. найден оптимальный план на максимум 2. задача неразрешима 3. найден оптимальный план на минимум Вопрос 11. Если в критериальной строке симплексной таблицы нет отрицательный коэффициентов, это означает, что . 1. задача неразрешима 2. найден оптимальный план на максимум 3. найден оптимальный план на минимум

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

1. если ее целевая функция линейна 2. если ее ограничения линейны 3. если ее целевая функция и ограничения линейны

Вопрос 13. Чему равны не базисные переменные в опорном плане задачи линейного программирования?

1. нулю 2. любым числам 3. положительным числам

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

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

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

1. больше нуля 2. может быть любым 3. равно нулю Вопрос 16. Если крайнее положение линии уровня пересекает область допустимых планов более чем в одной точке, то оптимальный план . 1. только одна из точек пере-сечения (единственный) 2. не существует 3. любая точка пересечения (бесконечное множество точек)

Вопрос 17. Что такое оптимум задачи линейного программирования?

1. значение целевой функции на оптимальном плане 2. оптимальный план 3. любое значение целевой функции

Вопрос 18. В чем заключается критерий оптимальности симплексной таблицы?

1. все коэффициенты в критериальном ограничении должны быть неотрицательными (или неположительными)

2. все свободные члены должны быть неотрицательными (или неположительными) 3. все свободные члены должны быть неотрицательными

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

1. полуплоскость 2. прямую 3. отрезок

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

1. как уравнения 2. как неравенства 3. другое

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

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

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

ГРАФИКА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Область допустимых планов . Оптимальный план и оптимум

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

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

Планы такой задачи — это пары чисел (x₁, x₂). Им соответствуют точки координатной плоскости ( Рис. 2.1 ).

Рис. STYLEREF 1 \ s 2 . 1 . Ограниченная область допустимых планов

Область допустимых планов

Рассмотрим систему ограничений. Возьмем одно из неравенств системы,

Множество решений неравенства, то есть множество пар (x₁, x₂), компоненты которых удовлетворяют неравенству, геометрически представляет собой полуплоскость. Для того чтобы определить граничную прямую этой полуплоскости, следует заменить знак неравенства знаком равенства:

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

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

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

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

Множеством решений системы неравенств в целом является пересечение всех полуплоскостей, соответствующих отдельным неравенствам системы. Это пересечение и определяет множество допустимых планов. Это множество часто называют также областью допустимых планов (сокращенно ОДП). Оно представляет собой выпуклую многоугольную область.

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

Оптимальный план и оптимум

Как найти оптимальный план? Обратимся к целевой функции. Приравняем ее какой-нибудь константе d

Мы получили уравнение, определяющее некоторую прямую на координатной плоскости. Все точки этой прямой соответствуют одному и тому же значению целевой функции, равному d, одному и тому же уровню значений. Такая прямая называется линией уровня целевой функции.

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

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

Однако, существует более простой способ. А именно, изобразим в координатной плоскости вектор, начало которого находится в начале координат, а конец которого упирается в точку с координатами ( c ₁, c₂), где c ₁ и c₂ — коэффициенты при переменных в целевой функции. Это градиент целевой функции. Этот вектор-градиент перпендикулярен всем линиям уровня целевой функции, а его направление указывает направление роста значений функции.

На Рис. 2.1 изображен градиент, направленный внутрь первого координатного угла. Это означает, что коэффициенты c ₁ и c ₂ положительны. Разумеется, это не во всех задачах так, в разных задачах знаки этих коэффициентов могут быть различными. Начало градиента всегда располагается в начале координат, но направлен он может быть в любую сторону.

Для того чтобы найти оптимальный план, нужно взять одну из линий уровня, пересекающих область допустимых планов. Затем следует параллельно смещать эту линию в направлении градиента до ее . Крайним называется положение линии уровня, удовлетворяющее двум условиям: во-первых, в этом положении линия уровня еще пересекает область допустимых планов, во-вторых, при любом ее дальнейшем смещении она перестает пересекать эту область.

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

На Рис. 2.1 множество оптимальных планов состоит из одной единственной точки — вершины многоугольника, обозначенной посредством X*_max .

Заметим сразу, что если бы требовалось решать задачу на минимум той же самой целевой функции, то смещать линию уровня следовало бы в направлении уменьшения ее значений, то есть в направлении, противоположном градиенту (или, как иногда говорят, в направлении антиградиента ). Линия уровня в новом крайнем положении прошла бы через точку X*_min ( Рис. 2.1 ).

Если изменить знаки коэффициентов целевой функции c₁ и c₂ на противоположные, то градиент развернется на 180 о , то есть совпадет с антиградиентом первоначальной целевой функции. Если отыскивать минимум этой новой целевой функции с измененными знаками, то следует смещать линию уровня в направлении антиградиента по отношению к новому градиенту, то есть в направлении прежнего градиента. Мы убеждается еще раз, что решение задачи на минимум для целевой функции с измененными знаками соответствует задаче на максимум исходной целевой функции.