Практическое занятие № 13 решение транспортной задачи
Имеется m поставщиков определенного вида продукции. Максимальные объемы возможных поставок заданы и равны соответственно ai, i=1,2,…,m. Эта продукция используется n потребителями. Объемы потребностей заданы и равны соответственно bi, j=1,2,…n. Стоимость перевозки единицы продукции от i-го поставщика к j-му потребителю известна для всех i=1,2,…,m и всех j=1,2,…n и равна сij. Требуется установить такие объемы перевозок хij от каждого поставщика к каждому потребителю, чтобы суммарные затраты на перевозки были минимальными и потребности всех потребителей были бы удовлетворены (если только общий объем возможных поставок покрывает общий объем возможных потребителей).
Математическая модель этой задачи такова:
Очевидно, что эта задача линейного программирования с mn переменными и m+n непрямыми ограничениями.
В литературе описан ряд классических транспортных задачи методов их решения. І
1. Задача о ранце. Здесь речь идет о собравшмся в поход путешественнике, который должен кпаковать в ранец различные полезные предметы n наименований, причем может потребоваться несколько одинаковых предметов. Имеется m ограничений такого типа, как вес, объем, линейные размеры и т.д. При формулировке задачи место ранца может занять бомбардировщик, трюм или палуба корабля, складское помещение и т.д.
2. Задача о назначениях. Имеется n различных транспортных средств, которые требуется распределить между m маршрутами. Известно, что на j-м маршрутами i-е транспортное средство будет приносить доход сij. Требуется так распределить транспортные средства, чтобы максимилизировать суммарный доход.
3. Задача о коммивояжере. Имеются города, пронумерованные числами 0, 1, 2, …, n. Выехав из города 0, коммивояжер должен объехать все остальные города, побывав в каждом из них по одному разу, и вернуться в исходный город. Известны расстояние сij между городами i и j (i,j = 0, 1, 2, …, n). Требуется найти самый короткий маршрут.
4. Задача о четырех красках. В 1976 г. была доказана замечательная теорема: любую географическую карту можно раскрасить, используя не более четырех различных красок. Тем самым была решена одна из наиболее знаменитых и старых математических проблем. Показательно, что обоснование этого результата проделано с помощью ЭВМ: после теоретических рассуждений осталось большое, но конечное число карт, относительно которых не было известно лишь то, можно ли их раскрасить четырьмя красками. С помощью ЭВМ был получен положительный ответ, который и дал окончательное решение проблемы.
Уточним формулировку задачи. Дана плоская географическая карта, на которой граница каждой страны представляет собой замкнутую непрерывную кривую. Две страны называются соседними, если у них есть общая граница – участок кривой определенной длины. Требуется так раскрасить данную карту в четыре цвета, чтобы соседние страны были раскрашены в разные цвета.
Задача о назначениях или задача выбора
Пусть имеется n видов работ и n претендентов (рабочих, механизмов и др.) для их выполнения, причем каждый претендент может использоваться на любой работе. Известна производительность i – го претендента на j – й работе (сij). Требуется так распределить претендентов по работам, чтобы суммарная производительность была максимальной. При этом каждого претендента можно назначить только на одну работу и на каждую работу можно назначить только одного претендента.
Построим математическую модель этой задачи. Введем переменные:
