ТРАНСПОРТНАЯ ЗАДАЧА

Для решения задачи 3.2 необходимо изучить следующую литературу:

[1] Раздел D. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, глава 6, стр. 597…637.

[3] Раздел 1. МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ЕГО ПРИЛОЖЕНИЯ, глава 7, стр. 123…152.

[4] Глава 3. Транспортная задача, стр. 43…55.

Учебно-методическая литература

[4] Главы 1, 2, стр. 5…37.

Задача3.2. Найти оптимальный план перевозок товара с двух баз: A₁ и A₂ в три магазина: B₁, B₂, B₃. Запасы на базах, потребности магазинов, а также тарифы на перевозку товаров между базами и магазинами даны в таблице (справа та же таблица, но без заголовков).

Требуется найти план с минимальной общей стоимостью перевозок товара:

Z = 3 x ₁₁ + 2 x ₁₂ + x ₁₃ +5 x ₂₁ + 3 x ₂₂ +6 x ₂₃ (min).

Суммарные запасы на базах 90(ед.) и потребности магазинов 90(ед.) равны, следовательно задача является закрытой.

Введём обозначения:

c_ij - тариф на перевозку единицы товара с базы A_i в магазин B_j;

m - число баз (строк таблицы);

n - число магазинов (столбцов);

p - число занятых клеток в таблице.

Заполняем клетки методом наименьшего тарифа:

min c_ij= c₁₃= 1; Þ x ₁₃= min{50; 40} = 40;

записываем 40 в клетку (1; 3); третий столбец вычёркиваем, т.к. потребности B₃ удовлетворены; запасы на складе A₁ уменьшились до 10(ед.).

Далее ищем наименьший тариф среди не вычеркнутых клеток: min c_ij= c₁₂= c₂₁= 2. Заполним клетку (1, 2): x ₁₂= min{10; 20} = 10. Первую строку вычёркиваем, т.к. запасы на складе A₁ исчерпаны; потребности B₂ уменьшились до 10(ед.).

Остались не вычеркнутыми клетки только одного ряда – второй строки, которые заполняются однозначно в любом порядке: x ₂₁ = 30; x ₂₂ = 10.

Первый план: X₁ = .

Стоимость перевозок по этому плану:

Z ₁ = 2×10 + 1× 40 + 5×30 + 3×10 = 240.

Проверим условие опорности плана: p = r, где r = m + n –1 - ранг системы уравнений. Заполненных клеток – четыре, т.е. р = 4; ранг:

r = 3 + 2 –1 = 4.

p = r = 4; Þ план опорный!

Проверка оптимальности плана методом потенциалов.

Пусть u_i - потенциалы строк, v_j - потенциалы столбцов (смотри последнюю таблицу). Для всех занятых клеток должно выполняться условие:

u_i + v_j = c_ij (1)

Для всех свободных клеток должно выполняться условие:

y_ij = c_ij - (u_i + v_j) ³ 0. (2)

Здесь y_ij - оценки клеток (двойственные переменные).

По формуле (1) составим систему уравнений для нахождения потенциалов:

; Пусть u₁= 0; Þ (v₂= 2; v₃= 1;) Þ (u₂= 3 - v₂= 1;) Þ

Þ(v₁= 5 - u₂= 4;)

По формуле (2) оценим свободные клетки:

y₁₁= c₁₁- (u₁+ v₁) = 3 – (0 + 4) = -1 < 0;

y₂₃= c₂₃- (u₂+ v₃) = 6 – (1 + 1) = 4 > 0;

Полученный план не оптимален, т.к. оценка y₁₁отрицательна. Эту пустую клетку (1, 1) следует заполнить, не нарушая баланса по рядам и сохраняя количество заполненных клеток. Такой переход к другому опорному плану возможен только по циклу (цикл существует и единственный!): + (1, 1) – (2, 1) + (2, 2) – (1, 2).

D = min(x ₂₁, x ₁₂) = min(30, 10) = 10.

Подставив D в предыдущую таблицу, получим новую:

y₁₁×D = (-1)×10 = -10; Þ Z ₂ = Z ₁ -10 = 240 -10 = 230.

Ответ.

Стоимость перевозок согласно плану X = будет наименьшей и составит 230(д.е.). При этом потребности магазинов будут полностью удовлетворены и товарные запасы с баз полностью вывезены.

Литература

Основная

1. Общий курс высшей математики для экономистов [Текст]: Учебник /под ред. В.И. Ермакова – М.: ИНФРА–М, 2007. – 656с.

2. Гмурман, В.Е. Теория вероятностей и математическая статистика [Текст]: учеб. пособие для вузов / В.Е. Гмурман. - 10-е изд., стер. – М.: Высш. шк., 2004. – 480 с.

3. Исследование операций в экономике [Текст]: учебн. пособие для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; под ред. Н.Ш. Кремера – М.: Банки и биржи, 1999. – 407с.

4. Дыхнов, А.Е. Математическое программирование [Текст]: учеб. пособие / Дыхнов А.Е., Тумашев В.И., Авдонькина А.В.; Челяб. ин-т (фил) ГОУ ВПО "РГТЭУ". - Челябинск, 2004. – 91 с.

Дополнительная

5. Сборник задач по высшей математике для экономистов [Текст]: Учебн. пособие /под ред. В.И. Ермакова – М.: ИНФРА – М., 2002. - 575с.

6. Кремер, Н.Ш. Теория вероятностей и математическая статистика: учеб. для вузов / Н.Ш. Кремер – М.: ЮНИТИ-ДАНА, 2003. – 543 с. (имеется электронный вариант)

7. Колемаев, В.А. Теория вероятности и математическая статистика [Текст]: Учеб. / В.А. Колемаев, В.Н. Калинина., под ред. В.А. Колемаева. – 2-е изд., перераб. и доп. – М.: ЮНИТИ, 2003. – 352с.

8. Лабскер, Л.Г. Теория массового обслуживания в экономической сфере [Текст]: Учеб. пособие для вузов /Л.Г. Лабскер, Л.О. Бабешко. – М.: Банки и биржи, 1998. – 319с.

9. Справочник по математике для экономистов [Текст] / В.Е. Барбаумов, В.И. Ермаков, Н.Н. Кривенцова и др.; под ред. В.И. Ермакова – 2-е изд., перераб. и доп. – М.: Высш. шк., 1997. – 384с.

10. Зайцев, М.В. Высшая математика: Сб. задач. Ч.2/ М.В. Зайцев, Т.А. Лавриненко, А.А. Туганбаев; РГТЭУ. – М., 2003. – 59 с.

11. Зайцев, М.В. Прикладная математика: Сб. задач. Ч. 2/ М.В. Зайцев, А.А. Беляев, Г.П. Фомин; РГТЭУ. – М.; 2003. – 46с.

12. Прикладная математика: Ч.2: Метод. указания и задания для контрольной работы №2 для студентов заоч. формы обучения всех спец. и направлений / РГТЭУ; Сост. В.П. Фомин, А.А. Беляев. – М., 2004. – 34с.

Поиск по сайту: