Метод потенциалов

Занятие № 6

Тема «Построение оптимального плана перевозок»

Цель образования: Изучение распределительного метода и метода потенциалов для построения оптимального плана перевозок

Цель развития: Развитие логического мышления

Цель воспитания: Воспитание интереса к предмету, к экономическим процессам.

Решить транспортные задачи по составлению оптимального плана перевозок.

Задача № 1.

В трёх пунктах отправления А, В и С находятся соответственно 22, 18 и 15 тонн горючего. В пункты 1, 2, 3 требуется доставить соответственно 16, 26 и 12 тонн горючего. Стоимость перевозки тонны горючего из пункта А в пункты 1, 2, 3 составляют соответственно 7, 4, и 2 ден. ед., из пункта В – 1, 3, 5 ден ед., а из пункта С – 6, 9, 8 ден ед. Составьте оптимальный план перевозок горючего так, чтобы общая сумма транспортных расходов была наименьшей. Опорный план составить методом минимального элемента в таблице.

Задача № 2.

На трёх складах А, В, С находится сортовое зерно соответственно 16, 10 и 8 тонн, которое надо доставить в три пункта: пункту № 1 - 12 тонн, пункту № 2 – 8 тонн, пункту № 3 – 14 тонн. Стоимость доставки одной тонны зерна со склада А в указанные пункты соответственно равна 7, 1, 2 ден. ед., со склада В - 3, 8, 6 ден. ед., а со склада С – 4, 9, 5 ден. ед. Составить оптимальный план перевозки зерна в три пункта, минимизирующий стоимость перевозки.

Опорный план составить методом «северо – западного угла».

Задача № 3.

Завод имеет четыре цеха А, В, С и Д и три склада: №1, №2, №3. Цех А производит 54 тыс. штук изделий, цех В – 26 тыс. штук изделий, цех С -72 тыс. шт., цех Д – 12 тыс. шт. Пропускная способность складов за то же время характеризуется следующими показателями: склад № 1 – 64 тыс. шт., склад № 2 – 56 тыс. шт., склад № 3 – 44 тыс. шт. изделий. Стоимость перевозки 1 тыс. шт. изделий из цеха А в склады № 1, 2, 3 соответственно равны 2, 4, 8 ден. ед; из цеха В – 5, 7, 3 ден. ед.; из цеха С – 12, 1, 6 ден. ед.; из цеха Д – 9, 4, 14 ден. ед. Составить такой план перевозки изделий, при котором расходы на перевозку 164 тысяч штук изделий были бы наименьшими.

Опорный план составить методом минимального элемента в таблице.

Метод потенциалов.

Имея опорный план перевозок, в методе потенциалов выполняют анализ клеток матрицы плана перевозок. Все заполненные клетки матрицы перевозок называются базисными, все незаполненные клетки – свободными. Для каждой свободной клетки, аналогично распределительному методу, можно построить замкнутый контур и перераспределить ресурсы между поставщиками и потребителями. Отличие этого метода состоит в том, что определяется потенциал каждой клетки и, в зависимости от значения этого потенциала, выполняется перемещение только по одному контуру.

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

u_i + v_j = c_ij,

подставляя в неё значения из базисных клеток. Для начала выполнения расчётов надо потенциал одной строки или одного столбца приравнять к нулю. Затем, используя указанную формулу, выполнить остальные вычисления. Для свободных клеток вычисляются оценки по формуле:

u_i + v_j - c_ij

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

Метод потенциалов предоставляет сведения, имеет ли транспортная задача альтернативные оптимальные планы перевозок.

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

1.

2.

3.