Численное решение в MATLAB





В MATLAB для решения задач линейного программирования служит функция linprog. В простейшем случае у этой функции три входных параметра: linprog(f, A, b). В этом случае решается задача минимизации выражения fTx при условии Ax<=b (сравнение производится по всем строкам), то есть задача представлена в форме (1).

 

>>x=linprog(-[8; 12],[2 4;0.5 0.25;2 2.5;],[440;65;320])

Optimization terminated successfully.

x= 60.0000

80.0000

 

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

У команды linprog есть несколько вариантов вызова, благодаря чему с её помощью можно решать задачи линейного программирвания, зданные в любой орме, в отм числе и в канонической (2). Информацию об этих способах вызова можно получить, выполнив команду help linprog.

Решение симплекс-методом

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

 

Составляем симплекс-таблицу:

    x1 x2 x3 x4 x5
базис Bi\Ci -8 -12
x3
x4 0.5 0.25
x5 2.5

 

Шаг 0: выбираем начальный допустимый базис и преобразуем симплекс-табилцу к диагональному виду относительно этого базиса. Если выбран базис (x3,x4,x5), то таблица уже приведена к диагональной форме.

Шаг 1: Проверяем, все ли С0,i>=0. Это не так.

Шаг 2: Выбираем ведущий столбец. Это столбец x2 (выделен жирным), так как ему соответствует наименьшее значение в верхней строке таблицы, -12.

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

Ведущая строка должна минимизировать Bi/Ai,x2. Выбрана строка x3, так как ей соответствует наименьшее значение, 440/4=110. (Удостоверьтесь, что для строк x4, x5 отношение больше). Следовательно, новый базис: (x2,x4,x5).

Шаг 4 Преобразование таблицы.

Для этого ведущую строку поделим на 4 (чтобы ведущий элемент стал равен 1), и прибавим её к другим строкам так, чтобы все элементы ведущего столбца стали равны 0.

 

Действие     x1 x2 x3 x4 x5
+12x3 базис Bi\Ci -8+6=-2 -12+12=0 0+3=3
/4 x3 0.5 0.25
-0.25*x3 x4 65-110*0.25=37.5 0.5-0.5*0.25=0.375 0.25-1*0.25=0 0-0.25*.25=-1/16 1-0=1 0-0=0
-2.5*x3 x5 320-2.5*110=45 2-2.5*0.5=3/4 2.5-2.5*1=0 0-0.25*2.5=-5/8

или, если не выписывать вычисления:

    x1 x2 x3 x4 x5
Базис Bi\Ci -2
x2 0.5 0.25
x4 37.5 3/8 -1/16
x5 ¾ -5/8

Симплекс-таблица, диагонализированная относительно нового базиса, получена. Повторяем итерацию с шага 1.

Шаг 1: Проверяем, все ли С0,i>=0. Это не так.

Шаг 2: Ведущий столбец x1, Cx1 = -2.

Шаг 3: Выбираем ведущую строку, x5, ей соответствует значение 45/(3/4)=60.

Следовательно, новый базис: (x1,x2,x4).

Шаг 4: Преобразование таблицы.

действие     x1 x2 x3 x4 x5
+2*x5 базис Bi\Ci 4/3 8/3
-0.5*x5 x2 2/3 -2/3
-3/8*x5 x4 1/4 -1/2
*4/3 x1 -5/6 4/3

 

Повторяем итерацию.

Шаг 1: Проверяем, все ли С0,i>=0. Это так. Следовательно, решение получено.

Оптимальным базисом является (x1,x2,x4), Оптимальное решение задачи в канонической форме: (x1,x2,x3,x4,x5)=(60, 80, 0, 15, 0).

Таким образом, решением исходной задачи является (x1,x2)=(60, 80).

 

 

ЗАДАНИЕ ПО РАБОТЕ И СОДЕРЖАНИЕ ОТЧЕТА

 

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

- переменные задачи.

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

- ограничения типа неравенство.

В работе необходимо

