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

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

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

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

Таблица 2

Используются и другие формы симплексных таблиц, но принятая нами форма является наиболее компактной и наглядной. В ней содержится вся необходимая информация о ходе решения задачи. Если, как предполагалось выше, все bi0>0, то при нулевых значениях верхних (свободных) переменных столбец свободных членов дает значения базисных переменных опорного плана xо= (b10;…;bm0;0; ... 0) и соответствующее значение b00 целевой функции: f(х0) = b00.

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

bko*1 + bk1 (—xm+l)+ … +bks{—xm+s)+ ... + bk,n-m(—xn) =xk или xi = bi0 -∑ bij xm+1 .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Докажем этот признак. Установим правила выбора переменных для такого преобразования начального базиса Бо с опорным планом х0 в новый базис Б1 с опорным планом х1 при котором; значение функции f увеличивается, т. е. f(xi)>f(x0). Тогда по правилу пересчета элементов из симплекс-таблицы преобразуем к новому базису, что позволит найти компоненты нового опорного плана.

Допустим, что в табл. 2.1, например, b0s<0, а среди элементов bis s-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные хm+j кроме xm+s, равными нулю, получаем f = boo — bos xm+s . Из этого равенства видно, что при увеличении xm+s значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых xm+s принимает положительные значения, а все остальные компоненты xm+j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Бо в новый базис Б1. В самом деле, если переменная xm+s принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане xо она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной xm+s. Но здесь предстоит решить два вопроса:

Страницы: 1, 2, 3