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

Тест по предмету «Методы оптимальных решений» с ответами

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

Тест по методам оптимальных решений онлайн

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Лекция 3: Математическое программирование. Линейное программирование. Виды задач линейного программирования. Постановка задач линейного программирования и исследование их структуры. Решение задач линейного программирования симплекс-методом

1. Понятие математического программирования

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

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

Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.

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

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

2. Понятие линейного программирования. Виды задач линейного программирования

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

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

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

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

Общая форма задачи имеет вид: найти при условиях

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

Задача ЛП в канонической форме:

( 2.1)

( 2.2)

( 2.3)

Задача ЛП в стандартной форме:

Задача ЛП в общей форме сводится (в определенном смысле) к задаче ЛП в канонической (стандартной) форме. Под этим понимается существование общего способа построения по исходной задаче (в общей форме) новой задачи ЛП (в нужной нам форме), любое оптимальное решение которой «легко» преобразуется в оптимальное решение исходной задачи и наоборот. (Фактически, связь между этими задачами оказывается еще более тесной). Тем самым мы получаем возможность, не теряя общности, заниматься изучением задач ЛП, представленных либо в канонической, либо в стандартной форме. Ввиду этого наши дальнейшие рассмотрения задач ЛП будут посвящены, главным образом, задачам в канонической форме.

Источник

Лекция 3: Математическое программирование. Линейное программирование. Виды задач линейного программирования. Постановка задач линейного программирования и исследование их структуры. Решение задач линейного программирования симплекс-методом

1. Понятие математического программирования

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

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

Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.

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

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

2. Понятие линейного программирования. Виды задач линейного программирования

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

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

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

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

Общая форма задачи имеет вид: найти при условиях

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

Задача ЛП в канонической форме:

( 2.1)

( 2.2)

( 2.3)

Задача ЛП в стандартной форме:

Задача ЛП в общей форме сводится (в определенном смысле) к задаче ЛП в канонической (стандартной) форме. Под этим понимается существование общего способа построения по исходной задаче (в общей форме) новой задачи ЛП (в нужной нам форме), любое оптимальное решение которой «легко» преобразуется в оптимальное решение исходной задачи и наоборот. (Фактически, связь между этими задачами оказывается еще более тесной). Тем самым мы получаем возможность, не теряя общности, заниматься изучением задач ЛП, представленных либо в канонической, либо в стандартной форме. Ввиду этого наши дальнейшие рассмотрения задач ЛП будут посвящены, главным образом, задачам в канонической форме.

Источник

Научная электронная библиотека

Оразбаев Б. Б., Курмангазиева Л. Т., Коданова Ш. К.,

4.1. Модели операций. Задачи математического программирования

1. Задачи математического программирования.

2. Линейное программирование. Интерпретация задач линейного программирования.

3. Задача распределения ресурсов. Аксиомы линейности.

1. Задачи математического программирования

Основная задача математического программирования. Рассмотрим множество:

(4.1)

Пусть скалярная функция f(x) определена на множестве Х. Задачу минимизации функции f(x) на множестве Х будем называть основной задачей математического программирования.

Форма записи задачи математического программирования.

(4.2)

или, ей эквивалентный запись:

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

1) либо найти оптимальную точку x* ∈ X:

2) либо, если существует такая х*, то найти

где inf f(x) – нижняя граница функции f(x).

3) либо: убедиться в том, что Х = ∅.

Если множества Х выпукло и выпукла функция f(x), то задачу (4.2) называют задачей выпуклого программирования.

Множество Х в задаче (4.2) называют допустимым множеством, точки этого множества – допустимыми точками; множество – исходным множеством альтернатив; неравенство ϕj(x) ≥ 0, , определяющие допустимое множество – ограничениями. Точку
называют решением или оптимальной точкой. Точку х, в которой выполняется необходимые условия, локального минимума функции f(x) на множестве Х, будем называть стационарной.

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

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

при

Общую задачу математического программирования разбивают на задачи, названия которых определяются видом оптимизируемой функции, функций, входящих в условия – ограничения, типом переменных и алгоритмом решения:

– линейного программирования f(x), ϕj(x), hj(x) – линейны;

– нелинейного программирования – хотя одна из функций f(x), ϕj(x), hj(x) нелинейные;

– квадратичного программирования – f(x), является квадратичной функцией, ограничения (ϕj(x), hj(x)) нелинейные;

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

– целочисленного программирования функция f(x) – выпукла, ϕj(x), hj(x) – вогнутые, решения представляют собой целочисленные значения.

2. Линейное программирование. Интерпретация задач линейного программирования

Наиболее разработанными в математическом программировании являются задачи линейного программирования (ЛП) Модели ЛП занимают чрезвычайно важное место среди известных моделей экономических явлений и производственных процессов.

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

(4.3)

(4.4)

(4.5)

и минимизирует (максимизирует) линейную функцию:

(4.6)

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

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

Очевидно, задача максимизации целевой функции (с, х) при каких-либо ограничениях эквивалентна задаче минимизации –(с, х). При этом

