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

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

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

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

; и

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

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. На трех хлебокомбинатах ежедневно производится 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 вид можно передавать от одного предприятия другому.