Графическое решение в MATLAB

Графическое решение в MATLAB

Решение задач линейного программирования

Цельработы: ознакомиться с решением задач линейного программирования в пакетах MATLAB и Maple.

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

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

Эти условия можно записать в матричной Графическое решение в MATLAB форме

(1)

Тут b и c – векторы-столбцы, А – матрица размера m´n.

Существует другая форма записи, именуемая канонической, когда ограничения имеют вид равенств, а на переменные накладывается требование положительности:

(2)

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

Чтоб Графическое решение в MATLAB перейти к канонической форме (2), нужно условия типа неравенство поменять на равенства и перейти к положительным переменным. 1-ое делается методом введения дополнительных переменных, к примеру, заместо неравенства можно записать равенство

где – новенькая переменная.

Всякую переменную неопределённого знака можно поменять разностью 2-ух положительных переменных:

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

.

К примеру, заместо можно записать пару неравенств

Существует много способов решения задач линейного программирования. одним из более приятных является графический способ, а посреди численных более известен симплекс-метод. Остановимся на их подробнее.

Графический способ

Применяется, когда число переменных невелико (обычно две Графическое решение в MATLAB), число ограничений может быть хоть каким. На плоскости х,у отрисовывают прямые, надлежащие ограничениям и рассматривают образованный ими многоугольник. Решение достигается в одной из его вершин. Чтоб отыскать ее, берут прямую (где – мотивированная функция), и перемещают ее параллельно на право либо на лево до того времени, пока многоугольник ограничений Графическое решение в MATLAB не окажется по одну сторону от нее.

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

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

Мысль симплекс-метода состоит в последующем. На исходном шаге отыскивается неважно какая исходная верхушка G и определяются все выходящие из неё ребра. Дальше передвигаются повдоль того из ребер, по которому функция убывает (при поиске минимума), и попадают в последующую верхушку. Находят выходящие из нее ребра и повторяют процесс Графическое решение в MATLAB. Когда приходят в такую верхушку, в какой повдоль всех выходящих из нее ребер функция растет, то минимум найден.

Применение симплекс-метода для задачки линейного программирования подразумевает предварительное приведение ее к канонической форме (2) с n положительными переменными и m критериями типа равенство.

При всем этом требование положительности переменных значит Графическое решение в MATLAB, что точки принадлежат области n-мерного места, где все координаты положительны (положительный ортант). Равенства определяют n-m мерную гиперплоскость, скрещение которой с положительным ортантом и даёт полиэдр допустимых решений.

Рис. 1. Вид допустимого огромного количества для n=2, m=1.

На рис.1 это проиллюстрировано для варианта n=3, m=1. При всем этом условие положительности Графическое решение в MATLAB задаёт положительный октант трёхмерного места, а одно (m=1) условие-равенство задаёт двухмерную (n-m=2) плоскость. В итоге, допустимое огромное количество, в каком производятся все условия, становится сечение октанта плоскостью (заштрихованный треугольник). Экстремум линейной мотивированной функции может наблюдаться исключительно в верхушках этого уймищи, другими словами в одной из трёх Графическое решение в MATLAB вершин треугольника.

Чтоб отыскать верхушки полиэдра, заметим, что на границе ортанта одна либо более переменных равны нулю (на рис.1 на грани (x1,x2) переменная x3=0). Тогда, чтоб отыскать верхушку, необходимо максимально большее число переменных приравнять нулю, а другие отыскать из условий-равенств. Потому что при всем этом Графическое решение в MATLAB должна появляться система линейных уравнений с n неведомыми, для её конкретного решения нужно n уравнений, другими словами имеющиеся m критерий нужно дополнить n-m равенствами вида xi=0.

Тогда в каждой верхушке полиэдра будет m ненулевых координат, которые образуют базис. Другие n-m координат входят в небазисный набор. Направьте внимание, что базис совершенно Графическое решение в MATLAB точно определяет координаты верхушки. Как следует, задачку можно было бы решить оковём полного перебора всех базисов, но их число может быть очень велико (число выборок по m частей из n).

Метод симплекс-метода состоит из последующих 5 шагов.

На шаге 0 выбирается исходный базовый набор.

Мотивированная функция и ограничения-равенства Графическое решение в MATLAB преобразуются к диагональной форме относительно базовых переменных, так, чтоб любая базовая переменная заходила исключительно в одно уравнение и не заходила в мотивированную функцию. Это комфортно записать в форме так именуемой симплекс-таблицы. А именно, последующая таблица диагонализирована относительно базиса (x1, x2, …, xm):

x1 x2 ... xm xm+1 ... xn
Базис Графическое решение в MATLAB Bi\Ci ... Cm+1 ... Cn
x1 B1 ... A1,m+1 ... A1,n
x2 B2 ... A2,m+1 ... A2,n
... ... ... ... ... ... ... ... ...
xm Bm ... Am,m+1 ... Am,n

