6 amaliy mashg'ulot. Transport masalasi
Download 243 Kb.
|
6 Amaliyot variantlar
|
6 - amaliy mashg'ulot. Transport masalasi Amaliyotda chiziqli dasturlash masalalari orasida ko'pincha ularning xususiyatlaridan bir-biridan farq qiladigan narsalar mavjud. Bunday vazifalar orasida, masalan, transport vazifalari mavjud. Transport muammosining klassik formulasini ko'rib chiqing. Muayyan turdagi mahsulotlarni etkazib beruvchilar (ishlab chiqaruvchilar) ning m nuqtalari bo'lsin. Mumkin bo'lgan mahsulotlarni etkazib berish hajmi berilgan hisoblanadi. Biz ularni belgilaymiz . Эта продукция используется n потребителями, потребности которых также считаются заданными. Обозначим их через . Будем считать, что стоимость перевозки одной единицы продукции от i-го поставщика к j-му потребителю линейно зависит от объема перевозимого однородного груза, она известна для всех , , и равна . Har bir yetkazib beruvchidan har bir iste'molchiga mahsulotni tashish uchun shunday rejani tuzish kerak bo’ladiki, bunda transportning umumiy qiymati minimal bo'lsin. Faraz qilaylik, birinchidan, butun yuk iste'molchilarga yetkaziladi, ikkinchidan, iste'molchilarning ehtiyojlari to'liq qondiriladi, ya'ni balans sharti bajariladi. Bunday qaratilayotgan masala yopiq transport masalasi deb ataladi. Masalaning matematik modelini tuzamiz. i- yetkazib beruvchidan j-iste’molchiga tashilgan yuk hajmini , , , deb belgilaymiz. Keyin, masalaning cheklovlariga ko'ra, uning matematik modeli quyidagicha bo'ladi: Ko'rinib turibdiki, bu masala mn o'zgaruvchiga va m+n asosiy cheklovlarga ega chiziqli dasturlash masalasidir. Umuman olganda, balans sharti qoniqtirilmasligi mumkin. Bunday holda, masalaning matematik modeli tegishli o'zgarishlarga uchraydi. Ushbu o'zgarishlar asosiy cheklovlardagi tengsizliklar sifatida ifodalanadi. Xayoliy yetkazib beruvchini (talab taklifdan oshib ketganda) yoki xayoliy iste'molchini (taklif talabdan oshib ketganda) joriy etish orqali bunday muammoni yopiq transport muammosiga qisqartirish mumkin. Вообще говоря, условие баланса может и не выполнится. В этом случае математическая модель задачи претерпит соответствующие изменения. Эти изменения будут выражены в виде неравенств в основных ограничениях. Путем ввода фиктивного поставщика (в случае, когда спрос превышает предложение) или фиктивного потребителя (в случае, когда предложение превышает спрос) такая задача может быть приведена к закрытой транспортной задаче. Понятия плана (допустимого решения), оптимального плана транспортной задачи аналогичны соответствующим понятиям, что и в задачах линейного программирования. Специфический вид транспортной задачи позволяет довольно легко доказать некоторые ее свойства. Например, транспортная задача всегда имеет допустимое решение и она разрешима, т.е. для нее всегда существуют план и оптимальный план. Более того, если все и все – целые числа, то хотя бы одно ее оптимальное решение также целочисленное. Отметим, что в математической модели транспортной задачи, коэффициент при переменной может принимать одно из значений 0 или 1, т.е., матрица условий транспортной задачи состоит только из 0 и 1. Доказано, что ранг матрицы условий транспортной задачи на единицу меньше суммы числа поставщиков и потребителей. Поскольку, транспортная задача является задачей линейного программирования, то, естественно, для ее решения можно применить все методы, с помощью которых можно решать задачи линейного программирования. Условия транспортной задачи позволяют разработать специфичные методы ее решения. Отметим, что для транспортной задачи всегда можно подобрать некоторый план, используя эвристический подход. Будет ли этот план оптимальным – вопрос, требующий специального исследования. 2. Методы определения начального плана Теперь рассмотрим наиболее часто используемые методы определения начального плана транспортной задачи. Подобно другим задачам линейного программирования, процесс решения транспортной задачи начинается с определения ее начального плана. Существуют несколько методов определения начального плана транспортной задачи. Здесь, рассмотрим так называемые методы северо-западного угла и наименьших элементов. Прежде всего, условимся задавать транспортную задачу в виде таблицы 1. В этой таблице , – i- й поставщик, а , – j-й потребитель. Каждая клетка основной части этой таблицы соответствует определенной паре поставщик – потребитель, точнее, клетка, расположенная в i-м вертикальном и j-м горизонтальном ряду соответствует паре i-й поставщик - j-й потребитель. Клетка (i,j) основной части таблицы 1 содержит значение , соответствующее стоимости перевозки одной единицы продукции от i-го поставщика к j-му потребителю. Таблица 1
Задание транспортной задачи в виде таблицы удобно еще и тем, что в ее соответствующие клетки можно заносить объемы перевозок . Метод северо-западного угла. Идея этого метода заключается в следующем. Сначала определяется значение переменной , расположенной в северо-западном углу таблицы: . Если выполняется условие , то получим и положим . Если же выполняется условие , то получим и положим . Выполнение условия означает, что весь груз из в количестве доставлен потребителю . Тем самым предложение поставщика полностью удовлетворено, а спрос потребителя уменьшается на величину и становится равным . В этом случае, необходимость обращения к поставщику других потребителей, естественно, исчезает. Поэтому, поставщик исключается из рассмотрения. Выполнение же условия означает, что потребитель полностью удовлетворил свою потребность в продукции, а предложение поставщика уменьшается на величину и становится равным . В этом случае, необходимость обращения потребителя к другим поставщикам, естественно, также исчезает. Здесь, из рассмотрения исключается потребитель . Итак, после определения , предложение поставщика и спрос потребителя уменьшатся на величину , т.е. они становятся равными и соответственно. Если , то из рассмотрения можно исключить и поставщика , и потребителя . Однако, условимся считать, что в этом случае, из рассмотрения выбывает только один из них (поставщик или потребитель), а возможность второго (спрос или предложение) равна нулю. После установления объема перевозок из в , имеем дело с новой транспортной задачей, в которой суммарное число поставщиков и потребителей на единицу меньше, чем в исходной. Выполняя такие же действия, что и для определения значения переменной , можно определить значение северо-западного угла оставшейся части таблицы рассматриваемой задачи. При этом, каждый раз значения и заменяются соответственно на и и из рассмотрения исключается или поставщик , или потребитель . Эти действия продолжаются до тех пор, пока из рассмотрения на будут исключены все поставщики и потребители. Это означает, что запросы всех поставщиков и потребителей выполнены полностью. Это утверждение обусловлено наличием условия баланса. Пример 1. Определить, методом северо-западного угла, начальный план транспортной задачи, приведенной в таблице 2. Таблица 2
После проведения соответствующих вычислений получим следующую таблицу 3, основная часть которой содержит объемы перевозок груза от поставщика , к потребителю . Таблица 3
В результате получим следующий начальный план этой задачи: . Все остальные . Значение целевой функции равно: z=3290. Метод минимальных элементов. При определении начального плана транспортной задачи, методом северо-западного угла, был предусмотрен формальный подход начала выбора клетки таблицы для ее заполнения. Этой клеткой могла стать любая угловая (например, юго-западная), несмотря на то, что используемый метод называется – северо-западным. Отметим, что здесь использование такого важного показателя задачи, как стоимость перевозки одной единицы продукции вообще не учитывается. Однако, представляется вероятным, что чем больше в начальном плане дешевых перевозок, тем ближе этот план к оптимальному. Заметим, что выбор именно северо-западной клетки в каждой из последовательных частных таблиц – это лишь одно из возможных правил выбора одного из рассматриваемых маршрутов. Принципиально ничего не изменится, если будем выбирать в исходной таблице, а затем и в последовательно рассматриваемых ее частях, сначала клетку, соответствующую наиболее дешевому маршруту. При этом, как и прежде, будем вводить в клетку таблицы максимально возможную перевозку. Можно условиться выбирать минимальный элемент первой строки, или же первого столбца рассматриваемой части таблицы. Согласно метода минимальных элементов, выбор минимального элемента осуществляется среди всех значений , рассматриваемой части таблицы. Отметим, что возможны случаи, когда клеток с минимальным значением (в таблице, строке или столбце, соответственно) несколько. Поэтому необходимо заранее условиться, по какому правилу выбирается для заполнения одна из них. Например, можно условиться выбирать, в этих случаях, клетку с минимальным первым индексом, а если первые индексы совпадают, то с минимальным вторым. При использовании такого подхода определения начального плана, как и при выборе северо-западной клетки, следует исключать (об этом было изложено и выше) из рассмотрения на каждом шаге только строку (или только столбец). В этом случае, формально вводится в рассмотрение поставщик с нулевым предложением (или потребитель с нулевым спросом). Этот метод называют также методом наименьших затрат или же методом наименьших элементов. Опыт показывает, что не всегда использование метода минимальных элементов приводит к лучшему плану, по сравнению с тем, который был найден с помощью метода северо-западного угла. Задачи для самостоятельной работы Определить начальный план следующей транспортной
задачи методом минимальных затрат:
Определить начальный план следующей транспортной задачи методом минимальных затрат:
Определить начальный план следующей транспортной задачи методом минимальных затрат:
Определить начальный план следующей транспортной задачи методом потенциалов:
Определить начальный план следующей транспортной задачи методом северо-западногоугла:
Определить начальный план следующей транспортной задачи методом минимальных затрат:
Download 243 Kb. Do'stlaringiz bilan baham: 
|