Реферат: Использование среды MatLAB для решения линейной программы

/>СОДЕРЖАНИЕ

Введение

1. Постановка задачи линейногопрограммирования

1.1 Формы задачи линейного программирования

1.2 Переходк канонической форме

2. Симплекс-метод

2.1 Теоретические основы симплекс-метода

2.2 Прямой алгоритм симплексного метода

3. Метод Гомори

4. Математическая и техническаяпостановка задачи. Программная реализация.Описаниепроекта

4.1 Запуск

4.2 Описание графического интерфейса

4.3 Описание созданных функций

Заключение

Список литературы

/>ВВЕДЕНИЕ

Колоссальные темпытехнического прогресса породили проблему создания систем управления сложнымисистемами. Эта проблема приводит к необходимости построения математическихмоделей принятия оптимальных решений.

Совокупностьматематических методов, занимающихся вопросами выбора на заданном множестведопустимых решений того решения, которое по установленным критериям являетсяоптимальным, составляет математическую дисциплину «исследование операций».

В свою очередь,исследование операций разделяется на ряд самостоятельных дисциплин, а в даннойработе мы столкнемся с задачей решения линейной программы симплексным методом вобычном, целочисленном и частично целочисленном вариантах.

/> 

1. ПОСТАНОВКА ЗАДАЧИЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ [2] 1.1 Формы задачи линейного программирования

В общем виде задача линейного программирования (в дальнейшемЗЛП) может быть сформулирована как задача нахождения наибольшего значениялинейной функции

/> (1.1)

на некотором множестве D Ì Rn, где x Î D удовлетворяют системе ограничений

/>

/>

/>

/>

/> (1.2)

и, возможно, ограничениям

/> (1.3)

He умаляя общности, можно считать, что в системе (1.2) первые т ограниченийявляются неравенствами, а последующие — l-уравнениями. Очевидно, этого всегда можно добиться за счетпростого переупорядочения ограничений. Относительно направления знаканеравенства будем предполагать, что левая часть меньше или равна правой.Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеютпротивоположный знак. Ограничения (1.3), вообще говоря, могут быть рассмотреныкак частный случай ограничений в форме неравенств, но в силу особой структурыих обычно выделяют отдельно и называют условиями неотрицательности (или тривиальнымиограничениями).

Дополнительно следует заметить, что выбор типа искомогоэкстремума (максимума или минимума) также носит относительный характер. Так,задача поиска максимума функции

/> (1.4)

эквивалентна задаче поиска минимума функции

/> (1.5)

Часто условия задачи (1.1) — (1.3), содержащей ограничениятолько типа неравенств, бывает удобно записывать в сокращенной матричной форме

/> (1.6)

где с и x — векторы из пространства Rn, b — векториз пространства Rm, a А — матрица размерности m ´ п.

Задачу линейного программирования, записанную в форме (1.1) — (1.3), называют общей задачей линейного программирования (ОЗЛП).

Если все ограничения в задаче линейного программированияявляются уравнениями и на все переменные xj наложены условия неотрицательности, то она называется задачейлинейного программирования в канонической форме, или канонической задачейлинейного программирования (КЗЛП). В матричной форме КЗЛП можно записать вследующем виде:

/> (1.7)

Поскольку любая оптимизационная задача однозначноопределяется целевой функцией f иобластью D, на которой отыскивается оптимум (максимум), будем обозначатьэту задачу парой (D, f).

Условимся относительно терминологии, которая используется вдальнейшем и является общепринятой в теории линейного программирования.

Планом ЗЛП называется всякий вектор х из пространства Rn.

Допустимым планом называется такой план ЗЛП, который удовлетворяетограничениям (1.2)-(1.3), т. е. содержится в области D. Самаобласть D называется при этом областьюдопустимых планов. Оптимальным планом х* называется такойдопустимый план, при котором целевая функция достигает оптимального (в нашемслучае — максимального) значения, т. е. план, удовлетворяющий условию

