Вырожденные случаи. Открытая транспортная задача.

Некоторые замечания по частным случаям, которые могут встретиться при решении.

1. Если на некотором шаге построения базисного плана из рассмотрения выпадают одновременно и строка и столбец (случай вырождения), можно использовать следующий прием: дать нулевую (фиктивную) поставку в произвольную еще не занятую клетку данной строки или столбца. (Тем самым сохраняется число занятых клеток m+n–1 для базисного распределения поставок).

2. Если в отрицательных вершинах цикла, по которому перераспределяется поставка, две или более минимальных поставок, то все они при перераспределении обратятся в нуль. Так как на каждом шаге число занятых клеток сохраняется в количестве m+n–1, то из этих “нулевых” клеток образуется только одна пустая клетка, а остальные считаются заполненными поставкой равной 0.

3. Если мы нашли клетку с отрицательной оценкой и построили соответствующий цикл перераспределения, в одной из отрицательных вершин которого находится нулевая поставка, то следует переместить эту нулевую поставку (значение целевой функции при этом не изменится), а затем вновь определять оценки пустых клеток в полученном базисном плане.

Рассмотрим некоторые моменты, имеющие практическое значение, но усложняющие постановку транспортной задачи:

1. Обязательные поставки.

Независимо от оптимальных расчетов некоторому поставщику вменяется определенный объем поставки некоторому потребителю (например, определенная марка бетона производится только на таком-то заводе, а некоторому потребителю необходимо определенное количество данной марки). В этом случае на величину обязательных поставок корректируются мощности и потребности, и после этого решается задача.

2. Ограничения пропускной способности.

Ранее мы исходили из того, что от любого поставщика любому потребителю можно перевозить любое количество продукта (в пределах мощности и спроса). В реальных задачах часто приходится учитывать пропускную способность коммуникаций (особенно железных дорог).

Самый простой способ учитывать пропускную способность состоит в следующем:

Пусть поставка в клетку (i, j) ограничена числом, строго меньшим В_j. Столбец j, соответствующий потребителю с ограниченной пропускной способностью, разбивается на два столбца, в одном спрос принимается равным ограничению, а в другом – остатку. Показатели транспортных затрат одинаковы для этих двух столбцов за исключением клетки (i, j) в столбце, где спрос равен разности (остатку). Здесь с_ijпринимается очень большим, блокирующим какую-либо поставку в эту клетку.

До сих пор мы рассматривали закрытую транспортную задачу, т.е. при условии баланса спроса и объемов производства (мощностей). В практических задачах это условие далеко не всегда выполняется. При нарушении баланса возникает открытая транспортная задача, которая решается сведением ее к закрытой транспортной задаче.

При превышении суммарной мощности над суммарным спросом на величину D вводится дополнительный столбец так называемого фиктивного потребителя со спросом равным D. Показатели с_in+1(i=1, 2, …, m) в этом столбце выбираются произвольно, но с одним условием, что все они равны между собой. Удобнее всего принимать их равными 0. Далее задача решается как закрытая.

Аналогично, при превышении суммарного спроса над суммарной мощностью на величину D вводится дополнительная строка так называемого фиктивного поставщика с мощностью равной D и с нулевыми транспортными издержками.

Практический блок

Пример

Экономическая модель

– это наличие товара у поставщика и ;

– это наличие потребностей у потребителя и ;

– это удельные затраты на перевозку товара от каждого -го поставщика, каждому -ому потребителю.

Математическая модель.

Определим неизвестные. За примем количество перевозимой продукции от каждого -го поставщика, каждому -ому потребителю.

– вывезти товара, не менее, чем есть;

– привезти не менее запросов потребителя.

; и

Получили, что суммарный спрос равен суммарному предложению, значит данная транспортная задача является закрытого типа.

2. Получение начального (опорного) плана методом северо-западного угла

Поверим по формуле, получился ли вырожденный случай:

; (невырожденный случай).

Определим начальные (опорные) издержки:

;

3. Итерации по улучшению плана до получения оптимального решения.

Рассчитаем оценки пустых клеток:

; ; ;

Минимальная оценка в клетке (1, 3). Сделаем перепоставку по контуру (23 из клетки 3, 3 в клетку 1, 3) и получим новый план поставки товара.

План после первой итерации

Снова рассчитаем оценки пустых клеток:

; ; ;

; .

Минимальная оценка в клетке (5, 1). Сделаем перепоставку по контуру – это будет число 31 из клетки (1, 1). Рассчитаем новый план поставки товара.

План после второй итерации

Снова рассчитаем оценки пустых клеток:

; ; ;

; ; .

Выбираем клетку (2, 4). Сделаем перепоставку по контуру – это будет число 38 из клетки (2, 1). Рассчитаем новый план поставки товара.

План после третьей итерации

Снова рассчитаем оценки пустых клеток:

; ; ;

; ; .

Выбираем клетку (3, 3). Сделаем перепоставку по контуру – это будет число 15 из клетки (5, 3). Рассчитаем новый план поставки товара.