Верхняя строчка симплекс-таблицы обрисовывает мотивированную функцию задачки. Другие строчки соответствует ограничениям задачки. Cвободные члены ограничений составляют последний левый столбец таблицы. Слева от таблицы записаны текущие базовые переменные (x1, ..., xm Графическое решение в MATLAB), которые входят в уравнение, задаваемое данной строчкой. Над таблицей приведен набор всех переменных задачки, где xm+1, ..., xn - cвободные переменные задачки.

На шаге 1 проверяется, все ли Ci>=0. Если это так, то такая таблица именуется двойственно-допустимой, и соответствует хорошему решению. Значения базовых переменных в данном случае находятся в столбце B Графическое решение в MATLAB.

Если не все Ci>=0, то на шаге 2 выбирается ведущий столбец (т.е. ведущая переменная), для которого Свед мало. При увеличении этой переменной аспект миниатюризируется более стремительно.

Наращивать небазисную переменную можно за счёт базовых, потому на шаге 3 выбирается ведущая строчка, соответственная той из базовых переменных, которая будет убывать меньше других Графическое решение в MATLAB. Это та переменная, для которой Ai,вед>0 и отношение Bi/Ai,вед мало. Если таких переменных нет (все Ai,вед<=0), то задачка неразрешима.

После того, как выбраны ведущая строчка и столбец, происходит смена базиса, при всем этом переменная ведущей строчки исключается из него (миниатюризируется до 0), а переменная ведущего Графическое решение в MATLAB столбца, напротив, вносится (воспринимает ненулевое значение).

На шаге 4 таблица приводится к диагональному виду уже относительно нового базиса. Для этого линейно комбинируются её строчки. А именно, проще всего поделить ведомую строчку на значение ведущего элемента (чтоб этот элемент стал равен 1), а потом добавлять эту строчку к другим с таким коэффициентом, чтоб обнулить Графическое решение в MATLAB все другие элементы ведущего столбца.

Потом осуществляется возврат к шагу 1.

Примеры

Пример 1

Отыскать максимум и минимум функции 2x+yпри ограничениях 0£x£1, 0£y£1.

Геометрическое решение.

Рисуем единичный квадрат и сечем его семейством прямых 2x+y=с

Ясно, что максимум достигается в верхнем правом углу квадрата (точка x=1, y=1) и равен 3, а Графическое решение в MATLAB минимум – в обратном углу (точка x=0, y=0) и равен нулю.

Решение в MAPLE

В пакете MAPLE для задач линейного программирования необходимо загрузить библиотекуsimplex. Для загрузки библиотек служит команда with(). Команды Maple нужно завершать или ";", или, чтоб подавить вывод результата, ":".

Ограничения вводятся в виде перечня линейных неравенств. Матричную запись введённой Графическое решение в MATLAB ситемы можно получить с помощью команды display из такого же пакета.

После того, как ограничения введены, применяется командаminimize(f, C), если необходимо отыскать минимум мотивированной функции, или командаmaximize(f, C), если необходимо отыскать ее максимум, где f – мотивированная функция, а C – перечень критерий.

> with(simplex):

> e:={x>=0,x=0,y<=1};

> display(e Графическое решение в MATLAB);

> minimize(2*x+y,e);

> maximize(2*x+y,e);

Пример 2

Задачка о производстве стульев. Мебельная фабрика может выпускать стулья 2-ух типов, ценой 6000 и 12000 рублей. Имеются последующие ресурсы: 440 метров досок, 65 кв.м. обивочной ткани и 320 человеко-часов трудовых ресурсов. На изготовка 1-го стула требуются последующее количество ресурсов:

Стул Расход досок Расход ткани Графическое решение в MATLAB Расход времени
1-ый 0.5
2-ой 0.25 2.5
Ресурс

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

Математическая модель

Обозначим х – количество стульев первого типа, у – количество стульев второго типа.

Тогда:

- оптимизируемый аспект.

- ограничение по расходу досок

- ограничение по расходу ткани

- ограничение по расходу времени.

Матричная форма записи:

Графическое решение в MATLAB

Для Графическое решение в MATLAB графического решения данной задачки построим на плоскости (x,y) три прямые, надлежащие ограничениям по трем ресурсам. По оси x будем откладывать количество стульев второго вида, по оси y количество стульев первого вида. Приобретенные графики показаны на рис.2 красноватым цветом. Они, вкупе с осями координат, задают область допустимых решений.

Черным Графическое решение в MATLAB цветом показано семейство прямых . Решение задачки дает последняя правая ровная этого семейства, касающаяся многоугольника допустимых решений в точке с координатами (80, 60).

Графики построены в МАТLAB при помощи последующей программки:

x=0:0.2:300; y1=-2*x+220; y2=(-1/2)*x+130; y3=(-5/4)*x+160;

plot(x,y1,x,y2,x,y3); grid; hold on

for c=0:60:1460

y=-3/2*x+c/8;

plot Графическое решение в MATLAB(x,y,'black');grid on;

end

Рис. 2. Графическое решение.


graficheskie-modeli-i-modeliruyushaya-deyatelnost-v-processe-oznakomleniya-detej-s-prirodoj.html
graficheskie-redaktori-na-primere-adobe-imagestyler-referat.html
graficheskie-uprazhneniya-shtrihovka.html