max f(x) = f(x*).

Величина f* = f(x*) называется оптимальным значением целевой функции.

Решением задачи называется пара (х*, f*), состоящая из оптимального плана и оптимального значения целевойфункции, а процесс решения заключается в отыскании множества всех решений ЗЛП.

 
1.2 Переход к каноническойформе

Подавляющее большинство известных методов решения задачлинейного программирования предназначены для канонических задач. Поэтомуначальный этап решения всякой общей задачи линейного программирования обычносвязан с приведением ее к некоторой эквивалентной канонической задаче.

Общая идея перехода отОЗЛП к КЗЛП достаточно проста:

Øограниченияв виде неравенств преобразуются в уравнения за счет добавления фиктивных неотрицательныхпеременных />,которые одновременно входят в целевую функцию с коэффициентом 0, т. е. не оказывают влияния на еезначение;

Øпеременные, на которые не наложеноусловие неотрицательности, представляются в виде разности двух новыхнеотрицательных переменных:

/>

Øпеременные, на которые наложеноусловие неположительности, представляются в виде новой неотрицательнойпеременной помноженной на -1:

/>

Нетрудно заметить, что «платой» за переход от общей формызадачи линейного программирования к канонической является рост ее размерности,что, при прочих равных условиях, является фактором, усложняющим процессрешения.

2.СИМПЛЕКС-МЕТОД 2.1 Теоретические основы симплекс-метода

Исходя из свойств линейных экстремальных задач, можнозаключить, что на принципиальном уровне поиск их решений сводится к последовательномуперебору угловых точек множества допустимых планов или, что то же самое,перебору соответствующих допустимых базисных планов. Средством решения даннойпроблемы явились прикладные оптимизационные методы, основанные напоследовательном, целенаправленном переборе базисных планов ЗЛП.

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

Пусть стоит задачамаксимизации

/> (2.1)

при условиях

/>, (2.2)

Xj³ 0, j=1,…,n (2.3)

Предположим, что намудалось найти опорный план X0, в котором, например, первые mкомпонент отличны от нуля:

X0=(X10,X20,…,Xm0,0, …, 0), (2.4)

и соответствующий базис Б=(A1,A2,…,Am).

Попытаемся выбрать другуюсистему базисных векторов с целью построения нового опорного плана, в которомk-я переменная (k>m) принимает значениеQ >0:

X(Q) = (X1(Q), X2(Q),…,Xm(Q), 0, …,Q, … 0) (2.5)

Подставляя (2.4) в (2.2),имеем

/>(2.6)

Подставив (2.5) в (2.2), получаем

/> (2.7)

Разложим вектор Ak повекторам исходного базиса

/> (8)

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

Подставляя (2.6) и (2.8)в (2.7), получаем

/>, (2.9)

откуда имеем

/> (2.10)

Так как система уравнений(2.10) имеет единственное решение, то получаем представление первых mкомпонентнового плана

/> (2.11)

Естественно потребоватьнеотрицательность компонент нового плана. Так как нарушение неотрицательности в(2.11) может возникнуть лишь при Zjk>0, то значение Q нужно взять не превышающимнаименьшего из отношений /> к положительным Zjk.

Если к тому же учесть,что число положительных (базисных) компонент опорного плана должно оставаться равнымm, то одну из первых m (ненулевых) компонент исходного плана обращаем в нульвыбором

/> (2.12)

Подставляя (2.11) в(2.1), имеем

/> (2.13)

Если обозначить

/>, (2.14)

/>, (2.15)

то (2.13) примет вид

/> (16)

Из полученных соотношенийнапрашиваются следующие выводы.

Критерий 1 (критерийоптимальности).Если все Dk ³ 0, то выбранный план для задачи максимизации является оптимальным.

Критерий 2. Еслиобнаруживается некоторое Dk < 0 ихотя бы одно из значений Zjk >0, то переход к новому плануувеличит значение целевой функции.

