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

Процесс решения данной ЗЛП приведен в табл. 3.9. Таблица 8.8 81 Столбец свободлыл чле- 1!омер итерации, точ- Базис- лый Небазлслые столбцы Рис. З.Е а' з ! хз+ х2 9, Зхз — х2 3, х2~ 3, х1> О, х2> О. (3.15) 1.33 — 0,33 0 ... 0,75 лб= 3 — х2+ лз, а также искусственную функцию ю= па+ уб. 0,25 0,75 Рис.

330 3,75 82 83 От отрнцательного элемента — 1 в 1'-строке невозможно избавиться, так как в единственвом разрешающем столбце нет положительных элементов, что является признаком неограниченности решения ЗЛП. Нет конечного решения данной ЗЛП. Результаты прнмевевия графического метода к решенпю данной ЗЛП изображены на рис. 3.9. Теперь продолжим выполнение варианта задаяня Тт'и 20. Найдем решение второй ЗЛП: ш1п ~35 — Зх1 — 4х2 ~ Х Результаты применения графического метода к решению второй ЗЛП приведены на рнс. 3.10.

Минимум функции дости- гается в точке Хйбм (3;6) с у~Х®)= 2. Нандем снмплекс-методом решение второй ЗЛП. Для этого вводим дополнительную базисную переменную р1= 9 — х1 — х2, дополнительные небазисные переменные р 2 н уз, искусственные базисные переменные л а — — 3 — Зх з+ х2+ л2, Процесс решения заданной ЗЛП приведен в табл. 3.10. Таблица 3.10 ш(в (35 — 3 х1 — 4 х 2) Х (3.16) при ! х1+ х2~ 9, Зх1 — х2~ 3, х2= 3, х1> О, х2> О. (3 17) Вводим дополнительную базисную переменную у 1 = 9 — х 1 — х 2, дополнительную небазисную переменную уз, искусственные ба- Минимум функции У(Х) достигается в точке Х = (3;6) с 12) у'( Х(з))= 2. Согласно порядку выполнення работы для второй ЗЛП необходимо было вначале вручную симплекс-методом осуществить только итерации по сведению ю к нулю (е данном случае итерации й = О, 2 ), а также составить таблицу на последнее итерации, заполнив в ней только три строки базисного столбца и столбца свободных членов (в данном случае х1= 3, х2= 6 и — 1= — 2), содержимое которых известно из решения ЗЛП графическим методом.

Затем всю таблицу целиком следует получить на ЗВМ. Из рис. 3 10 видно, что полученные симплекс-методом допустимые базисные решения Х я Х~~ соответствуют верши- 12) нам выпуклого множества ХВ допустимых значеинй Х, задаваемого ограничениями (3.15). Отметим, что при решении 'любой ЗЛП общего вида базисное решение Х соответствует началу координат (как н в слу- 10) чае ЗЛП частного вида), а базисяое решенве Х вЂ” бляжай- (1) шей к ляпни постоянного уровня )(Х) = со точке пересечения одной из прямых, которой принадлежит сторона многоугольника ХВ, с осью координат Ох 1 или Ох 2. Функция )о сводится к нулю в первой достигнутой по симплекс-методу точке области ХВ (в данном случае в точке Х ).

12) На этом заканчивается решение второй ЗЛП для варианта задания У= 20, Дополнительно найдем решение двух других ЗЛП общего вида. Определим симплекс-методом зисные переменные уз — — 3 — Зх + х2+ у и у = 3 — х, а та 1 2 2 4 2' же искусственную функцию и = у З + у 4 . Процесс решения данной ЗЛП приведен е табл. 3.11. Минимум функции 7'(Х) достигается в точке Х(~)= (6;3) с г( Х1~))= 5. Результаты применения графического метода к решению ЗЛП (3,16) — (3.17) представлены на рис.

