Атомная энергетика России Инженерная графика и машиностроительное черчение Математика Курс лекций и примеры решения задач Информатика Электротехника Физика курс лекций примеры решения задач
Аппарат дифференциальных уравнений в экономике Элементы линейного программирования

Элементы программирования в экономике

Транспортная задача

Общая постановка задачи

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

В общем виде задачу можно представить следующим образом: в т. пунктах производства A1, A2, ..., Am имеется однородный груз в количестве соответственно a1, a2,…, am. Этот груз необходимо доставить в п пунктов назначения B1, В2, …., Вп в количестве соответственно b1, b2,..., bп. Стоимость перевозки единицы груза (тариф) из пункта Ai в пункт Bj равна cij.

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

Закон Фарадея Электродвижущая сила наведенная в замкнутом контуре C, равна скорости изменения магнитного потока, проходящего через данный контур

 

В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нем транспортные задачи могут быть закрытыми и открытыми.

Определение 1. Если

то задача называется закрытой. Если

то открытой.

Обозначим через xij количество груза, перевозимого из пункта Ai в пункт Bj. Рассмотрим закрытую транспортную задачу. Ее условия запишем в распределительную таблицу, которую будем использовать для нахождения решения (табл. 23.1).

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

при ограничениях:

Оптимальным решением задачи является матрица

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

— нахождение исходного опорного решения;

— проверка этого решения на оптимальность;

переход от одного опорного решения к другому.

Рассмотрим каждый из этих этапов.

Нахождение исходного опорного решения

Условия задачи и ее исходное опорное решение будем записывать в распределительную таблицу. Клетки, в которые поместим грузы, называются занятыми, им соответствуют базисные переменные опорного решения. Остальные клетки незанятые, или пустые, им соответствуют свободные переменные. В верхнем правом углу каждой клетки будем записывать тарифы. Существует несколько способов нахождения исходного опорного решения.

Рассмотрим один из них — метод минимального тарифа (элемента). Согласно этому методу, грузы распределяются в первую очередь в те клетки, в которых находится минимальный тариф перевозок cij. Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учетом оставшихся запасов у поставщиков и удовлетворения спроса потребителей. Процесс распределения продолжают до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены. При распределении грузов может оказаться, что количество занятых клеток меньше, чем т + п - 1. В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми.

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

Рассмотрим нахождение исходного опорного решения транспортной задачи на конкретном примере.

Определение эффективного варианта доставки изделий к потребителю

На складах A1, А2, А3 имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители В1, В2, B3 должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей (усл. ед.)

Проверим, является ли данная транспортная задача закрытой:

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

Число занятых клеток в табл. 23.2 равно т + п - 1 = 3 + 3 – 1 = 5, т.е. условие невырожденности выполнено. Получили исходное опорное решение, которое запишем в виде матрицы:

Стоимость перевозки при исходном опорном решении составляет

 

Проверка найденного опорного решения на оптимальность

Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система т + п действительных чисел ui и vj, удовлетворяющих условиям ui + vj = cij для занятых клеток и ui + vj - сij ≤ 0 для свободных клеток.

Числа ui и vj называют потенциалами. В распределительную таблицу добавляют строку vj и столбец ui.

Потенциалы ui и vj находят из равенства ui + vj = cij, справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например и1 = 0, тогда остальные потенциалы определяются однозначно. Так, если известен потенциал ui, то vj = сij — ui; если известен потенциал vj, то ui = cij – vj.

Обозначим Δij = ui + vj - cij. Эту оценку называют оценкой свободных клеток. Если Δij ≤ 0, то опорное решение является оптимальным. Если хотя бы одна из оценок Δij > 0, то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому.

Проверим найденное опорное решение на оптимальность, добавив в распределительную табл. 23.3 столбец ui и строку vj.

Полагая u1 = 0, запишем это значение в последнем столбце таблицы.