Этот вывод с очевидностьюследует из (2.16); в такой ситуации согласно (2.12) полагаем k-ю переменнуюравной Q и преобразуем значения остальных(базисных) переменных в соответствии с (2.11).

Критерий 3. Еслиобнаруживается некоторое Dk < 0, новсе Zjk£0, то линейная форма задачи не ограничена по максимуму.

Этот вывод следует изтого, что согласно (2.11) компоненты нового плана сохраняют неотрицательностьпри любом Q>0 (в томчисле и при сколь угодно большом) и согласно (2.16) появляется возможностьнеограниченного изменения значения целевой функции.

Предположение о том, чтобазисными являются первые mкомпонент плана, не является принципиальным,и указание диапазона поj от 1 до m в (2.11)-(2.15) можно заменить науказание о принадлежности к базису “jÎБ“.

Если все опорные планы задачиявляются невырожденными (число положительных компонент равно m), то Q отлично от нуля и переход к новомуплану согласно (2.16) изменяет значение целевой функции, что гарантируетдостижение экстремума за конечное число шагов. При наличии вырожденных плановвозможно т. н. зацикливание (возврат к ранее рассмотренным планам), но напрактике зацикливание никогда не возникало.

2.2 Прямой алгоритмсимплексного метода[1]

Пусть исходная задачаприведена к канонической форме и начальный базис образует единичную матрицу.Тогда базисные компоненты опорного плана совпадают с правыми частямиограничений и коэффициенты Zjk разложения вектора Xk по такому базису совпадают скомпонентами этого вектора.

Для единообразия описаниявычислительной процедуры в дальнейшем будем пользоваться т.н. симплекснойтаблицей вида:

C

Базис

План

C1

C2

Cm

Cm+1

Ck

Cn

баз

плана

X

X1

X2

Xm

Xm+1

Xk

Xn

С1

X1

B1

1

Z1m+1

Z1k

Z1n

С2

X2

B2

1

Z2m+1

Z2k

Z2n

Cm

Xm

Bm

1

Zmm+1

Zmk

Zmn

Zk

L(X)

Z1

Z2

Zm

Zm+1

Zk

Zn

Dk

D1

D2

Dm

Dm+1

Dk

Dn

В центральной частитаблицы записываются коэффициенты при неизвестных в ограничениях, в столбцеX- правая часть ограничений (базисные компоненты плана), в первой строке — коэффициенты линейной формы, во второй строке – переменные, входящие в целевуюфункцию и систему ограничений. Основное поле симплекс таблицы — коэффициентыпри неизвестных в ограничениях. В первом столбце для удобства вычислений будемзаносить коэффициенты линейной формы при базисных переменных, указанных вовтором столбце (умножение его на столбец X (свободные члены Bi≥0) с суммированием даетзначение L(X); аналогичное умножение его на столбец Xk даст Zk). Последняя строка получается вычитаниемиз предыдущей строки элементов первой строки таблицы и позволяет судить обоптимальности плана.

Т.к. выбор типа искомогоэкстремума (максимума или минимума) носит относительный характер, то прирешении задач максимизации/минимизации в последней строке должны быть тольконеотрицательные элементы.

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

Если такой единичнойподматрицы не обнаруживается, то либо придется перебирать все подсистемы mуравнений с m неизвестными в надежде обнаружить неотрицательные решения, либоприбегнуть к методу искусственного базиса.

В последнем случае вограничения добавляют неотрицательные, т.н. искусственные переменные так, чтобывозникла единичная подматрица коэффициентов, и эти переменные включают влинейную форму с коэффициентом — М для задачи максимизации, где М>0 — сколь угодно большое число.

Полученная М-задачарешается до получения оптимального плана.

Если в оптимальном планеМ-задачи значения искусственных переменных равны нулю, то значения остальныхкомпонент образуют оптимальный план исходной задачи.

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

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

 

3. МЕТОД ГОМОРИ [1]

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

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