3.11. Областью ХР допустимых значений является отрезок ~ Х12), Х12) ). Из 9 рис. 3.11 видно, что полученные симплекс-методом з допустимые базисные реше- 9 2 3 Х,+ХзЕ9 ния Х( ) и Х1 ) соответстзу- лп) ют аершянак выпуклого мно- :, х;з. жества ХВ. Отметим, что при я= 2, с з 3 й а одном ограничении типа Ху равенства и других ограничениях типа неравенств об- ~()=9Г ласть ХР допустимых значений Х либо отсутствует, Рзс. 3.11 если заданная с помощью равенства прямая проходит вне области ХР1, полученной на основе остальных ограничений типа неравенств, либо в противном случае представляет собой принадлежащий области ХВ1 отрезок прямой, заданной равенством. В этом случае либо минимум достигается в одном из двух концов данного отрезка, а максимум — в другом, либо одновременно максимум к минимум достигаются во всех точках отрезка, если он параллелен линии постоянного уровня функции у'(Х) = с О' При и= 2, двух огранвченнях типа равенств и других ограничениях тина неравенств область ХР допустимых значений либо отсутствует, либо ею является точка пересечения двух прямых, заданных ограничениями типа равенств, если данная точка принадлежит области ХР1, заданной остальными ограничениями типа неравенств.

В этом случае оптимальное решение (минимум и максимум одновременно) достигается в единственной точке ХВ. Таблица 3.11 Решим симплекс-методом ЗЛП ппп ~2х1+ Зхз) х (3.18) при ! Зх1+ 5х2< 15, х1+ х2> 7, х1> О, х2> О. (3.19) Вводим дополнительную базисную переменную у = 15— — Зх1 — 5х2, дополнительную небазисную переменную р, нс- 2' кусственную базисную переменную уз= 7- х1 — х + у н ис- 2 2 кусственную функцию ю= уз. Процесс решения заданной ЗЛП приведен в табл.

3.12. Таблица 2.12 37 Ркс. ЗА2 СОДЕРЖАНИЕ ОТЧЕТА Все элементы строки — и в небазисных столбцах — неотрицательные, а им О, что является признаком недопустимоств решения данной ЗЛП. Результаты применения графического метода к решению ЗЛП (3.18)— (3,19) приведены ва рис. 3.12. Не существует области ХП допустимых значений Х и решения даннов ЗЛП. 10. Выводы на основе анализа результатов решения ЗЛП с помощью графического метода н симплекс-метода.

КОНТРОЛЪНЪ|Е ВОПРОСЫ И ЗАДАЧИ 1. В чем состоят ЗЛП, их геометрическая интерпретация и графический метод рергенвя ЗЛПУ 2. На чем основан симплекс-метод решения ЗЛПР 3. В чем заключается алгоритм решения ЗЛП симплекс-методому 4. Что является признаками неограниченности решения ЗЛП„ множества ее оптимальных решений, недопустимости решения ЗЛПР 5. Найдите решение заданной преподавателем ЗЛП с помощью графического метода и симплекс-метода. 1. Наименование работы. 2. Цель работы. 3. Решаемые задачи согласно Вашему варианту задания. 4.

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

6. Решение второй ЗЛП графическим методом. 1. Полученная с помогцью симплекс-метода таблица решения второй ЗЛП на итерациях от нулевой до той, ва которой искусственная функция ю была сведена к нулю, и на последней итерации. В таблице на первых указанных итерациях должны быть заполнены все графы, а на последней итерации — только те графы, содержимое которых найдено по результатам решения второй ЗЛП графическим методом. 8. Полученные на ЗВМ распечатки с результатами решения на всех итерациях трех задач: первой ЗЛП по нахождению максимума заданной функцив, первой ЗЛП по поиску минимума и второй ЗЛП, 9.

Изображение навденных симплекс-методом на всех итерациях Й точек Х на рисунках с результатами решения двух ЗЛИ (й) графическим методом. ЛИТЕРАТУРА ОГЛАВЛЕНИЕ ,30 Литература .90 90 1. Банди Б. Методы оптимизации, — М,: Радио и связь, 1988. 2. Банди Б. Основы линейного программирования. — М.: Радио и связь, 4989. Работа 1. Методы решения задач безусловной оптимизации Работа 2. Методы решения задач условной оптимизации Работа 3, Методы решения задач линейного программирования .