В MATLAB для решения задач линейного программирования служит функция linprog. В простейшем случае у этой функции три входных параметра: linprog(f, A, b). В этом случае решается задача минимизации выражения f T x при условии A x <= 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] |