B общем случаевыдвигается идея последовательного отсечения нецелочисленных оптимальных планов:обычным симплексным методом отыскивается оптимальный план и, если оннецелочисленный, строится дополнительное ограничение, отсекающее найденныйоптимальный план, но не отсекающее ни одного целочисленного плана.

Эта идея, принадлежащаяД. Данцигу и Р. Гомори, впервые была представлена в форме дополнительного ограничения:

/> (3.1)

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

К сожалению, дляабсолютного большинства задач скорость сходимости процесса таких отсечениймала. Потому Р. Гомори предложена другая форма дополнительного ограничения.Так, если компонента плана, определяемая k-м уравнением системы ограничений,нецелочисленна, то добавляется ограничение

/>, (3.2)

где fk — дробная часть компоненты плана (правой части ограничения) и fkj — дробная часть коэффициента при Xj (целая часть числа – наибольшее целое,не превышающее это число; дробная часть числа равна разности между числом и егоцелой частью), S* — новая дополнительная переменная.

Можно уменьшить объемпреобразований, если руководствоваться следующими правилами:

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

2) для ввода в базисопорного плана расширенной задачи выбирать переменную, для которой достигаетсяминимум из отношений абсолютных значений Dj к значениям fk j ;

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

Появление дополнительногоограничения и дополнительной переменной вновь приводит к проблеме выбораначального опорного плана расширенной задачи и к использованию с этой цельюискусственной переменной. Следует заметить, что если при поиске переменной,исключаемой из базиса, значение Q (определяемое с учетом дополнительного ограничения)соответствует этому ограничению, то можно отказаться от использования искусственнойпеременной (она все равно выведется из базиса на этом же шаге решения).

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

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

 

 

4. МАТЕМАТИЧЕСКАЯ ИТЕХНИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

Математическую итехническую постановку задачи можно сформулировать следующим образом.Разработать программное обеспечение на встроенном языке среды MatLAB, позволяющее решать линейныепрограммы симплексным методом с учетом приведенного выше теоретическогоматериала.

Несмотря на то, что впоставляемом вместе с MatLABпакете программ Optimization Toolbox имелась функция linprog реализующая решение линейных задач,было принято решение реализовывать симплекс-метод и метод Гомори не используяуже готовые решения, но максимально задействуя встроенные функции средыразработки.

В ходе разработкинаибольшее внимание уделялось удобству работы с программой и качествуреализации методов.

В плане ограниченийнакладываемых на пользователя можно отметить лиши разумность вводимых данных.

Программнаяреализация

Программа написана навстроенном в MatLAB языке программирования. Не смотря навсю простоту языка программирования MatLAB’а стоит отметить его большую функциональность обеспечиваемую встроеннымифункциями и пакетами расширений Toolbox.

Отличительнойособенностью разработанной программы является ее графический интерфейс (Рисунок1), обеспечивающий максимально удобную работы и позволяющий работать спрограммой даже не посвященным в программирование, математику и экономикулюдям.

Основная частьпрограммного кода в соответствии со своим назначением разделена на функции,которые хранятся отдельно от интерфейса и могут быть использованы пользователемпо своему усмотрению, в том числе в других приложениях/программах или же могутбыть вызваны через консоль MatLAB.

/>

Рисунок1. Графический интерфейс программы

Описаниепроекта 4.1 Запуск

Для запуска проектанеобходимо запустить среду MatLABи указать путь к каталогу с программой. Затем необходимо запустить графическийинтерфейс (Рисунок 1) для чего в консоли MatLAB’а требуется ввести guide и в открывшемся окошке(Рисунок 2) выбрать вкладку «Открыть существующий GUI» и указав путь к GUI-интерфейсу «MainSimplexForm.fig» нажать кнопку «ОК».

/>

Рисунок2. GUIDE — среда разработки и работы с GUI-интерфейсами MatLAB

В итоге появится макетинтерфейса (Рисунок 3) для запуска которого достаточно нажать комбинацию клавиш«Ctrl+T» или зеленую стрелочку на панели под главным меню. Послезапуска перед вами появится полноценный графический интерфейс (Рисунок 1).

