Силаева Т.А. - Методы решения задач оптимального проектирования ВС (Методы решения задач оптимального проектирования ВС (Силаева Т.А.)), страница 10

из базисного столбца на последней итерации) равны свободным членам, находящимся в той же строке. Оптимальное значение функции при этом равно значению свободного члена в )-строке со знаком плюс прн нахождении максимума или минус лрк поиске икпнмума. Отметки, что если на некоторой итерации )г в у-строке в небазнснои столбце получен нулевой элемент, то это является призиакои множества оптимальных решений данной ЗЛП. Тогда необходимо провести еще одну итерацию !«+ 1 (с выбором небазнсыого столбца с нулевым элементом в )-строке в качестве разрешающего столбца), чтобы найти вторую оптимальную точку Х( ) с (ь+ 1) теи же значением функции в ней, что н в точке Х на лредыду(и) щей итерации )(.

Па итерации )г+ 1 в Устроке в небазиснои столбце тоже будет получен нулевой элемент. Оптимальным решением этой ЗЛП является все множество точек отрезка ~Х®,Х~~ параллельного линии уровня функции )(Х) = ср. 4. Конец алгоритма. Симплекс-метод Данцига для реы«еиня ЗЛП общего аида Решается задача ех(г г (Х), Х у(Х)= с,+ Х с.-х„ прк т ограничениях типа «<»л » <а ~, ()= 1,т), 1=1 ' сс ограниченыях типа «> с< » ~ а;хс> асс, (с= т+ 1,т+ 7с), (38) 1=1 и ограничениях типа «с< ~ч, а сх,.= а о, (~= т+ й+ 1,т+ (с+ и), (3.9) асс> О ()= 1,т+ й+ и), хс> О (с= 1,л). Алгоритм решения ЗЛП общего вида симплекс-методом состо- ит в следующем.

1. Вводим дополнительные и искусственные переменные и ис- кусственную функцию, а именно: 1.1. Вводим в (3.7) дополнительные переменные у < О ,1'= 1, т ), прибавляя по одной перемеыной в левую часть каж- ого ограйиченыя из (3.7), чтобы свеств неравенство типа «<» к равенству. Тогда (3.7) переписывается в ваде: » у = а — ~с а,хс (у= 1,т), (3.10) 1 1.2. Вводим в (3.8) дополынтельные переменные у.> 0 с= т+ 1, т+ й), со знаком « — » в левую часть ограничений, чтобы свести неравенство типа «<» к равеыству.

