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

…

b_m0

b₁₁ … b_1s … b_1,n-m

……………………………………

b_k1 … b_ks … b_k,n-m

……………………………………

b_m1 … b_ms … b_m,n-m

f= b₀₀ b₀₁ …b_{0 s} …b_0,n-m

Используются и другие формы симплексных таблиц, но принятая нами форма является наиболее компактной и наглядной. В ней содержится вся необходимая информация о ходе решения задачи. Если, как предполагалось выше, все b_{i 0} >0, то при нулевых значениях верхних (свободных) переменных столбец свободных членов дает значения базисных переменных опорного плана x_о = (b₁₀ ;…;b_{m 0} ;0; ... 0) и соответствующее значение b₀₀ целевой функции: f(х₀ ) = b₀₀ .

От табличной записи легко перейти к обычной записи уравнений. Для этого надо умножить элементы b_kj k-й строки на соответствующие переменные, стоящие в заглавной строке (-x_{m + i} ), полученные произведения сложить и сумму приравнять x_k Тогда

b_ko *1 + b_k1 (—x_m+l )+ … +b_ks {—x_m+s )+ ... + b_k ,_n-m (—x_n ) =x_k илиx_i = b_i0 -∑ b_ij x_{m+1 .}

4. Критерии оптимальности

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

1. По условию задачи составляется ее математическая модель.

2. Составленная модель преобразовывается к канонической форме. При этом может выделиться базис с начальным опорным планом.

3. Каноническая модель задачи записывается в форме симплекс-таблицы так, чтобы все свободные члены были неотрицательными. Если начальный опорный план выделен, то переходят к пункту 5.

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

5. Найденный начальный опорный план исследуется на оптимальность:

а) если в f-строке нет отрицательных элементов (не считая свободного члена), то план оптимален. Если при этом нет и нулевых, то оптимальный план единственный; если же есть хотя бы один нулевой, то оптимальных планов бесконечное множество;

б) если в f-строке есть хотя бы один отрицательный элемент, которому соответствует столбец неположительных элементов, то f→ ;

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

Важно заметить, что поскольку minf= — max( —f), задачу минимизации f можно формально заменить задачей максимизации функции (—f). Но можно этого и не делать. Признаком оптимальности опорного плана задачи минимизации является отсутствие положительных элементов в f-строке симплекс-таблицы, содержащей опорный план. В остальном вычислительная процедура не меняется.

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

1) просматривают строку, отвечающую какому-либо отрицательному свободному члену, например t-строку, и выбирают в ней какой-либо отрицательный элемент, а соответствующий ему столбец принимают за разрешающий (предполагая, что ограничения задачи совместны);

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

3) из симплексных отношений выбирают наименьшее. Оно и определит разрешающую строку. Пусть ею будет, например, р -строка;

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

4.1 Признак оптимальности опорного плана

Если в симплекс-таблице, содержащей некоторый опорный план, все элементы f-строки (не считая свободного члена) неотрицательны, то этот опорный план является оптимальным.. Пусть в f-строке табл. 2.b_{0 j} > (i=1, ..., nm). В опорном плане х₀ , содержащемся в этой таблице, значения всех свободных переменных x_{m + j} равны нулю и f(х₀ ) =b₀₀ . Если же увеличивать какую-либо из свободных переменных x_{m +} j, то, как видно из равенства (2.5), в силу неотрицательности b_{0 j} значение f(х) начнет уменьшаться. Следовательно, при x_о функция f(х) достигает наибольшей величины, а значит, х₀ действительно является оптимальным опорным планом.

4.2 Возможность переход от одного опорного плана к другому