План после четвертой итерации

Снова рассчитаем оценки пустых клеток:

; ; ;

Выбираем клетку (3, 4). Сделаем перепоставку по контуру – это будет число 12 из клетки (5, 4). Рассчитаем новый план поставки товара.

План после пятой итерации

Снова рассчитаем оценки пустых клеток:

; ; ;

; ; .

Выбираем клетку (4, 1). Сделаем перепоставку по контуру – это будет число 4 из клетки (3, 1). Рассчитаем новый план поставки товара.

План после шестой итерации (оптимальный план перевозок)

Снова рассчитаем оценки пустых клеток:

; ; ;

; ; .

Как видно из расчетов все оценки положительные, т.е. не уменьшают издержки. Выбран оптимальный план перевозок .

Контрольные вопросы

1. Транспортная задача: постановка.

2. Транспортная задача: экономическая значимость.

3. Транспортная задача: условия существования решения.

4. Отличие транспортной задачи от общей задачи линейного программирования.

5. Как найти начальное решение транспортной задачи методом северо-западного угла?

6. Как решается транспортная задача методом минимальной стоимости?

7. Как решается транспортная задача методом потенциалов?

8. Построение замкнутого контура (цикла) при решении транспортной задачи.

9. Открытая и закрытая транспортная задача.

10. Приведение открытой транспортной задачи к закрытому типу.

Тесты

1. Что требуется определить в транспортной задаче?

а) такой план перевозок, чтобы все заявки не были выполнены, а общая стоимость всех перевозок была бы минимальна;

б) такой план перевозок, чтобы все заявки были выполнены, а общая стоимость всех перевозок была бы минимальна;

в) такой план перевозок, чтобы все заявки были выполнены, а общая стоимость всех перевозок была бы максимальна;

г) такой план перевозок, чтобы все заявки были не выполнены, а общая стоимость всех перевозок была бы максимальна;

д) содержание п. а и г.

2. Транспортные задачи являются одним из видов задач:

а) линейного программирования;

б) нелинейной оптимизации;

в) динамического программирования;

г) теории игр.

3. Система ограничений в транспортной задаче включает в себя:

а) уравнения баланса по поставщикам;

б) уравнения баланса по потребителям;

в) суммарное время перевозок;

г) п.п. а, б;

д) п.п. а-в.

4. Целевой функцией в транспортной задаче является:

а) суммарные транспортные издержки;

б) суммарное время перевозок;

в) длина маршрута перевозок.

5. Оценка пустой клетки показывает:

а) на сколько изменится значение целевой функции, после совершения единичной поставки в рассматриваемую клетку;

б) максимально возможную поставку в рассматриваемую клетку;

в) стоимость перевозки единицы товара.

6. Как решается транспортная задача:

а) методом потенциалов;

б) методом обратной матрицы;

в) методом «северо-западного угла».

7. Транспортная задача может быть

а) замкнутая;

б) закрытая;

в) обособленная.

8. Для нахождения опорного плана транспортной задачи применяется

а) метод скользящей средней;

б) метод потенциалов;

в) метод «северо-западного угла».

9. Сколько занятых клеток в транспортной таблице соответствует опорному плану перевозок:

а) n+m; б) n+m – 1; в) n+m+1.

10. Всегда ли для пустой клетки транспортной таблицы существует контур перепоставки?

а) да;

б) нет;

в) при соблюдении определенных условий.

Ответы к тестам

1) б	6) а
2) а	7) б
3) г	8) в
4) а	9) б
5) а	10) а

Задания и задачи

Задача 1. На трех хлебокомбинатах ежедневно производится 110, 190 и 90т муки. Эта мука потребляется четырьмя хлебозаводами, ежедневные потребности которых равны соответственно 80, 60, 170 и 80т. Тарифы перевозок 1т муки с хлебокомбинатов к каждому из хлебозаводов задаются матрицей:

Составить такой план доставки муки, при котором общая стоимость перевозок является минимальной.

Задача 2. В трех хранилищах горючего ежедневно хранится 175, 125 и 140т бензина. Этот бензин ежедневно получают четыре заправочных станции в количествах, равных соответственно 180, 110, 60 и 40 т. Тарифы перевозок 1т бензина с хранилищ к заправочным станциям задаются матрицей:

Составить такой план перевозок бензина, при котором общая стоимость перевозок является минимальной.

Задача 3. В пунктах А и В находятся соответственно 100 и 180 т горючего. Пунктам 1, 2 и 3 требуется соответственно 60, 80 и 140 т горючего. Стоимость перевозки 1 т горючего из пункта А в пункты 1, 2, 3 равна 100, 200 и 200 руб., а из пункта В в пункты 1, 2, 3 – 500, 200 и 400 руб. за 1т. соответственно. Составить план перевозок горючего, минимизирующий общую сумму транспортных расходов.