Рассмотрим занятую клетку первой строки, которая расположена в первом столбце (1,1), для нее выполняется условие и1 + v1 = 2, откуда v1 = 2. Это значение запишем в последней строке таблицы. Далее надо рассматривать ту из занятых клеток таблицы, для которой один из потенциалов известен.

Рассмотрим занятую клетку (3,1): и3 + v1 = 3, v1 = 2, откуда и3 = 1.

Для клетки (3,3): и3 + v3 = 8, и3 = 1, v3 = 7.

Для клетки (2,3): и2 + v3 = 5, v3 = 7, и2 = -2.

Для клетки (2,2): u2 + v2 = 1, и2 = -2, v2 = 3.

Найденные значения потенциалов заносим в таблицу.

Вычисляем оценки свободных клеток:

Получили одну оценку Δ13 = 5 > 0, следовательно, исходное опорное решение не является оптимальным и его можно улучшить.

Переход от одного опорного решения к другому

Наличие положительной оценки свободной клетки (Δij > 0) при проверке опорного решения на оптимальность свидетельствует о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому опорному решению. При этом надо перераспределить грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а одна из ранее занятых клеток — свободной.

Для свободной клетки с Δij > 0 строится цикл (цепь, многоугольник), все вершины которого кроме одной находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (—) и (+). У вершин со знаком (—) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (—). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т.д. до тех пор, пока не получим оптимальное решение.

Рассмотрим переход от одного опорного решения к другому на заданном примере.

Строим цикл для клетки (1,3), имеющей положительную оценку. У вершин цикла ставим знаки (+) и (—) и записываем грузы:

У вершин со знаком (—) выбираем минимальный груз, он равен 60. Его прибавляем к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у отрицательных вершин. Получаем новый цикл:

Новое опорное решение:

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

Имеем

Построим цикл для клетки с положительной оценкой Δ21 = 1:

Произведем перераспределение грузов:

Получим новое решение, которое занесем в табл. 23.5. Проверим его на оптимальность.

Получим

Все оценки свободных клеток отрицательные, следовательно, найденное решение оптимальное. Итак,

Стоимость транспортных расходов равна

По сравнению с исходным опорным решением транспортные расходы уменьшились на 1610 — 1280 = 330 усл. ед.

Наклонные асимптоты.

 Предположим, что кривая y = f(x) имеет наклонную асимптоту y = kx + b.

 Обозначим точку пересечения кривой и перпендикуляра к асимптоте – М, Р – точка пересечения этого перпендикуляра с асимптотой. Угол между асимптотой и осью Ох обозначим j. Перпендикуляр МQ к оси Ох пересекает асимптоту в точке N.

  Тогда MQ = y – ордината точки кривой, NQ =  - ордината точки N на асимптоте.

  По условию: ÐNMP = j.

Угол j - постоянный и не равный 900, тогда

Тогда  .

Итак, прямая y = kx + b – асимптота кривой. Для точного определения этой прямой необходимо найти способ вычисления коэффициентов k и b.

 В полученном выражении выносим за скобки х:

Т.к. х®¥, то , т.к. b = const, то .

Тогда ,  следовательно, 

.

Т.к. , то , следовательно,

  Отметим, что горизонтальные асимптоты являются частным случаем наклонных асимптот при k =0.

При замене переменной в определенном интеграле следует помнить о том, что вводимая функция (в рассмотренном примере это функция sin) должна быть непрерывна на отрезке интегрирования. В противном случае формальное применение формулы приводит к абсурду. Т.е. два способа нахождения интеграла дают различные результаты. Это произошло из-за того, что не был учтен тот факт, что введенная переменная tgx имеет на отрезке интегрирования разрыв (в точке х = p/2). Поэтому в данном случае такая подстановка неприменима. При замене переменной в определенном интеграле следует внимательно следить за выполнением перечисленных выше условий.


Системы линейных алгебраических уравнений