В каком случае базисное оптимальное решение задачи линейного программирования будет ее единственным оптимальным решением? Ответ обосновать
При выполнении условий оптимальности 
базисное решение будет единственным оптимальным решением задачи линейного программирования тогда и только тогда, когда все коэффициенты 
при свободных неизвестных в последнем уравнении вспомогательной системы 
строго отрицательны. Если же хотя бы один из коэффициентов при свободных неизвестных равен нулю, то будут и небазисные оптимальные решения. Действительно, если, например, 
, то как бы мы не изменяли в общем решении 
свободную неизвестную Xm+1 в ее неотрицательной области изменения при Xm+2 =…=Xn = 0 , целевая функция будет сохранять одно и то же значение, т. е. мы получим некоторую совокупность оптимальных решений задачи. Очевидно, оптимальных решений будет еще больше, если среди коэффициентов при свободных неизвестных в уравнении окажется несколько нулевых.
Доказать, что в случае отсутствия вырождения в задаче линейного программирования на нахождение минимума линейной функции преобразования по симплекс-методу приводят к конечной последовательности монотонно убывающих значений линейной функции
При выполнении условий оптимальности базисное решение будет единственным оптимальным решением задачи линейного программирования тогда и только тогда, когда все коэффициенты при свободных неизвестных в последнем уравнении вспомогательной системы строго отрицательны. Если же хотя бы один из коэффициентов при свободных неизвестных равен нулю, то будут и небазисные оптимальные решения. Действительно, если, например,
|
|
|
то как бы мы не изменяли в общем решении свободную неизвестную Xm+1 в ее неотрицательной области изменения при Xm+2=….=Xn=0, целевая функция будет сохранять одно и то же значение
т. е. мы получим некоторую совокупность оптимальных решений задачи. Очевидно, оптимальных решений будет еще больше, если среди коэффициентов при свободных неизвестных в уравнении окажется несколько нулевых.
В каком случае задача оптимального производственного планирования не имеет оптимального плана? Ответ обосновать
Если есть хотя бы одна свободная неизвестная, такая, что коэффициент при ней в последнем уравнении системы положителен, а в первых уравнениях той же системы
среди коэффициентов при ней нет ни одного положительного, то задача линейного программирования неразрешима в силу неограниченности целевой функции на множестве неотрицательных решений системы ограничений. Действительно, если, например Δn>0, в уравнении L=L0-∆m+1xm+1-...-∆nxn, но g1n<=0 g2n<=0 в предпочитаемой форме
системы ограничений, то в общем решении системы ограничений мы можем переменную xm+1=…=xn-1 неограниченно увеличивать, положив xn, и тогда, как видно из выражения L=L0-∆m+1xm+1-...-∆nxn, целевая функция будет неограниченно убывать и, следовательно, оптимального решения не существует.
|
|
|
В каком случае при решении задачи линейного программирования симплекс-методом значения линейной функции двух последовательных планов могут совпасть? Ответ обосновать
В каждом последовательном плане новое значение линейной функции приближается к оптимальному, пока не будет получено оптимальное решение или не будет доказана неограниченность линейной формы на множестве решений системы ограничений
Но это утверждение справедливо только при условии невырожденности рассматриваемой задачи, т. е. если ни на одном этапе процесса решения ни один из свободных членов системы уравнений (Hi) не обращается в нуль.
При 
новое значение линейной формы строго меньше предыдущего и через конечное число шагов мы придем к оптимальному решению или докажем неразрешимость задачи, так как число шагов не может быть больше числа базисных решений , среди которых неотрицательных значительно меньше. В вырожденном случае на одном или нескольких этапах свободный член разрешающего уравнения может оказаться равным нулю, и значение линейной формы не изменится.
|
|
|
28 Сформулировать теорему о связи решений исходной и вспомогательной задач при решении задачи линейного программирования методом искусственного базиса.
S=Xn+1+…..+Xn+m к мин Вспомогательная задача всегда имеет оптимальное решение, т.к. решая симплексным методом через конечное число шагов найдем оптимальное решение т.к. 1) система совместна 2)S>=0. Если оптимальное решение дает Smin=0, тогда исходная задача либо имеет оптимальное решение, либо уходит в минус-бесконечность
Дата добавления: 2018-06-01; просмотров: 671; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!