КАФЕДРАИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИКУРСОВАЯ РАБОТА ПО ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ Выполнил Студент 2 курса заочного отделенияКалинкин Степан ВалерьевичФакультет ЭМиАТСпециальность 1502Зач тная книжка 0084 Содержание.1. Задача 32. Задача 73. Списоклитературы 12 ЗАДАЧА 2 Вариант 1. Условиезадачи. Требуется перевезти товары с тр х складов вчетыре магазина. Дан ные о наличии товаров на складе, спрос на него вмагазинах, а также стои мости перевозки единицы груза между складами имагазинами приведены в таблице.
Составить план перевозки, чтобы затраты былиминимальными. 2. Построениематематической модели. Пусть X ij количество деталей, отправленных со склада i в магазин j, а C ij стоимость перевозки одной детали сосклада i в магазин j. Очевидно, что X ij gt 0 и C ij gt 0.В силу ограничений на возможностьпоставки товара со склада и спрос в магазинах величина X ij должна удовлетворять следующим условиям 30Общаястоимость перевозок равна Z C ij X ij 21 X 11 36 X 12 28 X 13 21 X 14 25 X 21 35 X 22 26 X 23 25 X 24 23 X 31 21 X 32 27 X 33 21 X 34, т.е. Z C ijX ij. 3 Необходимо определить такиенеотрицательные значения переменных X ij,которые удовлетворяют ограничениям 1 и 2 и обращают в минимум целевуюфункцию Z 3 . В такойпостановке задача является транспортной задачей линейного программирования.
Необходимым и достаточным условием разрешимоститранспортной задачи является условие баланса S i M j Где, S i X ij cуммарное количество деталей наскладах M j X ij суммарное количество деталей, требуемое в магазинах.
В данной задаче Si M j 100,Следовательно, задача с балансом.3. Решение задачи. Решение задачи состоит из двух этапов 1. Определениедопустимого решения.2. Определениедопустимого решения методом наименьшей стоимости. На основе исходной таблицыпостроим вспомогательную таблицу в верхнем правом углу каждой клетки будем записыватьстоимости перевозки . Введ м в таблицу вспомогательную строку и столбец длязаписи остатков.
Определимнаименьшую стоимость перевозки X 14 min 25, 30 25X 32 min 30, 10 10X 34 min 20, 5 5X 31 min 15, 15 15X 21 min 45, 15 15X 23 min 30, 30Стоимость перевозки Z 25 21 25 15 30 26 15 23 10 21 5 21 2340 усл. ед.Последовательное улучшение допустимого решения методомпотенциалов.Выберем вспомагательныепеременные U i и V j, обращающие в нули коэффициенты при базисныхпеременных, то естьC ij U i V j 4 Такие переменные называются потенциалами. Выполнимследующие действия 1. Для всех Xij gt 0 т. е. для всехзанятых клеток составим потенциальные уравнения C 14 U 1 V 4 0 21 U 1 V 4 0C 21 U 2 V 1 0 25 U 2 V 1 0 C 23 U 2 V 3 0 26 U 2 V 3 0 5 C 31 U 3 V 1 0 23 U 3 V 1 0C 32 U 3 V 2 0 21 U 3 V 2 0C 34 U 3 V 4 0 21 U 3 V 4 0Для определения m n потенциаловнеобходимо, чтобы было m n 1 уравнений где m числострок, n числостолбцов . Тогда одному из потенциалов можно присвоить любое значение, напримерравное нулю, а значения других потенциалов получить, решая систему уравнений 5 .Для данной задачи m n 1 6 и число занятыхклеток равно 6. U 1 -2U 2 0U 3 -2. Решим систему уравнений 4, присвоив значение,равное нулю, наиболее часто встречающемуся неизвестному индексу U 2 0, тогда V 1 25 U 1 -2 V 2 23 U 2 0 V 3 26 U 3 -23 Занес мданные в таблицу выше.3. Для всех небазисных переменных, т.е. для X ij 0 дляпустых клеток , определим невязки G ij C ij S ij, где S ij U i V j. G 11 C 11 U 1 V 1 G 11 27 -2 25 4 G 12 C 12 U 1 V 2 G 12 36 -2 23 15 G 13 C 13 U 1 V 3 G 13 28 -2 26 4 6 G 22 C 22 U 2 V 2 G 22 35 0 23 12 G 24 C 24 U 2 V 4 G 24 25 0 23 2 G 33 C 33 U 3 V 3 G 33 27 -3.Отрицательных невязок нет, значит найденныйплан см. таблицу выше оптимален и значение целевой функции является минимальным.Таким образом, минимальная стоимость перевозокZ равна 2340 усл. ед. и достигается при объ мах перевозок X 14 25, X 21 15, X 23 30, X 31 15, X 32 10, 5.ЗАДАЧА 1. Условиезадачи. Фирма должна наладить перевозкупродуктов с базы в 7 магазинов. Сеть дорог, связывающая базу и магазины междусобой, а также длины участков дороги между каждой парой соседних пунктовпредставлены на рисунке.Определить кратчайшие пути от базы до каждого измагазинов.
Х 4 Х 1 Х 7 Х 5 Х 3 Х 2 Х 8 Х 2. Построениематематической модели. Пусть G A, U граф, где A множество вершин, означающих объекты базу вершина 1, а магазины вершины 2, 3, 4, 5, 6, 7, 8 , U множество р бер, означающихвозможную связь между двумя вершинами. Каждому ребру поставлено в соответствиенекоторое число L ij i, j 1, 2 8 весребра расстояние между двумя вершинами .Задача отыскания кратчайшего путииз вершины i в вершину j заключается в минимизациицелевой функции Y L i X ij ,где X ij 1, если путь проходит извершины i в вершину j, X ij 0, в противном случае.Даннаяфункция определяет длину между заданной начальной и конечной вершинами.
При этом должны выполняться следующие условия X ij X ji 0, i 2,3, ,m 1 т.е. для любой вершины i, исключаяначальную и конечную, число путей, входящих в эту вершину, равно чису путей,выходящих из не X 1j X j1 1. т. е. впоследнюю вершину входит на один путь больше, чем выходит X mj X jm 1. т. е. количество путей, входящих в вершину 1, превышает наединицу число путей, выходящих из не .Необходимо определить такиезначения X ij, равные 0 или 1, которые доставят минимум целевой функции Y при соблюдении условий, заданныхограничениями.Данная задача является задачей о кратчайшем пути и может быть решена индексно матричным методом.3. Решение задачи.Составим матрицу весов графа, представленного на рисунке.
Эле-мент L ij этой матрицы равен весуребра, если вершины i иj связаны между собойребром, и бесконечности в противном случае.
Диагональные элементы также равныбесконечности, так как граф без петель.
Для наглядности в матрицу весовбесконечности записывать не будем, оставляя соответствующие им клетки пустыми.Добавим к составленной таким образом матрице нулевую строку и нулевой столбец, в которые будем записывать соответственноиндексы столбцов и строк U i и V j U i расстояниеот вершины 1 до вершины i, V j расстояние от вершины 1 до вершины j . Тогда матрица весов будет иметь вид, представленный в таблицениже.
Для вычисления индексов выполним следующиедействия 1. ПоложимU 1 V 1 0 2. Значения всех заполненных клеток первой строкиперенес м на соответствующие места индексов столбцов V j и строк U i , т. е. V 2 8, V 3 10, V 4 10, V 7 12, U 2 V 2 8, U 3 V 3 10, U 4 V 4 10, U 7 V 7 12 смотрите таблицу ниже 3. Определимнедостающие индексы V j. В нашем примере этоиндексы V 5, V 6 и V 8. Для этого в каждом столбце,соответсвующем неизвестному индексу V j, просмотрим заполненные клетки и вычислим недостающие индексы поформуле V j U i L ij, если для них известны индексы U i.Для столбца, соответствующегоиндексу V 5, этими элементами будут L 4, 5 16 и L 7, 5 25. Значения U 4 и U 7 известны U 4 10, U 7 12.Следовательно, V 5 min U 4 L 4, 5 10 16 26 U 7 L 7, 5 12 25 37 26.Для столбца, соответствующегоиндексу V 6, ими будут L 2, 6 7, L 3, 6 17, L 7, 6 18. Значения индексов U 2, U 3, U 7 известны U 2 8, U 3 10, U 7 12. Следовательно, V 6 min U 2 L 2, 6 8 7 15 U 3 L 3, 6 10 17 27 U 7 L 7, 6 12 18 30 15.Для столбца, соответствующегоиндексу V 8, ими будут L 5, 8 17, L 6, 8 13, L 7, 8 19.Значения индексов U 5, U 6, U 7 известны U 5 26, U 6 15, U7 12. Следовательно, V 8 min U 5 L 5, 8 26 17 43 U 6 L 6, 8 15 13 28 U 7 L 7, 8 12 19 31 28.Запишем ихв строку V i смотритетаблицу ниже .4. Всеиндексы найдены.
Проверим полученное решение на оптимальность, т. е. выполнение условия L ij gt V j U i для каждой заполненнойклетки матрицы.Для всех заполненных клетокусловие L ij gt V j U i соблюдается.
Полученное решение является оптимальным.
Следовательно,минималь ными расстояниями от вершины 1 до всех остальных будут V 2 8, V 3 10, V 4 10, V 5 26, V 6 15, V 7 12, V 8 28.Определим кратчайший путь от вершины 1 довершины 5. Для этого в столбце 5 найд м элемент, значение которого равноразности индексов столбца и строки L ij V j U i L 4, 5 V 5 U 4 26 10.L 4, 5 последнее звено пути и,соответственно, вершина 4 предпоследняя.И далее, в столбце 4 определим L 1, 4 V 4 U 1 10 0 10.L 1, 4 первое звено пути, так каквершина 1 является начальной фиксированной.Таким образом, имеем минимальный путь отвершины 1 до вершины 5, проходящий через вершины 1, 4, 5, длина которогоравна 26.