Ознакомительная часть с решением задач по предмету: “Математические методы анализа экономики”. Вариант из методического пособия №2.
Дорогие студенты и гости нашего сайта, обращаем Ваше внимание! В случае, если условия данных задач Вам не подходят, напишите нам. Мы поможем Вам с решением задач любой сложности, а также с написанием курсовых работ по любым предметам.
Решение задания №1. Основная идея симплекс-метода. Пространство решений задачи ЛП.
Для решения задач линейного программирования предложено немало различных алгоритмов. Наиболее эффективным среди них является алгоритм, известный под названием симплексный метод, или метод последовательного улучшения плана.
Симплексный метод – это итерационный процесс, который начинается с одного решения и в поисках лучшего варианта движется по угловым точкам области возможных решений до тех пор, пока не достигнет оптимального значения, и в частности по угловым точкам многоугольника решений, полученного геометрическим методом.
Т.о., основная идея симплекс-метода состоит в последовательном приближении к оптимальному решению. При этом значение целевой функции изменяется. Рассмотрим алгоритм симплекс-метода.
1. Выбирается начальное базисное решение. Система ограничений задачи, решаемой симплекс-методом, задана в виде системы неравенств. Перейдем от системы неравенств к системе уравнений путем введения дополнительных переменных. Эти переменные будут базисными на первом этапе.
2. Проверка решения (опорного плана) на оптимальность. Если все коэффициенты индексной строки (строки целевой функции) при решении задачи на максимум неотрицательны (>0), то план является оптимальным. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный и его можно улучшить. В этом случае переходим к следующему этапу алгоритма.
Решение задания №2. Решить задачу графическим методом.
Строим область допустимых значений (четырехугольник АВСD). На графике он заштрихован. Затем строим линию целевой функции. Z – линия целевой функции Z=6×1+2×2. На графике она показана пунктиром.
Координаты точек: А(0;0); В(0;2); С(1,2;2,3); D(3:0).
Решение задания №3. Решить задачу методом больших штрафов.
Введем искусственные переменные r1,r2 с коэффициентами равными единице.
5×1+x2+х3+S1+r1=15
2×1+2×2+х3-S2+r2=10
Строим первую симплекс-таблицу. Т.к. решается задача минимизации и не все коэффициенты в z-строке неположительны, то начальное решение не оптимально.
В качестве вводимой в базис переменной выберем ту, у которой в z-строке коэффициент наибольший. В данном случае это переменная x2. Тогда исключаемой из базиса переменной будетr1, т.к. она дает наименьшее среди отношений правых частей ограничений к строго положительным коэффициентам при новой базисной переменной x2.
Решение задания №4. Решить транспортную задачу.
Решим транспортную задачу методом потенциалов. Найдем начальное решение. Воспользуемся методом наименьшей стоимости. В результате получен первый опорный план, который является допустимым.
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m+n-1=5+3–1=7. Следовательно, опорный план является вырожденным. Введем 0 в летку с наименьшим тарифом, например, в клетку A4B2.
Определим значение целевой функции первого опорного плана: Z=6*2+10*0+12*3+14*0+10*1+0*1+3*2=64. Проверим оптимальность плана. Сосчитаем общую стоимость перевозок. Результаты представим в таблице и после этого определим вводимую в базис переменную и исключаемую переменную.
Для этого найдем потенциалы αi, βj по занятым клеткам таблицы, в которых αi+βj=Сij. Потенциалы представлены слева и вверху таблицы. В нижнем левом углу ячеек рассчитаны оценки для небазисных переменных по свободным клеткам таблицы. Базисные переменные выделены.
Отзывы
Отзывов пока нет.