Задача 4. Из трех холодильников, вмещающих мороженную рыбу в количествах 320т, 280т, 250т, необходимо ее доставить в пять магазинов в количествах 140т, 150т, 110, 230т, 220т. Стоимости перевозки 1т рыбы из холодильника i в магазин j заданы в виде матрицы С={c_ij} размерностью 3x5. Написать математическую модель задачи и спланировать перевозки так, чтобы их общая стоимость была минимальной.

20 23 20 15 24

С = 29 15 16 19 29

6 11 10 9 8

Задача 5. Автомобильная компания MG Auto имеет три завода в Лос-Анджелесе, Детройте и Новом Орлеане и два распределительных центра в Денвере и Майами. Объемы производства заводов компании в следующем квартале составят соответственно 1000, 1500 и 1200 автомобилей. Ежеквартальная потребность распределительных центров составляет 2300 и 1400 автомобилей. Расстояния (в милях) между заводами и распределительными центрами приведены в таблице:

Таблица

Денвер Майами

Лос-Анджелес
Детройт
Новый Орпеан

Транспортная компания оценивает свои услуги в 8 центов за перевозку одного автомобиля на расстояние в одну милю. Составить план перевозок автомобилей, минимизирующий общую сумму транспортных расходов.

Задача 6. В рамках задачи 5 предположим, что завод в Детройте уменьшил выпуск продукции до 1300 автомобилей (вместо 1500, как было ранее). В этом случае общее количество произведенных автомобилей (3500) меньше общего числа заказанных (3700). Таким образом, очевидно, что часть заказов распределительных центров Денвера и Майами не будет выполнена. Составить план перевозок автомобилей, минимизирующий общую сумму транспортных расходов.

Задача 7. На четырёх ткацких станках с объёмом рабочего времени 200, 300, 250 и 400 станко-часов может изготавливаться ткань трёх артикулов в количествах 260, 200, 340 и 500 метров за 1 час. Составить модель формирования плана загрузки станков, если прибыль (в руб.) от реализации 1 м ткани i-го артикула при её изготовлении на k-м станке характеризуется элементами матрицы:

С=

а суммарная потребность в ткани каждого из артикулов равна оответственно

200, 100 и 150 тыс. м.

Задача 8. Четыре ремонтные мастерские могут за год отремонтировать соответственно 700, 500, 450 и 550 машин при себестоимости ремонта одной машины в 50, 70, 65 и 60 руб. Планируется годовая потребность в ремонте пяти автобаз: 350, 350, 300 и 200 машин. Избыточные мощности 1-й и 2-й мастерских могут быть использованы для обслуживания других видов работ, в 3-й и 4-й мастерских – только на указанный вид работ. Матрица

40 10 70 50

20 80 30 10

C= 60 30 30 40

10 40 50 50

20 30 10 40

характеризует транспортные расходы на доставку машины с i-й автобазы на

k-тую ремонтную мастерскую. Определить минимальную годовую потребность в кредитах на выполнение указанного объёма ремонтных работ по всем автобазам.

Задача 9. Четыре различных предприятия могут выпускать любой из четырёх видов продукции. Производственные мощности предприятий позволяют обеспечить выпуск продукции каждого вида в количествах (по заводам): 50, 70, 100 и 30 тыс. штук, а плановое задание составляет соответственно (по видам продукции) 30, 80, 20 и 100 тыс. шт. Матрица

4 5 9 8

7 5 9 4

C= 4 6 8 6

6 8 7 5

характеризует себестоимость единицы k-го вида продукции при производстве его на i-м предприятии. Найти оптимальное распределение планового задания между предприятиями.

Задача 10. Имеется три предприятия (1, 2, 3), которые могут выпускать три вида продукции: А, Б, В. Каждое из них располагает двумя видами ресурсов (I, II), объёмы которых составляют для 1-го предприятия 250 и 150 единиц, для 2-го 100 и 200 единиц и для 3-го соответственно 240 и 300 единиц. Известны: нормы затрат каждого ресурса на i-м предприятии для производства единицы k-й продукции (k = 1, 2, 3); себестоимость производства единицы k-й продукции на i-м предприятии; объём производства k-й продукции, предусмотренный производственной программой.

Все указанные числовые данные приведены в следующей таблице:

Предпри- ятия	Продукция А	Продукция Б	Продукция В
Нормы затрат	себесто- имость	Нормы затрат	себесто- имость	Нормы затрат	себесто- имость
I	II	I	II	I	II
				1, 1		2, 5
	1, 5			1, 6		2, 2	2, 5
	2, 2		2, 5	1, 2	2, 4	2, 4	4, 2
Программа выпуска

Составить математическую модель для определения оптимальной специализации производства из условия минимизации суммарной себестоимости. Решить ту же задачу из предположения, что I вид ресурсов жёстко закреплён за предприятием, а II вид можно передавать от одного предприятия другому.

2.3.7. Самостоятельная работа студентов

⇐ Предыдущая 6 7 8 9 10 11 12 13 1415