Лабораторная работа №4
Транспортные модели
Цель работы: научиться находить оптимальное решениезадач транспортного типа.
Задание
Вариант 1. На четырех ткацких станках с объемом рабочеговремени 200, 300, 250 и 400 станко-ч за 1 час можно изготовить соответственно 260,200, 340 и 500 м ткани трех артикулов I, II, III. Составить оптимальную программу загрузки станков, еслиприбыль (в ден. ед.) от реализации 1 м ткани i-го артикула при ее изготовлении на j-м станке характеризуется элементами матрицы
/>,
а суммарная потребность вткани каждого из артикулов равна 200, 100 и 150 тыс. м, учитывая, что ткань I артикула не может производиться на третьем станке.
Табличная модель:
/>
Контрольные вопросы:
1. Как записывается математическаямодель задачи транспортного типа?
Обозначим через xij объем перевозок от i-го поставщика j-ому потребителю. Математическая модельзадачи имеет вид:
1) объем поставок i-го поставщика должен равняться количествуимеющегося у него груза
/>;
2) объем поставок j-ому потребителю должен быть равен егоспросу
/>;
3) объемы поставок должны выражаться неотрицательнымичислами
xij ³ 0; />, />;
4) общая сумма затрат на перевозку грузадолжна быть минимальной
/>.
Если суммарный объем отправляемыхгрузов равен суммарному объему потребностей в этих грузах по пунктам назначения
/>,
то такая транспортная задачаназывается закрытой (сбалансированной), в противном случае — открытой (несбалансированной).
Если указанные затраты неизвестны(не указаны) соответствующие значения сij полагают равными нулю.
модельпоставка потребность затрата
2. Как свести открытуютранспортную задачу к закрытой?
Если имеет место открытаятранспортная задача, ее необходимо свести к закрытой:
1) в случае перепроизводства– ввести фиктивного потребителя с необходимым объемом потребления (элементы матрицысij, связывающие фиктивные пункты с реальными,имеют значения, равные затратам на хранение невывезенных грузов);
2) в случае дефицита – ввестификтивного поставщика с недостающим объемом отправляемых грузов (элементы матрицысij, связывающие фиктивные пункты с реальными,имеют значения, равные штрафам за недопоставку продукции).
3. Каковы основные ситуации,описывающие дополнительные ограничения транспортной задачи?
При решении практических задачзачастую приходится учитывать ряд дополнительных ограничений.
1. Отдельные поставки от определенныхпоставщиков некоторым потребителям должны быть исключены (из-за отсутствия необходимыхусловий хранения, чрезмерной перегрузки коммуникаций и т.д.). Это достигается искусственнымзначительным завышением затрат на перевозки сij в клетках, перевозки через которые следует запретить.
2. На предприятии необходимо определитьминимальные суммарные затраты на производство и транспортировку продукции. С подобнойзадачей сталкиваются при решении вопросов, связанных с оптимальным размещением производственныхобъектов. Здесь может оказаться экономически более выгодным доставлять сырье изболее отдаленных пунктов, но зато при меньшей его себестоимости. В таких задачахза критерий оптимальности принимают сумму затрат на производство и транспортировкупродукции.
3. Ряд транспортных маршрутов,по которым необходимо доставить грузы, имеют ограничения по пропускной способности.Если, например, по маршруту AiBj можно провести не более q единиц груза, то Bj-й столбец матрицы разбивается на два столбца – /> и/>. В первом столбце спрос принимаетсяравным />, во втором – />.Несмотря на то, что фактические затраты сij в обоих столбцах одинаковы и равны исходным, в столбце /> вместоистинного тарифа сij ставитсяискусственно завышенный тариф М (клетка блокируется). Затем задача решается обычнымспособом.
4. Поставки по определенныммаршрутам обязательны и должны войти в оптимальный план независимо от того, выгодноэто или нет. В этом случае уменьшают запас груза у поставщиков и спрос потребителейи решают задачу относительно тех поставок, которые необязательны. Полученное решениекорректируют с учетом обязательных поставок.
5. Необходимо максимизироватьцелевую функцию задачи транспортного типа (например, задача об оптимальном распределенииоборудования). В этом случае необходимо изменить знак в тарифах на противоположный.В ответе отрицательный знак игнорируется.
Вывод: я научилась находить оптимальное решениезадач транспортного типа.