Рассмотрим задачу по симплекс-методу.
Это довольно простая задача с двумя переменными. Мы имеем целевую функцию (максимизируем) и три ограничения в виде линейных неравенств. Такие задачи довольно часто встречаются в МОРе (методы оптимальных решений). Решить её можно не только симплекс-методом, но и аналитически, и графически.
1. Графический способ.
Все четыре графика представляют собой области над или под прямыми. Каждую прямую можно построить по двум точкам (далее заменим для удобства x1 на x, а x2 на y). Например, по точкам пересечения с осями. В первых двух неравенствах это будет область под прямыми, а в третьем – над, так как там y>=. Нас интересует пересечение (система) трёх областей. Линия уровня целевой функции также прямая, градиент которой направлен вверх и влево (перпендикулярно линиям уровня). То есть более «восточным» линиям уровня соответствует бОльшее значение целевой функции (z).
Красная зона на рисунке – пересечение всех ограничений. На график также нанесены три линии уровня, они параллельны прямой из второго неравенства. Вектор u – градиент. Из рисунка понятно, что нам нужна самая правая линия уровня, проходящая через зону ограничения. Понятно, что это часть прямой из второго неравенства, ограниченная красной зоны. По сути это отрезок между двумя точками пересечений первых двух (6,5; 2,5) и последних двух неравенств (8;1). Сумма координат в обеих точках даёт девять, а целевая функция принимает значение 18. В любой точке отрезка решений сумма координат будет 9, а целевая функция будет равна 18. Таким образом, в задаче есть решения и их бесконечно много.
2. Аналитический способ.
До этого решения можно было бы легко дойти и аналитически. Видно, что целевая функция в два раза больше левой части второго неравенства, которое не больше 9. Давайте возьмём максимум (9). Тогда целевая функция будет равна 18. Больше она быть не может. Осталось доказать, что это решение допустимо.
Также выходим на отрезок прямой, ограниченный двумя нашими точками (6,5; 2,5) и (8;1).
3. Симплекс метод.
В симплекс методе нужно, чтобы целевая функция была на максимум, столбец свободных членов b был положителен, ограничения в виде равенств, а все переменные неотрицательны.
Поскольку у нас нет ни одного ограничения на неотрицательность переменных, а все три ограничения в виде неравенств, то нам придётся добавить 7 переменных (по две на каждую из исходных переменных и 3 на переход к равенствам). Третье неравенство нужно умножить на (-1), чтобы было положительное b.
Далее переходим к таблице симплекс-метода. Коэффициенты целевой функции c записываются со знаком минус. Остальные коэффициенты выписываются из системы ограничений выше.
Нам нужно, чтобы в последней строке не было отрицательных значений. По алгоритму нужно выбрать столбец с отрицательны с, максимальным по модулям. У нас значения для первого и третьего столбца совпадают. Начнём с первого. Выбираем в нём строку, с наименьшим отношением b к значению a. 14/1>9/1>4/1. То есть наименьшее отношение для третьей строки первого столбца. Этот элемент делаем единичным (в данном случае он и так единичный, поэтому третью строку не меняем, а в других строках делаем так, чтобы был нулевой первый столбец). Это стандартный механизм Гаусса. Из первой и второй строк вычитаем третью, а к 4-й строке добавляем удвоенную третью.
Итак, мы получили таблицу без отрицательных значений в последней строке. В ячейке со свободным членом мы видим наибольшее значений целевой функции – 18 (мы уже приходили к этому ответу). Нас интересуют первые 4 столбца. Из второй строки видно, что x2=x5-x6=1, а из третьей, что x1=x3-x4=8. Точку (8;1) мы уже тоже получали.
Поскольку у нас три строки, то нам нужно было получить единичную матрицу 3*3 (cтолбцы 1, 3, 5). Но у нас нули в последней строке стоят также у второго и четвёртого столбца, что наводит на мысль, что решение не единственное.
В 6-м столбце в последней строке стоит ноль, хотя столбец не единичный. Делаем его единичным. Для этого находим наименьшее отношение для положительных значений. 3/0,4 < 8/0,2, то есть единичным элементом делаем первый элемент в 6-м столбце. Далее весь столбец делаем единичным.
Последняя строка у нас не меняется, так как там стоял ноль. Из таблицы мы находим вторую точку: из второй строки x2=x5-x6=2,5, а из третьей x1=x3-x4=6,5. Точку (6,5;2,5) мы уже тоже получали. Общее решение – выпуклая линейная комбинация найденных двух точек (отрезок их соединяющий).
Файлы по этой задаче можно скачать в папке https://disk.yandex.ru/d/RD9KHIm3KO_49A
#педагогика #преподавание #егэ #экономика #математика #ib #alevel #научение #экономика #эконометрика #микроэкономика #макроэкономика #НамНужнаИнаяШкола #ЯндексПрактикум #ЗФТШ #МФТИ #Физтех #ДПО #ЦентральныйУниверситет #МОР #симплекс #ЛинейноеПрограммирование #МатематическийАнализ