Прн етом в случае равенства нулю всех хс ( с= 1,и ) получим недопустимое решение у = — ась О, (/= т+ 1,т+ lс), / Поэтому в левую часть огранвчений (3.8) также вводят искусственные переменные у < 0 (~'= т+ й+ 1,т+ 2й), тогда (3.8) перепвсывается в виде л У. ь — — асс — ~Ч а,-хс+ У (/= т+ 1,т+ /с). (3.11) 1.3. Вводим в левую часть ограничений (3.9) искусственные переменные у.> 0 ()= т+ 2й+ 1 „т+ 2й+ и, тогда из (3.9) получаем » УУ+»= а Π— ~~с~ а,-хс (~= т+ й+ 1, т+ й+ и) (3.12) 1А. Вводим искусственную функцию сл, равную сумме всех искусственных переменных: »+и Ссс и са — ~ у»с»ь»с — .4, ам+с О /=1 7= 1 я+и 1 Х ам+21 7=1 Сс+ а Ссс а х »««т+ь»+ Х У»с»с' 7=1 !=1 (3.13) хс= 0 у .=0 Уу= асс уо (=' ") (=") ,с'= т+ 1,т+ 7«+ и 2.

По соотношениям (3.10) — (3.13), полученным из ограничений (3.7) — (3.9), и выражению (3.6) для целевой функции ДХ) формируем первоначальную табл. 3.4 на итерации О. За небазисные переменные, записанные в табл. 3.4 со знаком «-» в первую строку в небазысные столбцы, принимаем хс, ...,х„и дополнительные переменные у 1, ...,у +ь, полученные из ограыичеыий (3.8) типа «>», За базисные принимаем остальные перемеывые. Находим первое допуствмое базисное решение: все небазисные переменные х; (с= 1,и) и у +. ()= 1,й) таблицы 3.4 принимаем равными нулю, а каждый у (~' = 1, т ) и у . 7+я с= т+ 1,т+ й+ и) в базисном столбце приыымаем равным свободному члену, находящемуся в его строке, т.е.

70 Ф 3 о Ф ф 3 о ф Ф Ф Ф Ф ф а Н Ф о о„ ~' а о Ф Ф О Ф ф Ф л ф Ф а ф Ф О З Ф3 ф Ф Ф Ф ф 3 Ф о Ф о фг ф Ф ф Ф "Ф ф \ 3 а Ф о о ф ф Ф Ф Ф о Ф Ф и о Ф ф Ф Ф о ф Э Ф а о ф Ф О ю Ф м в. Ф 3 'о Ф о ) н Ф Ф,Ф Ф Ф Ф Ф Ф 3 о о. Ф о о Ф о а о ВАРИАНТЫ ЗАДАНИЯ Для каждого номера варианта УФ 1,20 в табл. 3.5 заданы две ЗЛП. Таблица 8.5 73 72 3. Искусственная функция ю нужна для нахождения на качальных итерациях базисных решений вплоть до нахождения первого допустимого базисного решения, при котором функция ю становится равной нулю, как и все искусственные переменные (получается первоначальный вид ограничении).

Затем находится оптимальное решение ЗЛП с оптимальным значением функции У. Поэтому решение ЗЛП выполняем в два этапа: 3.1. Проводим итерации, начиная с нулевой (заключающнеся в выборе разрешающего элемента и осуществлении шага модифицированного жорданова исключения с этим элементом), по минимизации функции ю. Зтот этап заканчиваем, когда и становится равной пулю (стоящему в строке -ю в столбце свободных членов), а все искусственные переменные — яебазисными, т.е. тоже равными пулю. Следовательно, в этом случае в строке -и будут стоять все нули, за исключением столбцов, соответствующих искусственным переменным, там будут 1. Тогда вычеркиваем строку — и и столбцы, соответствующие искусственным переменным.

Отметим„что если не удается свести и к нулю, а все элементы в строке — и в небазисных столбцах болыпе или равны нулю, то это является признаком недопустимости решения рассматриваемой ЗЛП. Не существует области Х1л допустимых значений Х и решения данной ЗЛП. В этом случае переходим к и. 4. 3.2. Продолжаем итерации уже по оптимизации функции ,Т(Х) .

