![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Прикладная математикаСтр 1 из 2Следующая ⇒
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ
Пермь 2012 Преподавание дисциплины " Прикладная математика" обосновывается на необходимости изучения арсенала математических методов и моделей для применения их в решении практических задач в различных сферах коммерческой и финансовой деятельности, позволяющие получить более выгодные, оптимальные решения в сравнении с традиционными приемами, привить навыки самостоятельного изучения литературы по математическим методам решения коммерческих задач, развить логическое мышление, повысить уровень математической культуры, выработать навыки математического исследования проблем и задач финансовой и коммерческой деятельности. Курс изучается по программе " Прикладная математика", утвержденной в 1992 г. Цель настоящих методических указаний: оказать помощь студентам в изучении разделов и тем курса " Прикладная математика" для развития навыков по применению различных математических методов и моделей в решении практических задач коммерческой деятельности, а также подготовить к самостоятельному изучению литературы по математическим методам в экономике и применения их к решению новых проблем и задач в финансовой и коммерческой сферах. Для выполнения контрольной работы студенту необходимо ознакомится с программой курса " Прикладная математика", с методическими указаниями и контрольными заданиями. При изучении студент должен пользоваться рекомендуемой литературой, материалами устных и письменных консультаций, закрепляя усвоение каждой темы решением практических задач. Студент, завершивший самостоятельное изучение дисциплины, должен выполнить две контрольные работы и сдать экзамен.
IV.МЕТОДИЧЕСКИЕ УКАЗАНИЯ К РЕШЕНИЮ ЗАДАЧ 1. Графический метод решения задач линейного программирования Общей задачей линейного программирования ОЗЛП называется задача, которая состоит в определении максимального (минимального) значения линейной целевой функции:
При условиях-ограничениях
где Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции при выполнении условий 1 и 3, где Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции при выполнении условий 2 и 4, где Совокупность чисел План В случае, когда требуется найти минимум функции Ограничение-неравенство исходной задачи линейного программирования, имеющее вид "
Допустим ограничения задачи отображают наличие производственных ресурсов, тогда числовое значение дополнительной переменной в плане задачи, записанной в форме основной, равно объему неиспользуемого соответствующего ресурса. План Так как векторы Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае - план вырожденный. Свойства основной задачи линейного программирования связаны со свойствами выпуклых множеств. Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит и их произвольную выпуклую линейную комбинацию. Геометрический смысл этого определения состоит в том, что множеству вместе с его двумя произвольными точками полностью принадлежит и прямолинейный отрезок, их соединяющий. Примерами выпуклых множеств являются прямолинейный отрезок, полуплоскость, круг, шар, куб, полупространство и др. Угловыми точками выпуклого множества называются точки, не являющиеся выпуклой комбинацией двух произвольных точек множества. Например, угловыми точками треугольника являются его вершины, круга - точки окружности, которые его ограничивают. Множество планов основной задачи линейного программирования является выпуклым (если оно не пусто). Непустое множество планов называется многогранником решений, а всякая угловая точка многогранника решений - вершиной. Если основная задача линейного программирования имеет оптимальный план, то максимальное значение целевая функция задачи принимает в одной из вершин многогранника решений. Если максимальное значение достигается более чем в одной вершине, то целевая функция принимает его во всякой точке, являющейся выпуклой линейной комбинацией этих вершин. Непустое множество планов основной задачи линейного программирования образует выпуклый многогранник, каждая вершина которого определяет опорный план. Для одного из опорных планов (т.е. в одной из вершин многогранника решений) значение целевой функции является максимальным (при условии, что функция ограничена сверху на множестве планов). Вершину многогранника решений, в которой целевая функция принимает максимальное значение, можно найти достаточно просто, если задача в стандартной форме содержит не более двух переменных: при условиях Каждое из неравенств системы ограничений задачи геометрически определяет полуплоскость допустимых значений переменных соответственно с граничными прямыми Если система неравенств совместна, то областью допустимых решений задачи является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств. Решение задачи линейного программирования графическим методом включает следующие этапы. 1. На плоскости 2. Находят полуплоскости, определяемые каждым из ограничений задачи. 3. Строят многоугольник решений. 4. Строят вектор 5. Строят начальную прямую 6. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке. Минимальное значение линейной функции цели находится путем передвижения начальной прямой противоположном вектору Пример Найти максимум и минимум линейной функции:
Решение; Построим на плоскости Для этого в неравенствах системы ограничений и условиях не отрицательности переменных знаки неравенств заменим на знаки точных равенств.
Построив полученные прямые, найдем соответствующие полуплоскости и их пересечение
Построив полученные прямые, найдем соответствующие полуплоскости и их пересечение Многоугольником решений задачи является пятиугольник АВ-СДЕ, координаты точек которого удовлетворяют условию неотрицательности и неравенствам системы ограничений задачи. Для нахождения точек экстремума построим начальную прямую Решив систему уравнений, получим: Для нахождения минимального значения целевой функции задачи перемещаем начальную прямую в направлении, противоположном вектору значение в угловой точке Е, где Найдем координаты угловых точек В, Д и А. Для этого решим следующие системы уравнений: В результате получим координаты точек В (0; 2, 5), Д (2, 0) и А (0, 1). Вычислим значения целевой функции во всех угловых точках многоугольника решений АВСДЕ:
КОНТРОЛЬНЫЕ ВОПРОСЫ 1. Сформулируйте общую задачу линейного программирования. 2. Дайте определение невырожденного и вырожденного опорного плана, оптимального плана. 3. Какое множество называется выпуклым? 4. Какая точка выпуклого множества называется угловой? 5. Дайте геометрическую интерпретацию задачи линейного программирования. 6. В какой точке многогранника решений целевая функция задачи линейного программирования достигает оптимального значения? 7. Какие задачи линейного программирования можно решить графическим методом? 8. Назовите особые случаи при решении задачи линейного программирования графическим методом. 2. Симплексный метод решения задачи линейного программирования. Симплексный метод основан на последовательном переходе от одного опорного плана задачи линейного программирования к другому, при этом значение целевой функции изменяется. Рассмотрим алгоритм симплексного метода на примере задачи планирования товарооборота. Коммерческое предприятие реализует несколько 1. Математическую модель задачи запишем следующим образом: Определить и обеспечивает максимальное значение целевой функции
Алгоритм симплексного метода включает следующие этапы. 2. Составление первого опорного плана. Система ограничений задачи, решаемой симплексным методом, задана в виде системы неравенств. Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных переменных. Векторы-столбцы при этих переменных представляют собой единичные векторы и образуют базис, а соответствующие им переменные называются базисными: где
Решим эту систему относительно базисных переменных: а функцию цели перепишем в таком виде:
Полагая, что основные переменные .получим первый опорный план 3. Проверка плана на оптимальность. Если все коэффициенты индексной строки симплексной таблицы при решении задачи на максимум неотрицательны ( план табл.3 4. Определение ведущих столбца и строки. Из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине, что и определяет ведущий столбец, который показывает, какая переменная на следующей итерации перейдет из свободных в базисные. Затем элементы столбца свободных членов симплексной таблицы делим на соответствующие только положительные элементы ведущего столбца. Результаты заносим в отдельный столбец Элемент симплексной таблицы, находящейся на пересечении ведущих столбца и строки, называют разрешающими и выделяет кружком. 5. Построение нового опорного плана Переход к новому плану проводится пересчетом симплексной таблицы по методу Жордана-Гаусса. Сначала заменим переменные в базисе, т.е. вместо Разделим все элементы ведущей строки предыдущей симплексной таблицы на разрешающий элемент и результаты деления занесем в строку следующей симплексной таблицы, соответствующую введенной в базис переменной нового плана находятся по правилу прямоугольника: где А и В - элементы старого плана, образующие прямоугольник с элементами
6. Полученный новый опорный план опять проверяется на оптимальность в соответствии с этапом 3 алгоритма. При решении задачи линейного программирования на минимум целевой функции, признаком оптимальности плана является отрицательные значения всех коэффициентов индексной строки симплексной таблицы. Если в направляющем столбце все коэффициенты Если в столбце симплексной таблицы содержатся два или несколько одинаковых наименьших значения, то новый опорный план будет вырожденным (одна или несколько базисных переменных станут равными нулю). Вырожденные планы могут привести к зацикливанию, т.е. многократному повторению процесса вычислений, не позволяющему завершить задачу. С целью исключения этого для выбора направляющей строки используют способ Креко, который заключается в следующем. Делим элементы строк, имеющие одинаковые наименьшее значение Если в оптимальный план вошла дополнительная переменная Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов. Свободную переменную, соответствующую указанному столбцу, можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.
Примеры решения задачи симплексным методом Торговое предприятие, располагающее материально-денежными ресурсами, реализует три группы товаров А, В и С. Плановые нормативы затрат ресурсов на тыс. руб. товарооборота, прибыль от продажи товаров на тыс. руб. товарооборота, а также объем ресурсов заданы в таблице 2. Определить плановый объем продажи и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.
Таблица 2
1.Запишем математическую модель задачи. Определить
и обеспечивают максимальное значение целевой функции
Для построения первого опорного плана систему неравенств, приведем к системе уравнений.
В матрице этой системы уравнений
Векторы
Соответствующие этим векторам переменные Решим систему уравнений относительно базисных переменных.
Функцию цели запишем в виде: 2.Полагая, что свободные переменные
следовательно товары не продаются и прибыль равна нулю, а ресурсы не используются. Заносим первый опорный план 1 в симплексную таблицу 3.
Первый опорный план 1 не оптимальный, так как в индексной строке находятся отрицательные коэффициенты - -3, -5, -4. За ведущий столбец выберем столбец, соответствующий переменной
Следовательно, первая строка является ведущей. Разрешающий элемент равен 0, 2 и находится на пересечении ведущего столбца и ведущей строки и выделен кругом. 5. Формируем следующую симплексную таблицу. Вместо переменной Таким образом, в новом плане II заполнены строки Элементы строки определяются аналогично:
Все элементы, расположенные на пересечении строк и столбцов, соответствующих одновременным базисным элементам равны 1, остальные элементы столбца в базисах векторов, включая индексную строку, равны 0. Аналогично проводятся расчеты по всем строкам таблицы, включая индексную. Выполняя последовательно все этапы алгоритма, формируем план II. 6.На третьей интеракции таблицы 3 получаем план III, который является оптимальным, так как все коэффициенты в индексной строке Оптимальный план можно записать так: X = (250, 5375, 0, 0, 0, 1875), Следовательно, необходимо продавать товаров первой группы А 250 ед., а второй группы В - 5375 ед. При этом торговое предприятие получает максимальную прибыль в размере 27625 тыс. руб. Товары группы С не реализуются. " В оптимальном плане среди базисных переменных находится дополнительная переменная В индексной строке оптимального плана в столбцах переменных
КОНТРОЛЬНЫЕ ВОПРОСЫ 1. Какие задачи линейного программирования можно решать симплексным методом? 2. Каков признак оптимальности в симплексном методе? 3. Как строится первый опорный план? 4. Как определяется ведущий столбец и ведущая строка симплексной таблицы? 5. Как осуществляется пересчет элементов симплексной таблицы? 6. Каковы особые случаи при реализации симплексного метода?
3. ДВОЙСТВЕННАЯ ЗАДАЧА. Двойственная задача формулируется следующим образом. Определить оценку единицы каждого вида ресурсов, чтобы при заданных объемах ресурсов Запишем математическую модель двойственной задачи. Определить и доставляет минимальное значение целевой функции Ограничения показывают, что стоимость всех ресурсов, затраченных на продажу единицы Для симметричной пары задач двойственная задача по отношению к исходной составляется согласно следующим правилам: Число переменных в двойственной задаче равно числу ограничений в прямой задаче. Матрица коэффициентов системы ограничений двойственной задачи получается из матрицы коэффициентов системы ограничений прямой задачи путем транспонирования. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи. Свободными членами системы ограничений двойственной задачи являются коэффициенты функции цели прямой задачи. На каждую переменную двойственной задачи накладывается условие не отрицательности. Двойственная задача решается на минимум, если целевая функция прямой задачи задается на максимум, и наоборот. Двойственная задача решается на минимум, если целевая функция прямой задачи задаётся на максимум, и наоборот. Коэффициентами функции цели двойственной задачи служат свободные члены системы ограничений прямой задачи. Решение прямой задачи дает оптимальные объемы в структуру товарооборота торгового предприятия, а решение двойственной - оптимальную систему оценок ресурсов, используемых для реализации товаров. Установим сопряженные пары переменных прямой и двойственной задач. Запишем переменные задач в двух строчках. В первой располагаем переменные основные дополнительные
дополнительные основные Согласно сопряженным парам переменных из решения прямой задачи можно получить решение двойственной, не решая ее, и наоборот, из решения двойственной задачи можно получить решения прямой. Составим, например, двойственную задачу к прямой задаче, которая решена выше симплексным методом. Определить и обеспечивает минимальное значение целевой функции Z( Таким образом, оптимальный план двойственной задачи имеет вид: _
По этим данным проводится анализ оптимального плана двойственной задачи по оценке ресурсов, используемых для реализации товаров.
КОНТРОЛЬНЫЕ ВОПРОСЫ 1. Как сформулировать экономическую постановку двойственной задачи к задаче планирования торгового процесса? 2. Как записывается математическая модель прямой и двойственной задач? 3. Каков план построения двойственной задачи? 4. Как определяется сопряженные пары переменных: прямой и двойственной задач?
4. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Транспортная задача заключается в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления Рассмотрим транспортную задачу, где в качестве критерия оптимальности является стоимость перевозок всего груза, которая должна быть минимальной.
Введем обозначения:
Определить план перевозок груза из пунктов отправления в пункты назначения так, чтобы: вывести все грузы от поставщиков; удовлетворить заявки каждого потребителя; обеспечить минимальные транспортные расходы на перевозку груза. Все исходные данные транспортной задачи можно записать в виде транспортной таблицы 4. Таблица 4
где
Математическая постановка транспортной задачи заключается в определении матрицы
а) Всякое неотрицательное решение системы линейных уравнений, определяемое матрицей
б) Ранг матрицы, составленный из коэффициентов при неизвестных системы линейных уравнений транспортной задачи, на единицу меньше числа уравнений, т.е. равен в) Допустимый план транспортной задачи, имеющий не более
г) Если в опорном плане число отличных от нуля компонент равно в точности д) План е) Для решения транспортной задачи необходимо и достаточно, чтобы суммарные запасы груза в пунктах отправления были равны сумме заявок пунктов назначения: ж) Модель транспортной задачи, удовлетворяющая этому условию, называется закрытой. Если же указанное условие не выполняется, то модель называется открытой. В случае превышения запаса над заявками: вводится фиктивный
При Рассмотрим один из методов построение первого опорного плана - метод наименьших тарифов. з) Наилучшим элементом матрицы тарифов называется наименьший тариф, если задача поставлена на минимум, наибольший тариф - если задача поставлена на максимум целевой функции. Алгоритм построения первого опорного плана методом наименьшей стоимости включает следующие этапы. 1. Среди тарифов находится наименьший. 2. Клетку с выбранным тарифом заполняем максимально возможным объемом груза с учетом ограничений по строке и столбцу, при этом либо весь груз вывозится от соответствующего поставщика, либо полностью удовлетворяется заявка потребителя. Строка или столбец таблицы вычеркивается и в дальнейшем распределении не участвует. 3. Из оставшихся тарифов вновь находим наилучший, и процесс продолжается до тех пор, пока не будет распределен весь груз. Если модель транспортной задачи открытая и введены фиктивный поставщик или потребитель, то распределение осуществляется сначала для действительных поставщиков и потребителей, и в последнюю очередь нераспределенный груз направляется от фиктивного поставщика или к фиктивному потребителю. Дальнейшее улучшение первого опорного плана и получение оптимального плана производим методом потенциалов. и) План
при решении задачи на минимум, а при решении задачи на максимум:
Потенциалы Введем обозначение оценки свободной клетки таблицы: Если среди оценок Алгоритм метода потенциалов включает следующие этапы. 1. Построение первого опорного плана. 2. Проверка вырожденности плана. Потенциалы 3. Определение значения функции цели путем суммирования произведений тарифов (удельных затрат) на объем перевозимого груза по всем занятым клеткам таблицы.
4. Проверка условия оптимальности. Определением потенциалы клетки таблицы записываем уравнение ( Так как число переменных больше числа уравнений В транспортную таблицу добавляется дополнительная строка и столбец, куда заносятся потенциалы. Определяем оценки свободных клеток Если все 5. Построение нового опорного плана. Из всех положительных оценок свободных клеток выбираем наибольшую (если задача поставлена на минимум), из отрицательных - наибольшую по абсолютной величине (если задача поставлена на максимум). Клетку, которой соответствует наибольшая оценка, следует заполнить, т.е. направить груз. Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых клеток и связанных с заполнением, так называемым циклом. Циклом или прямоугольным контуром в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, другое - в столбце. Если ломаная линия, образующая цикл, пересекается, то точки пересечения не являются вершинами. Для каждой свободной клетки таблицы можно построить единственный цикл. Вершинам цикла, начиная от вершины, находящейся в свободной клетке, присваиваем поочередно знаки " +" и " -". Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее и обозначим его 9. Перераспределяем величину 8 по циклу, прибавляя ее к соответствующим объемам грузов, стоящим в минусовых клетках. Клетка, которая ранее была свободной, становится занятой, а одна из занятых клеток цикла становится свободной. В результате получаем новый опорный план и возвращаемся к четвертому этапу алгоритма.
ЗАМЕЧАНИЯ 1. Если в минусовых клетках построенного цикла находятся два (или несколько) одинаковых минимальных значения 2. Если в оптимальном плане транспортной задачи оценка для некоторой свободной клетки 3. Значение функции цели на каждой интеракции можно рассчитать следующим образом:
Пример решения транспортной задачи На три базы пункты назначения заданы матрицей тарифов (в руб.):
Составить план перевозок однородного груза с минимальными транспортными издержками. Проверим необходимое и достаточное условие разрешимости задачи.
Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на трех базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу
|