Дьяконов В.П. Maple 9.5 и 10 в математике, физике и образовании (1185901), страница 59
Текст из файла (страница 59)
†.857142857142857094 3.57142857142857162 2.57)42857142857162 -.428571428571428548 .799999999999999820 3.19999999999999972 Таким образом, видно, что Мар[е в данном случае реализует типовые матричные операции, но средствами системы МАТ).АВ. Загрузка последней происходит автоматически при загрузке пакета МАТ[.АВ. Если система МАТЕАВ не установлена на вашем компьютере, то доступ к функциям пакета Ма()аЬ будет отсутствовать, а Мар!е при попытке использования данных функций будет выдавать сообщения об ошибках.
6.5. Линейная оптимизация и линейное программирование 6.5.1. Постановка задачи линейного программирования В общем случае задача линейного программирования может быть сформулирована следующим образом: найти максимум или минимум целевой 4ункции ,Г'(Х) = ( с .хт иа при ограничениях ~ад.ху = [), х. а О, ц > О, ! = 1 ... и, 7 = 1 ...
и. 7! 414 Глава б. Регавние задач ланейиай алгвйры, оптимизации и регрессии Зля решения задач линейного программирования разработано большое количество различных методов. При анализе моделей с двумя или тремя переменными часто используются графические построения на плоскости или в пространстве. Среди универсальных методов решения наиболее распространен сил~плексный метод. Симплекс это многоугольник, перемещаемый в пространстве решения таким образом, что бы постепенно сужаясь он мог охватить точку искомого решения, отвечающую решению задачи с заданной погрешностью. При этом методе задается некоторое начальное приближение, удовлетворяющее всем ограничениям задачи, но не обязательно оптимальное.
Оптимальность результата достигается последовательным улучшением исходного варианта за определенное число шагов (итераций). Направление перехода от одной итерации к другой выбирается на основе критерия оптимальности целевой функции задачи. Реализовывать симплекс-метода вручную — громоздко и сложно. Системы компьютерной математики имеют средства решения задач оптимизации, в том числе и симплекс-методом. Рассмотрим примеры решения несколько типичных задач линейного программирования с помощью таких средств системы Мар!е 9.5. 6Л.2. Обзор средств пакета вйпр1ех В пакете зппр!ех системы Мар!е имеется небольшой, но достаточно представительный набор функций и определений для решения задач линейной оптимизации и программирования: > еггп(агврзех) Иагпгпо, Гье ргосессег! павеа вахгв! ае апо вгпзваге паче Ъееп гес1еГЬпео апб ппргогесгег! [бааз, сопгехйии.
сгегт, Нерпе гего, йзр1ау, дига1,Гваяые, тихгтгее. тттиее, риог, рпогедп, рптхаг, гине, зегир, з(апдагй~е1 Приведем краткое назначение этих функций: ° Ьаа!а — возврат списка основных переменных для множества линейных уравнений; ° сопчехЬЫ! — вычисление выпуклой оболочки для набора точек; ° с1епп — задание констант для системы уравнений или неравенств; ° тейпе аего — определение наименьшего значения, принимаемого за ноль (по умолчанию увязано со значением системной переменной Р1о11а); ° г!!ар!ау — вывод системы уравнений или неравенств в матричной форме; ° с!ца1 — выдача сопряженных выражений; ° еоца111у — параметр для функции сопчеП, указывающая на эквивалентность; ° 1еав!Ые — выяснение возможности решения заданной задачи: ° тахппае — вычисление максимума функции; ° п~!п1пхае — вычисление минимума функции; ° р1чо1 — создание новой системы уравнений с заданным главным элементом; ° р!чо1ецп — выдача подсистемы уравнений для заданного главного элемента; ° р!чошаг — выдача переменных с положительными коэффициентами в целевой функции; ° га1ю — выдача отношений для определения наиболее жесткого ограничения; ° ве1цр — задание системы линейных уравнений; ° а)апс!аглае — приведение заданной системы уравнений или неравенств к стандартной форме неравенств типа «меньше или равно».
415 6.5. Линейная оптимизация и линейное программирование 6.6.3. Переопределенные функции )пах)п)1ге и )п1п1гп)ге вахьвьге(г, С) вьп1в1ге(Т , С, вах1вь ге ( Т, С, вьпгвьге (Т, С, в1пьвйге(й, С) чаггуре) вахьвьге(й , С, чагсуре) уаггуре, 'НеиС', 'ггапайогв') иаггуре, 'МеиС', 'сгапаТогв') Здесь ! — линейное выражение, С вЂ” множество или список условий, чануре — необязательно задаваемый тип переменных А)ОА))чЕОАТ)НЕ или ()А))<ЕЗТЯ)СТЕО, А)е)нС и !гапв(опп — имена переменных, которым присваиваются соответственно оптимальное описание и переменные преобразования.
Ниже даны примеры применения этих функций «файл з)п)р)ех); > геагагггеьгл(а1вр1ех): Иаглглд, гле ргсгесгес павел вахьвьге ал<) вьл1вьге паче Ьеел ге<)ег1ле<) алс ллргогесгес( > вьлгв1ге( х+у, (4*х+3*у <= 5, 3*х+4*у <= 4), НОИНЕСАТТЧЕ ) «у =О, х =О» > вглгвьге( х-у, (4*х+2*у <= 10, 3*х+4*у <= 1б), ИОННЕ6АТ1ЧЕ,'ИС', 'чг' )' «у =4, х =О) > мс;ег; «51.1=2- — + —,у = — +4- — ) 5х Я2 И2 Зх 2 2 4 4 > вахьвгге( х+у, (4*к+2*у <= 10, 3*х+4*у <= 16), МОИНЕОАТХЧЕ ) 17 4 у=« —,х=-) 5 5 > вах1вьге( х+у, (З*х+2*у <= 5, 2*х+4*у <= 4 ] ) «у=-, х= — ) 1 3 4 2 > вахувгге( х+у, (3*х+2*у <= 3, 2*х+4*у <= 4 ) ] 1 3 «у= —,х= — ) 4 2 > г:= 2*х1 — х2 + 3*хЗ; г:=2х1-х2+ЗхЗ > спга1:=( х2+2*хЗ <= 1, 2*х1 — 4*х2 + б*хЗ <= 3, -х1 + 3*х2 + 4~хЗ 12 ); спи1:=«х2+2хЗ < 1, 2х1-4х2+бхЗ < 3, -х1+Зх2+4хЗ <!2) Главными из этих функций являются п]ах(п))ге и п))п))п)ге, оптимизирующие задачу симплекс-методом.
Они записываются в следующих формах: 41б Глава 6. Решеиие задач лииейиой алгебры, оптимизации и регрессии > ао11 := вах1вьге(г,соса1,НОНБЕОйт1ЧЕ) зо]1: = «х2 = 1, хЗ = О, х! = — ) 7 2 При использовании функций гп]п]п))2е и гпах(п)12е надо не забывать, что этг переопределенные функции — аналогичные по названию функции есть в ядре > они реализуют иные методы вычислений. Для возврата к исходному определеник функций надо выполнить команду геа!аг!. 6.5.4.
Прочие функции пакета в]гпр!ех Функция Ьав!а(С) возврашает базис для системы линейных уравнений С. На пример: > Ьааьа( [ х = 2*г+х, г = 2*у — х ) ) г [х, 2] Функция сопчехбцй(ра) возвращает выпуклую оболочку множества точек ра Например: > соочехьо) 1 ( ( [О, О), [1, 1], [2, -1], [1, 1/3], [1, 1/2) ) ): [[О, О], [2, -1], [1, 1]] Для определения констант для системы линейных уравнений или неравенст( служит функция с!епп(С): > сеегв( [2*х+у< 6,7'у-г-3=41): [б, 7] Функция с)ей(пе Еего(С) возвращает ближайшее ненулевое значение, завися шее от установки переменной О]п]!а: > 4(еггое гего() г .!000000000 )О 7 > Огогга:=40; 2](е]гз: = 40 > <(еггое гего П .1000000000000000000000000000000000000000 1О 37 > с(еггое гего[1*10"(-10!) .)000000000000000000000000000000000000000 1О 4 Функция (]]ар]ау(С) имеет еше и форму (йар)ау(С,[х, у, 2]).
Она задает вывод ли нейных уравнении и неравенств в матричной форме: > 4(гаР1аУ((2*х+5*У-г<= О, 2*в-4*У-4<=2]); 0 -4 2 -1 6.5. Линейная оптимизация и линейное программирование 417 Функция ()ца](1, С, у) имеет следующие параметры: ( — линейное выражение. С вЂ” множество неравенств и у — имя.
Эта функция возвращает сопряженное с ! выражение: > с]оа1 ( х-у, (2*х+3*у<=5, 3*х+б*у<=15>, х> ( ]521+522, (1< 321+2 22, - ! < 621+322) Функция (еая]Ые может быть задана в трех формах: Ееазйбуе (С) Теаз1Ь1е (С, чаггуре) йеазЬЬ1е(С,чагоуре,'МечС','Тгапзйогв') Здесь параметр чаг(уре может иметь значения ]чОМЬ>ЕСАТ)ЧЕ или []Ь>!!ЕЗТ[!!СТЕ[3. Эта функция определяет систему как осуществимую или нет: > геав[ь1е((2*х+3*у<=5, 3*к+6*у<=15], ионнебйт1не» ггие > Геавгьзе((2*х+3*у<=5, 3*х+б*у<=-15], НОННЕбйТ1ЧЕ); 1д!зе Если функция возвращает логическое значение (п]е, то заданная система осуществима, а если (а]яе — неосушествима, то есть ни при каких значениях переменных не способна удовлетворить записанным неравенствам и равенствам.
Функция р]чо1(С, х, е()п) конструирует новую систему с заданным главным элементом: > р1чог (( ЯЬ1=5-4*х-З*у, ЯЬ2=4-3*х-4*у], х, [ ЯЬ1=5-4*х-3*у] ); (х = — — 5Е1+ — — -у, 5Е2 = — + — 5Е1 — — у) 1 5 3 ! 3 7 4 4 4 4 4 4 Функция р]чо(е(]п(С, чаг) возвращает подсистему для заданного диагонального элемента С: > рвчогеяо( ( ВЬЬ = 5-3*х-2*у, ВЬ2 = 4-2*х-2*у], х ); 5Е1 = 5 — Зх -2 у) Функция р]чо1чаг(1, Ыв1) или р]чо1чаг(() возврашает список переменных, имеющих положительные коэффициенты в выражении для целевой функции: > рвчогчаг( х1-2*х2+3*хЗ-х4); х1 > ргчогчаг( х1 + 2*хз — З*х4, [х4,хЗ,х1) ); хЗ Функция гаво(С, х) возвращает список отношений, задаюших наиболее жесткие ограничения: > гас1о( [ ЯЬ1=10-3*х-2*у, ВЬ2 8-2*х-4*у],х ); [ —, 4] Функция Ве1цр может иметь три формы: зеецр (С) зегцр (С, МОИИЕОйТ1НЕ) зев ар (С, ИОИИЕСАТ1ЧЕ, ' С ' ) (4 эах (ВО 41В Глава б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
