Задача по "Линейному программированию"
Автор: K_1arina • Январь 6, 2023 • Задача • 451 Слов (2 Страниц) • 125 Просмотры
Задание.
Для варианта матриц , решить задачу линейного программирования вручную (графически и при помощи симплекс-метода), а также при помощи пакета MATLAB.
В пояснительной записке необходимо:
1) привести построенную графически область допустимых значений задачи и найти ее решение;
2) привести задачу к канонической форме ;
3) решить задачу симплекс-методом, выбрав начальный базис из искусственных переменных (по аналогии с решенным примером);
4) решить задачу средствами MATLAB.
Дано:
[pic 1]; [pic 2]; [pic 3]
Графический метод решения задачи
Математическая формулировка задачи:
[pic 4]
Для графического решения построим на плоскости три прямые, соответствующие ограничениям
[pic 5][pic 6][pic 7][pic 8]
Полученные прямые показаны на рис. 1.
Границы области допустимых решений. Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи. Обозначим границы области многоугольника решений – это треугольник с точками АВС.
На этом же рисунке показано семейство прямая F(x) =[pic 9].
Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых 2x1+2.5x2=220 и x1=0.
Решив систему уравнений, получим: x1 = 0, x2 = 88
Откуда найдем максимальное значение целевой функции:
F(X) = 4*0 + 24*88 = 2112
2. Переход к канонической форме.
Чтобы перейти к канонической форме, необходимо условия типа неравенство заменить на равенства и перейти к положительным переменным. Это делается путем введения дополнительных переменных. Получим:
[pic 10]
Поскольку в канонической форме ищется минимум, знак целевой функции изменяем на противоположный.
[pic 11]
3. Решение задачи симплекс – методом
Составляем симплекс-таблицу1.
Таблица 1.
x1 | x2 | x3 | x4 | x5 | ||
базис | bi/ci | -4 | -24 | |||
x3 | 440 | 2 | 4 | 1 | 0 | 0 |
x4 | 65 | 0.5 | 0.25 | 0 | 1 | 0 |
x5 | 22 | 2 | 2.5 | 0 | 0 | 1 |
Шаг 0: выбираем начальный допустимый базис (х3,х4,х5), поскольку относительно него таблица уже приведена к диагональной форме.
Шаг 1: проверяем, все ли с0,i>=0. Нет.
Шаг 2: выбираем ведущий столбец. Это столбец х2, т.к. ему соответствует наименьшее значение в верхней строке таблицы – 24.
Шаг 3: В данном столбце все положительные элементы. Выбираем ведущую строку с минимальным значением bi/ai,x2. Выбрана строка х5, так как 220/2,5=88 (минимальное).
...