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

 

В частном случае общей задачи ЛП система уравнений имеет предпочитаемый вид, при этом правые части всех уравнений неотрицательны.

Допустим необходимо минимизировать целевую функцию L=c₁x₁+c₂x₂+...c_nx_n (1), при условиях:

x₁      + g_1,m+1x_m+1 + ... + g_1nx_n = h₁,

x₂ + g_2,m+1 x_m+1 + ... + g_2nx_n = h₂, (2)

...     ...               ...  ...

x_m + g_m,m+1 x_m+1 + ... + g_mnx_n = h_m

и x_j≥0, j = 1,2,...n (3).

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

Из выражения L=L₀-∆_m+1x_m+1-...-∆_nx_n (1) следует, что базисное решение x₁=h₁, x₂=h₂,...x_m=h_m, x_m+1=0,...x_n=0 (2) является оптимальным решением задачи ЛП

Базисное решение является единственным оптимальным решением задачи ЛП тогда и только тогда, когда в уравнении среди коэффициентов при неизвестных нет ни одного положительного, т. е. условие оптимальности имеет вид ∆j≤0 , j=1,2,…,n.

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

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

положителен, а в первых m уравнениях той же системы среди коэффициентов g_1j, g_2j, …g_mj при ней нет ни одного положительного, то задача линейного программирования неразрешима в силу неограниченности линейной формы L=c₁x₁+c₂x₂+...c_nx_n на множестве неотрицательных решений системы ограничений

 

29Доказать, что если при решении задачи линейного программирования:

симплексным методом в качестве начального базиса выбирают базис из дополнительных переменных, для которых с_i, = 0, то оценки для всех небазисных (свободных) переменных

будут равны , а соответствующее значение целевой функции

При дополнительных переменных коэффициенты целевой функции равны0      

При базисном решении все свободные переменные равны нулю,

 

 

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

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

алгебраических уравнений с бóльшим числом неизвестных и привести задачу к каноническому виду основной задачи линейного программирования. Эти неизвестные называют балансовыми или дополнительными. Правило введения: если неравенство со знаком «≤» , то добавляем в левую часть +Х_m+I,если «≥», то -Х_m+i

 

В каких задачах применяется симплекс-метод?

 

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

 

 

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

---

Дата добавления: 2018-06-01; просмотров: 689; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!