Естественным ответом на вопрос о том, как решать сформулированную задачу ЛП (4.3)–(4.6), кажется следующий метод простого перебора: найти произвольное решение х1 системы (4.3)–(4.5), вычислить (с, х1), затем найти другое решение х2, вычислить (с, х2) и т.д. и среди полученного спектра значений целевой функции (с, х), выбрать наименьшее. Значение х, реализующее минимум целевой функции, будет решением задачи ЛП. Но этот путь перебора оказывается труднореализуемым или даже нереализуемым в силу сложности поиска допустимых решений задачи ЛП. Допустимая область имеет, вообще говоря, бесконечное множество точек и может являться многогранным множеством. Это, в частности, означает, что если D принадлежат две какие-либо точки, то D принадлежат и все точки, соединяющего эти точки.

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

Для простоты рассуждений рассмотрим задачу ЛП в двумерном пространстве.

Пусть ограничения задачи имеют следующий вид:

(4.7)

Требуется найти минимум целевой функции

Допустим, что система (4.7) совместно и соответствующее ей многогранное множество ограничено, т.е. является многоугольником. Очевидно, что каждое из неравенств (11.7) определяет полуплоскость соответственно с граничной прямой

и целевая функция принимает одно и то же значение f во всех точках прямой

где f – некоторая константа.

При изменении (уменьшение или увеличение) получаем семейство параллельных прямых, называемых линиями уровня функции c1x1 + c2x2. Предположим, что многоугольник и линии уровня имеют вид, представленной на рис. 4.1. Нас интересуют те точки многоугольника D, которые принадлежат линии уровня с наименьшим значением f. Известно, что если перемещать прямую c1x1 + c2x2 = f в направлении ее нормали с, то значение f будет убывать.

Выберем достаточно большое f и будем перемещать прямую c1x1 + c2x2 = f в направлении –с. При этом линии уровня (с, х) = f вначале впервые коснется многоугольника, потом пересчет его и, наконец наступит момент, когда она коснется многоугольника в последний раз. Из рис. 4.1 следует, что прямая будет соприкасаться с многоугольником в точках А и В, причем в А значение целевой функции минимально.

Если же многоугольник не ограничен, то может быть два случая:

1) прямая, передвигаясь в направлении –с, все время пересекает многоугольник D; в этом случае линейная форма не ограничена на допустимой области и ее минимум равен –∞;

2) в результате передвижения вдоль направления –с прямая становится опорной к многоугольнику D.

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

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

Теорема. Пусть допустимое множество D задачи линейного программирования (4.3)–(4.6) является многогранником. Тогда целевая функция (4.6) достигает своего минимума в вершине D. Если линейная форма принимает минимальное значение более чем в одной точке, то она достигает того же значения в любой точке, являющейся их выпуклой комбинацией.

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

(4.8)

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

Двойственной задаче (4.8), т.е.:

и переменным можно придать следующий смысл.

Пусть ui ≥ 0 – удельная оценка i-го ингредиента, измеренная в тех же единицах, в которых измеряется доход (убыток) каждой технологии. Тогда представляет собой суммарную оценку всех затрат предприятия, связанных с работой по j-й технологии с единичной интенсивностью. Ограничения же двойственной задачи

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

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

3. Задача распределения ресурсов. Аксиомы линейности

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

заданных линейными соотношениями.

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

Целью можно считать получение максимальной прибыли (целей может быть больше чем одна, что чаще всего имеет место).

Допустим, фирма реализует 1–4 технологических процессов. Технологические процессы 1 и 2 ориентированы на выпуск продукции А, 3 и 4 ориентированы на выпуск продукта В.

Расходы каждого технологического процесса определяются трудозатратами (в человеко-неделях), недельным потреблением материала Y и Z.

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

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

1. Делимость. Для каждого технологического процесса (Т.П.) суммарное потребление каждого из потребляемых ресурсов и прибыль пропорциональны объему выпускаемой продукции.

а) Т.е. все показатели Т.П. могут быть увеличены или уменьшены при сохранении их взаимной пропорциональности.

Для выпуска 10 единиц продукции x1 необходимо 10 человеко-недель, 70 единиц материала Y, 30 единиц материала Z. Доход составит 40 единиц.

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

При составлении производственного плана на неделю примем следующие производственно-экономические показатели и ограничения:

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

Принятие аксиом делимости и аддитивности эквивалентно утверждению о представлении математической модели в виде линейных соотношений. А именно: доходы строго пропорциональны затраченным ресурсам.

В реальных ситуациях такое утверждение можно принимать лишь приближенно.

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

4×1 + 5×2 + 9×3 + 11х4 ≡ max; (4.10)

1×1 + 1×2 + 1×3 + 1×4 ≤ 15 (колич. человеко-недель);

7×1 + 5×2 + 3×3 + 2×4 ≤ 120 (ед. материала Y); (4.12)

3×1 + 5×2 + 10×3 + 15×4 ≤ 100 (ед. материала Z).

Уравнение (4.11) определяет суммарную прибыль производственно-технологического процесса из табл. 4.1.

Источник