1) Привести задачу к канонической форме (2).

2) Построить графически область допустимых значений задачи.

3) Решить задачу средствами Maple и Matlab, выписать матричный вид условий.

4) Решить задачу симплекс-методом. Для решения симплекс-методом необходимо привести её к канонической форме, в качестве начальной точки (начального допустимого базиса) выбрать базис, составленный из искусственных переменных (по аналогии с решённым примером). Целочисленности решений не требуется.

Контрольные вопросы

1) Привести заданное условие типа неравенство с переменными неопределённого знака к равенству с положительными переменными.

2) Привести Заданное условие типа равенство к системе неравенств.

3) Сколько переменных (какую размерность) будет иметь задача после преобразования в каноническую форму, если ограничения заданы системой n неравенств, и все переменные имеют произвольный знак?

4) То же, что и в вопросе 3, но все переменные положительны?

5) Сколько вершин может иметь допустимое множество, если задача задана в канонической форме, и число переменных равно числу условий-равенств?

6) Сколько вершин может иметь допустимое множество, если задача задана в канонической форме, и условий-равенств на одно меньше числа переменных?

7) Решить графически задачу линейного программирования:
.

8) Решить графически задачу линейного программирования:
.

9) Приведите пример задачи линейного программирования, не имеющей конечного решения.


Варианты заданий

Матрицы заданы в форме, принятой в Matlab, элементы разделяются пробелами или запятыми, строки – точкой с запятой.

№ варианта A B C
[2, 4; 0.5, 0.25; 2, 2.5] [440;65;160] [8 12]
[2, 4; 0.5, 0.25; 2, 2.5] [220;65;320] [8 12]
[2, 4; 0.5, 0.25; 2, 2.5] [440;130;320] [8 12]
[2, 4; 0.5, 0.25; 2, 2.5] [880;65;320] [8 12]
[8, 4; 0.5, 0.25; 2, 2.5] [440;65;320] [8 12]
[2, 4; 1, 0.25; 2, 2.5] [440;65;320] [8 12]
[2, 4; 0.5, 2; 2, 2.5] [440;65;320] [8 12]
[2, 4; 0.5, 0.25; 2, 10] [440;65;320] [8 12]
[2, 4; 0.5, 0.25; 2, 2.5] [440;65;320] [8 24]
[2, 4; 0.5, 0.25; 2, 2.5] [440;65;320] [8 6]
[2, 4; 0.5, 0.25; 2, 2.5] [440;65;320] [4 12]
[2, 4; 0.5, 0.25; 2, 2.5] [440;65;320] [4 6]
[2, 4; 0.5, 0.25; 2, 2.5] [200;35;120] [4 24]
[2, 4; 0.5, 0.25; 2, 2.5] [440;65;120] [4 24]
[2, 4; 0.5, 0.25; 2, 2.5] [440;65;120] [4 24]
[2, 4; 0.5, 0.25; 2, 2.5] [440;65;220] [4 24]
[2, 4; 0.5, 0.25; 2, 2.5] [440;65;220] [4 24]
[2, 4; 0.5, 0.25; 2, 2.5] [440;65;220] [4 24]
[2, 4; 0.5, 0.25] [440;65] [4 24]
[2, 4; 0.5, 0.25] [440;65] [4 24]

 





Читайте также:
Роль языка в формировании личности: Это происходит потому, что любой современный язык – это сложное ...
Ограждение места работ сигналами на перегонах и станциях: Приступать к работам разрешается только после того, когда...
Конфликтные ситуации в медицинской практике: Наиболее ярким примером конфликта врача и пациента является...
Основные научные достижения Средневековья: Ситуация в средневековой науке стала меняться к лучшему с...

Рекомендуемые страницы:



Вам нужно быстро и легко написать вашу работу? Тогда вам сюда...

Поиск по сайту

©2015-2021 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-02-16 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту:

Мы поможем в написании ваших работ! Мы поможем в написании ваших работ! Мы поможем в написании ваших работ!
Обратная связь
0.017 с.