Курсовая работа: Последовательность решения задач линейного программирования симплекс-методом

…….. a_kj ……… a_ks ………

……………………………

Тогда из формулы непосредственно следует, что преобразованный элемент b_ij равен разности произведений элементов, расположенных на главной и побочной диагоналях, деленной на РЭ.

2. Идея симплекс метода

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

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

f=∑ c_i x_j (max)

∑ a_ij x_j = a_i0 (i=1,…,m)

x_j >0 (j= 1,…,n)

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

Рассмотрим суть симплекс-метода. Если в системе m<n и все m уравнений линейно независимы, иначе ранг системы равен m. Тогда система имеет бесконечное множество решений. Систему можно разрешить относительно m переменных, которым в матрице системы соответствуют линейно независимые векторы-столбцы. Обозначив эти переменные через x₁ ,…,x_m ,выразим их через свободные переменные x_{m +1} ,…,x_n

x_i = b_i0 -∑ b_ij x_m+1 (i=1,..,m)

Подставив значения x_i в целевую функцию, получаем:

f=b₀₀ - ∑ b_{0 j} x_{m + j}

Значения базисных переменных x_i и целевой функции f полностью определяются значениями свободных переменных x_{m + j} .

Положим, что все b_{i 0} >0. Тогда план x₀ =(b₁₀ ;…;b_{m 0} ;0…;0), полученный при нулевых значениях свободных переменных x_{m + j} , будет невырожденным опорным, а отвечающее ему значение функции f равно, как видно b_00.

Опорный план x₀ соответствует базису Б₀ ={x₁ ;…;x_m }.Для получения другого опорного плана преобразовывают базис Б₀ в новый базис Б₁ , удаляя из Б₀ одну переменную и вводявместо нее другую из группы свободных. При этом в базисе Б₁ опорному плану x₁ соответствует значение f(x₁ ), не меньшееf(x₀ )_. Действуя таким образом, переходят к близкому к оптимальному плану. Ввиду того что опорных планов не более С ,через конечное число шагов либо приходят к оптимальному плану, либо устанавливают, что задача неразрешима.

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

3. Построение начального опорного решения

Решение задач линейного программирования вручную наиболее рационально можно выполнять именно в табличной форме. В таблицу вписывают систему ограничительных уравнений и целевую функцию в виде выражений, разрешенных относите льно начального базиса Б_о = {х₁ ; ...; х_т } (табл. 2.). Левый столбец занимают базисные переменные и целевая функция, а верхнюю строку — свободные переменные . Нижнюю строку, в которую вписаны коэффициенты целевой функции f, называют f- строкой или строкой целевой функции.. За столбцом базисных переменных следует столбец свободных членов. Иногда f-строку помещают сразу же за заглавной строкой, а столбец свободных членов в конце; таблицы. Таблицы описанного вида называются симплексными.

Таблица 2

базисные переменные	1	свободные переменные -xm +1 … -xm + s … -xn
x1 = … xk = … xm =	b10 … « 1 2 3 4 5 6 7 » К-во Просмотров: 238 Бесплатно скачать Курсовая работа: Последовательность решения задач линейного программирования симплекс-методом >>> Скачать <<< Меню Поиск