Завершаем, когда все злементы в этой строке в небазнсных столбцах становятся больше нуля (или все болыпе нуля„кроме одного нулевого элемента, тогда проводим еще одну последнюю итерацию). 4. Конец алгоритма. Окончание табл 3 б Продолжение табл. З,б Номер зараантз Ф Вторая ЗЛП Первая ЗЛП юзх (б+ 4х1+ 2" г) х х,+ Загс 5, хги 1 Зх1+ хгг 3 сб,х О. пнп (10- 2хг- 3хг), х )х,+ха~7, х — х с3, ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ Для Вашего варианта задания необходимо: 1. Опрсделить решение первой ЗЛП с помощью графического метода.

2. Согласно симплекс-методу для первой ЗЛП выполнить итерации 0 и 1 (если процесс поиска экстремума не заканчивается на итерации 0) по нахождению как минимума, так и максимума заданной функции, а также составить таблицу на последней итерации, заполнив в ней только те графы, какие могут быть заполнены исходя из полученной в п. 1 информации о решении первой ЗЛП.

3. Определить решение второй ЗЛП с помощью графического метода. 4. Симплекс-методом выполнить для второй ЗЛП такое число итераций, чтобы искусственная функция ю была сведена к нулю, а также составить таблицу на последней итерации, заполнив в ней только те графы, по которым имеется информация исходя нз полученного в п. 3 решения второй ЗЛП графическим методом. 5. Показать полученные результаты преподавателю. б. Выполнить на ЗВМ решение симплекс-методом каждой из двух ЗЛП, получив две распечатки для первой ЗЛП по нахождению минимума и максимума заданной функции и одну распечатку для второй ЗЛП. 77 Таблица д,б ПРИМЕР 1) ехьг (2+ бх + 2х ) 2Х1+ 4Х2~ 9 Х1+ Х2( 3 Х1а О, х2> о (3.14) 2) ш( и ( 35 — 3 х 1 — 4 х 2 ), х1+ Х2< 9, Зх1 — х2> 3, хз> 3 х1> О, хзл О.

Таблица 8.2 у =9 — 2х -4х2>0; 1 1 у2= 3- х1 — х2~ О. Процесс определения минимума при ре1пенив заданной ЗЛП симплекс-методом представлен в табл. 3.6. точке Х(1= (3.0) ,1'(Х( 1)= 20. Риа 3.7 79 7. Изобразить полученные свмплекс-методом в и. 6 на всех итерацвях )с точки Х( на рисунках с результатами решения а) каждой из двух ЗЛП графическим. методом. Выполнить на ЗВМ решение каждой ЗЛП графическим методом.

8. Сформулировать выводы. Пусть номер варнанта задания )У= 20. Тогда заданы следующие дзе ЗЛП: Найдем решение первой ЗЛП. Результаты применения графического метода к решению данной ЗЛП приведены на рис. 3.7. Функция у(Х) имеет минимум в точке Х(о) = (О; 0) с г(Х(Ф) = 2 и максимум в точке Х( '= (3; 0), У(Х(0) = 20. Решим первую ЗЛП симплекс-методом. Для етого введем дополнвтельные переменные: Все злементы 7-строки в небазвсных столбцах неотрнца ные, позтому процесс нахождепня минимума функции завершается на втерацив О. Функция ДХ) имеет минимум е точке Х 1Ф = (О; 0) с у ( Х ( ) 1= 2. Процесс нахождения максимума при решения заданной ЗЛП скмплекс-методом приведен в табл.

3.7. Функция ~(Х) имеет максимум в Из сравнения результатов решения первой ЗЛП симплекс-методом и графическим методом (см, рис. 3.7) видно, что допустимые базисные решения Х и Х соответствуют вершинам вы- (О> (1> пуклого множества Хь) допустимых значений Х, задаваемого ограничениями (3 т4).

На этом заканчивается решение первой ЗЛП для варианта задания Ж= 20. Дополнительно найдем рспгение двух других ЗЛП. Решим симплекс-методом ЗЛП пил (2 — бх1 — 2хг) при Х 2х1+ 4хг~ 9, Зх>+ хгь 6 х>а О,хг> О. Процесс решения данной ЗЛП приведен в табл. 3.8. Таблица 8.8 На и а ~ервой и втором итерациях в у-строке в небазисном столбце получен нулевой элемент, что является призна- р ком множества оптимальных л решений данной ЗЛП. На этих итерациях получены решения ЗЛП: Х( >= (2;О) и н уб ) Х = (1,5; (,5) с одинако- О,го щ ~" >, т.

х зым минимальным значением чв>..т <а ( > ' ' .(г> ' Х еи = — (О, Минимум этой ЗЛП .' лгайО достигается на множестве точек отрезка ~Х( >, Х( >), параллельного линии уровня р . з.а функцвн г"(Х) = 2. Результаты применения графического метода к решению данной ЗЛП приведены на рис. 3.8. Решим симплекс-методом ЗЛП шах (х + 2х ) прн х х г прн ограни- ченнях хг< 2, х1> О, хга О.