Примеры решения экономических задач математическими методами

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

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

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

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

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

Альтернативный оптимум в транспортных задачах Признаком наличия альтернативного оптимума в транспортной задаче является равенство нулю хотя бы одной из оценок свободных переменных в оптимальном решении (Xопт1).Сделав перераспределение грузов относительно клетки, имеющей Δij = 0, получим новое оптимальное решение (Хопт2), при этом значение целевой функции (транспортных расходов) не изменится.

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

Экономический анализ транспортных задач Проведем экономический анализ задачи на конкретном примере.

Выбор оптимального варианта использования производственного оборудования На предприятии имеются три группы станков, каждая из которых может выполнять пять операций по обработке деталей (операции могут выполняться в любом порядке). Максимальное время работы каждой группы станков соответственно равно 100, 250, 180 ч. Каждая операция должна выполняться соответственно 100, 120, 70, 130 ч.

Целочисленное программирование Общая формулировка задачи Некоторые задачи линейного программирования требуют целочисленного решения. К ним относятся задачи по производству и распределению неделимой продукции (выпуск станков, телевизоров, автомобилей и т.д.).

Прогнозирование эффективного использования производственных площадей Рассмотрим следующую задачу. Для улучшения финансового положения фирма приняла решение об увеличении выпуска конкурентоспособной продукции, для чего принято решение об установке в одном из цехов дополнительного оборудования, занимающего 19/3 м2 площади. На приобретение дополнительного оборудования фирма выделила 10 усл. ед., при этом она может купить оборудование двух видов. Приобретение 1-го комплекта оборудования 1-го вида стоит 1,0 усл. ед., 2-го вида — 3 усл. ед.

Параметрическое линейное программирование

Определение диапазона оптимального решения выпуска продукции при изменении условий реализации

Транспортная параметрическая задача

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

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

Задачи с несколькими целевыми функциями Формулировка задачи В рассматриваемых выше задачах линейного программирования математические модели имели одну целевую функцию, для которой находилось максимальное или минимальное значение экономического показателя. Однако на практике часто требуется найти экстремальные значения нескольких экономических показателей. В этом случае математическая модель имеет несколько целевых функций, причем некоторые из них требуют нахождения максимального, а другие — минимального значений. Поэтому ставится задача нахождения такого компромиссного (субоптимального) решения модели, в котором значения всех рассматриваемых экономических показателей были бы приближены к экстремальным значениям.

Элементы оптимального управления Нелинейное программирование

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

Метод множителей Лагранжа

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

Определение 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.


На главную