Математические модели в транспортных системах. Математические модели в транспортных системах КР-2. Задача 2 Решить графическим методом задачу линейного программирования, при ограничениях 1,24х 1 0,8х 2 2,4
 Скачать 328.59 Kb.
|
|
Математические модели в транспортных системах Задача 2 Решить графическим методом задачу линейного программирования, при ограничениях: 1,24х1 – 0,8х2  2,40,84х1 + 1,2х2 3,3и целевой функции: Z = 2,7x1 + 3.1x2  maxРешение: Точки, координаты которых удовлетворяют одновременно всем неравенствам системы ограничений, называются областью допустимых решений. Очевидно, для нахождения области допустимых решений данной задачи, необходимо последовательно рассмотреть каждое неравенство. (см. шаг 1 - шаг 2) Последние два шага (см. шаг 3 - шаг 4) служат непосредственно для получения ответа. Это стандартная схема решения. Если область допустимых решений представляет собой точку или пустое множество, то решение будет короче. По условию задачи: x1 ≥ 0 x2 ≥ 0. Если бы это было единственным условием, то область допустимых решений имела бы вид, как на рисунке (вся первая четверть). Перейдем к обыкновенным дробям для удобства решения  Шаг №1 Рассмотрим неравенство 1 системы ограничений. 31/25 x1 - 8/10 x2 ≤ 24/10 Построим прямую: 31/25 x1 - 8/10 x2 = 24/10 Пусть x1 =0 => - 8/10 x2 = 24/10 => x2 = -3 Пусть x2 =0 => 31/25 x1 = 24/10 => x1 = 60/31 Найдены коородинаты двух точек (0, -3) и (60/31 ,0). Соединяем их и получаем необходимую прямую (1). Нас интересуют точки расположенные выше или ниже построенной прямой (1) Вернемся к исходному неравенству. 31/25 x1 - 8/10 x2 ≤ 24/10 Преобразуем неравенство, оставив в левой части только x2 - 8/10 x2 ≤ - 31/25 x1 + 24/10 x2 ≥ 31/20 x1 - 3 Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (1). Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.  Шаг №2 Рассмотрим неравенство 2 системы ограничений. 84/10 x1 + 12/10 x2 ≤ 33/10 Построим прямую: 84/10 x1 + 12/10 x2 = 33/10 Пусть x1 =0 => 12/10 x2 = 33/10 => x2 = 11/4 Пусть x2 =0 => 84/10 x1 = 33/10 => x1 = 11/28 Найдены коородинаты двух точек (0, 11/4) и (11/28 ,0). Соединяем их и получаем необходимую прямую (2). Нас интересуют точки расположенные выше или ниже построенной прямой (2) Вернемся к исходному неравенству. 84/10 x1 + 12/10 x2 ≤ 33/10 Преобразуем неравенство, оставив в левой части только x2 12/10 x2 ≤ - 42/5 x1 + 33/10 x2 ≤ - 7 x1 + 11/4 Знак неравенства ≤ . Следовательно, нас интересуют точки расположенные ниже построенной прямой (2). Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.  Шаг №3 Строим вектор C = (27/10, 31/10), координатами которого являются коэффициенты функции F.  Шаг №4 Будем перемещать "красную" прямую, перпендикулярно вектору C, от левого нижнего угла к правому верхнему. В точке, в которой "красная" прямая в первый раз пересечет область допустимых решений, функция F достигает своего наименьшего значения. В точке, в которой "красная" прямая в последний раз пересечет область допустимых решений, функция F достигает своего наибольшего значения. Функция F достигает наибольшего значения в точке A. (см. рисунок) Координаты точки A (0,11/4) известны. (см. шаг 2) Вычислим значение функции F в точке A (0,11/4). F (A) = 27/10 * 0 + 31/10 * 11/4 = 341/40  Ответ: x1 = 0 x2 = 11/4 = 2,75 F max = 341/40 = 8,525 Задача 3 Найти кратчайшие расстояния от пункта 4 до всех других пунктов заданной транспортной сети, используя метод потенциалов. Найти кратчайшую связывающую сеть.  Решение Транспортная есть представляет собой систему дорог (улиц города), которые пригодны по качеству дорожного покрытия, ширине проезжей части, и открыты для движения подвижного состава. Она состоит из отдельных элементов. Ими являются вершины (пункты) и звенья сети. Вершины транспортной сети представляют собой точки на карте города или местности (перекрёстки, пересечения, площади, грузообразующие и грузопоглащающие пункты, микрорайоны), наиболее важные для определения расстояний или маршрутов движения. Каждой вершине присваивается порядковый номер или другое условное обозначение. Две соседние вершины (два соседних пункта) можно соединить линией, по которой осуществляется непосредственная связь между этими вершинами с указанием расстояния между ними. Эти линия называются звеньями сети. Совокупность всех вершин и звеньев называется сетью. Транспортная сеть считается заданной, если определены вершины сети, звенья и их длина. Расстояния между вершинами или отдельными пунктами транспортной сети определяются путём замера расстояний от каждого пункта до всех остальных по масштабным картам (плану) местности или города, которые затем корректируются путём умножения на коэффициент приведения (1,1÷1,3). Задача определения кратчайших расстояний является задачей многовариантной, которая имеет множество допустимых решений. Для нахождения оптимального решения применяются математические методы, позволяющие осуществить решения как вручную, так и с использованием современных ЭВМ. Задача методом потенциалов решается следующим образом: Шаг 1. Вершина, от которой требуется определить кратчайшие расстояния, называется начальной. Ей присваивается потенциал Vi = 0 . Шаг 2. Просматриваются все звенья, начальные вершины i которых имеют потенциалы Vi, а конечные j – не имеют. Определяется значение потенциалов конечных вершин Vj по формуле:  где  – длина звена ( i – j ), т.е. расстояние между вершинами i и j .Из всех полученных потенциалов выбирается наименьший и его значение присваивается соответствующей конечной вершине. Звено ( i – j ) отмечается стрелкой. Шаг 2 повторяется до тех пор, пока всем вершинам данной сети не будут присвоены потенциалы. Величина потенциалов у соответствующих вершин показывает кратчайшее расстояние от выбранного начального до данного пункта. Звенья со стрелками образуют кратчайший маршрут движения от начального пункта до всех остальных. Принимая за начало сети последовательно каждый её пункт (вершину) и выполняя расчёты по описанному методу, можно получить таблицу кратчайших расстояний между всеми пунктами сети. Выберем расстояния для заданной сети 1 – 2 = 11 см =110 мм = 220 км 4 – 3 = 4 см = 40 мм = 80 км 3 – 1 = 6,5 см = 65 мм = 130 км 3 – 2 = 5,5 см =55 мм = 110 км 3 – 6 = 4,5 см = 45 мм = 90 км 6 – 7 = 3,5 см = 35 мм = 70 км 7 – 5 = 6,5 см =65 мм = 130 км 6 – 5 = 3 см =30 мм = 60 км 4 – 5 = 5 см =50 мм = 100 км 6 – 1 = 4,5 см =45 мм = 90 км  Необходимо определить кратчайшее расстояние от вершины 4 до всех остальных вершин (пунктов) сети на рисунке 1. Шаг 1. Принимается V4 = 0 . Шаг 2. 1) Определяются звенья, для которых вершина 4 является начальной. На рисунке 1 – это звенья (4 – 3), (4 – 5). Вычисляются потенциалы конечных вершин этих звеньев по формуле 1:  ; ;2) выбирается наименьшее значение этих потенциалов:  ;3) звено (4 – 3)отмечается стрелкой. Вершине 3 присваивается значение потенциала равное 80. Потенциалы проставляются в виде квадратов на рисунке 1 около соответствующих вершин. Вновь повторяется шаг 2, но за начальную вершину принимается вершина 3, потенциал которой определён. Теперь можно получить значения потенциалов для вершин (3 – 1), (3 – 2).(3 – 6):  ; ; ;Из всех полученных сейчас и на первом этапе расчёта значений потенциалов выбирается наименьшее –  . Это значение проставляется в квадрате у вершины 6. Звено (3 – 6)отмечается стрелкой. Теперь в качестве начальной вершины используется вершина 6. Она связана с вершинами 1, 5 и 7 звеньями (6 – 1), (6 – 5),(6 – 7). Определяется значение потенциалов для этих вершин:  ; ; ;стрелкой отмечается звено (6 – 5). Аналогично выбирается потенциал для вершин 5: Стрелкой отмечается звено (5 – 4). На основании проведённых расчётов может быть составлена таблица кратчайших расстояний между пунктами транспортной сети в таблице 1. Таблица 1. Кратчайшие расстояния между пунктами транспортной сети
В итоге наименьший пробег:  80 + 90 + 60 +100 = 330 км Задача 4 Решить транспортную задачу линейного программирования для данных:
Ai – i-ый поставщик Bj – j-ый потребитель QAi – объем запаса у i-го поставщика (далее запас) QBj – объем потребления j-го потребителя (далее потребность) В клетках указаны затраты на поставку единицы ресурса от i-го поставщика к j-му потребителю | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||