/>

Рисунок3. Макет GUI-интерфейса

 

 

4.2 Описание графического интерфейса

Вверху формы расположеноглавное меню (Рисунок 4), состоящее из пунктов «Примеры», «Дополнительно» и«Выход».

/>

Рисунок4. Главное меню

Пункт «Примеры» позволяетзагрузить или создать пример работы с программой. Примеры хранятся в текстовыхфайлах с расширением «matex»содержащих целевую функцию, ограничения и условия неотрицательности.

Пункт «Дополнительно»позволяет пользователям операционной системы Windows получить доступ к Калькулятору, Блокноту и некоторымдругим приложениям.

Пункт «Выход» закрываетсреду MatLAB.

Для ввода функции,ограничений, условий неотрицательности и выбора метода используется центральнаячасть формы (Рисунок 5).

/>

Рисунок5. Здесь можно ввести исходные данные и выбрать метод решения

Для запуска метода ипросмотра результатов его работы служит нижняя часть формы (Рисунок 6).

/>

Рисунок6. Здесь можно запустить метод и просмотреть результат его работы

Особое внимание надообратить на статусное сообщение. Поля «Оптимальный план» и «Экстремум функции»будут заполнены последними значениями, но судить об их верности можно толькопрочитав статусное сообщение! Решение двойственной задачи отображается толькодля обычного варианта симплексного метода.

В случае если вы хотитевоспользоваться частично целочисленным методом стоит обратить внимание на вводтребуемых иксов (Рисунок 7).

/>

Рисунок7. Ввод номеров требуемых целых иксов

Необходимо через пробелвводить номера иксов, которые вы хотите видеть целыми.

 

4.3 Описание созданных функций

В ходе разработки проектабыли написаны следующие функции:

1.  parser_input – функция разделениястроки типа “2x1+5x2-7x3” намассив номеров иксов и массив коэффициентов при этих иксах;

2.  parser_allogr – функция канонизации,формирующая составляющие симплексной таблицы из введенных функции, ограничений,условий неотрицательности;

3.  load_example – функция чтения файла спримером;

4.  save_example – функция записи файла с примером;

5.  simple_simplex – функция, реализующаяпростой симплекс-метод;

6.  gomory_simplex – функция, реализующая метод Гомори;

7.  MainSimplexForm – функция, связаннаяс графическим интерфейсом и содержащая основные вызовы остальных функций.

Все перечисленные вышефункции снабжены подробной справкой и для более подробного ознакомления с нимидостаточно в консоли MatLABввести: help имя_функции

Данные функции можноиспользовать в других программах написанных для MatLAB, т.к. они работают в проекте как «автономные модули».

/> 

 

Заключение

Итогом написания даннойкурсовой работы является компьютерная реализация решения линейных программсимплексным методом в обычном, целочисленном и частично целочисленномвариантах.

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

Следует отметить, чтосимплексный метод в различных вариациях фигурирует во многих задачах дисциплины«исследование операций», например, при рассмотрении двойственности в линейномпрограммировании, целочисленном линейном программировании, матричных играх ит.д. Соответственно созданная программа позволит упростить решение упомянутыхвыше задач.

/>Список литературы

1.  Тынкевич М.А.«Экономико-математические методы (исследование операций)», издание 2-е,исправленное и дополненное, Кемерово, 2007г.

2.  Конюховский П.В. «Математическиеметоды исследования операций в экономике», СПб.: Питер, 2008г.

3.  Дегтярев Ю.И. «Исследованиеопераций», М.: Высшая школа, 2009 г.

4.  Ануфриев И.Е., Смирнов А.Б., СмирноваЕ.Н. «MATLAB 7», СПб.: БХВ-Петерберг, 2005г.

5.  Дъяконов В. «MATLAB 6: Учебный курс», СПб.: Питер, 2010г.