Решение оптимизационных экономических задач методами линейного программирования

y₁ = 0, y₂ = 7 ; y₁ = 4, y₂ = 5.

 

Отобразим на графике  найденные нами точки и найдем полуплоскости, определяемые каждым из ограничений задачи:

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

Обозначим границы области многоугольника решений:

Рассмотрим целевую  функцию задачи G = 2y₁ + 5y₂ → min.

Построим вектор, отвечающий значению функции G = 2y₁ + 5y₂ = 0. Поскольку нас интересует минимальное решение, следовательно проводим от вектора характеристическую прямую в виде перпендикуляра и двигаем ее до первого касания обозначенной области. На графике она обозначена пунктирной линией.

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

Характеристическая прямая пересекает область в точке D. Т.к. точка D получена в результате пересечения прямых (3) и (4), то ее координаты удовлетворяют уравнениям следующих прямых:

y₁ + 3y₂ ≥ 15

2y₁+4y₂ ≥ 28

Решим систему уравнений:

 

Подставив полученные значения в целевую функцию, получим ответ:

G_min = 2*12 + 5*1 = 29

Высчитав G_min мы видим, что оно совпадает с результатом исходной задачи: G_min = F_max = 29.

 

в) Найти решение второй задачи, используя  теорему двойственности.

 

Так как y₁ и y₂ больше нуля, то соответствующие ограничения в исходной  задаче выполняются как строгое равенство:

 

Подставим найденные y₁ и y₂ в ограничения:

(1) 3*12 + 3*1 > 27 → x1 = 0

(2) 2*12 + 1*1 > 10 → x2 = 0

(3) 1*12 + 3*1 = 15 → x3 ≠0

(4) 2*12 + 4*1 = 28 → x4 ≠0

 

Ограничения двойственной задачи (3) и (4) выполняются как равенства, а (1) и (2) как строгие неравенства. Следовательно, x₁ и x₂ в оптимальном плане исходной задачи равны нулю. Остается решить ограничения исходной задачи с внесенными поправками и подставить результаты в целевую функцию:

 

F_max = F(0; 0; 1; 0,5) = 27*0 + 10*0 + 15*1 + 28*0,5 = 29

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

9. Транспортная задача и ее решение методом потенциалов

 

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

Пусть имеется m пунктов отправления (ПО): , в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно единиц. Также имеется n пунктов назначения (ПН): , подавших заявки соответственно на единиц груза. Считаем, что сумма всех заявок равна сумме всех запасов (сбалансированная транспортная задача):

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

Экономико-математическая модель задачи имеет вид задачи линейного  программирования. Обозначим  – количество единиц груза, отправляемого из i-го ПО в j-й ПН . Совокупность чисел ( ) будем называть планом перевозок, а сами величины – перевозками.

Необходимо найти такой  план перевозок ( ), при котором целевая функция (суммарная стоимость перевозок) будет минимальной:

и который удовлетворяет  следующим ограничениям:

1) Суммарное количество  груза, направляемого из каждого  ПО во все ПН должно быть  равно запасу груза в данном  пункте:

 

2) Суммарное количество  груза, доставляемого в каждый  ПН из всех ПО, должно быть  равно заявке, поданной данным  пунктом:

 

3) Условие неотрицательности:

Решение транспортной задачи разбивается на два этапа:

1) определение исходного  опорного решения;

2) построение последовательных  итераций – приближение к оптимальному  решению.

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

	ПН					…
ПО						…
						…
						…
…	…	…		…		…	…
						…

 

Определение исходного  опорного решения. Существует несколько способов, наиболее популярными являются:

- метод северо-западного  угла,

- метод минимального  элемента,

- метод аппроксимации  Фогеля.

Они перечислены в  порядке усложнения алгоритма, но при  этом получаемое решение, как правило, меньше отличается от оптимального.

В каждом методе на любом шаге в выбранную ячейку ( ) таблицы помещается максимальная допустимая перевозка – минимальное из того, что есть у соответствующего поставщика (ПО) и требуется соответствующему потребителю (ПН) . При этом каждый раз «закрывается» строка таблицы, если у соответствующего поставщика (ПО) больше нет груза, или «закрывается» столбец, если соответствующему потребителю (ПН) больше не надо груза. Методы отличаются лишь способом построения последовательности заполнения ячеек таблицы.

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

В методе минимального элемента заполнение начинается с ячейки с минимальной стоимостью. Каждый раз переходят к следующей свободной ячейке (расположенной в «незакрытых» сроках и столбцах) с минимальной стоимостью.

 

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

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

Для каждой свободной  клетки вычисляется числовая характеристика – косвенная стоимость: .

Критерий оптимальности плана перевозок:

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

1) , если (для заполненных клеток),

2) (для свободных клеток).

Т.е. если все косвенные  стоимости неотрицательные, то решение  оптимальное, в противном случае его можно улучшить.

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

	Значение l определяется как максимально возможное, сохраняющее неотрицательность всех перевозок, т.е. по соотношениям вида . На рис.1: . В результате определения l и пересчета перевозок получаем новый опорный план, которые необходимо проверить на оптимальность.
Рис. 1

 

 

Алгоритм применения метода потенциалов:

1) Определить начальный  опорный план, рассчитать стоимость  перевозок.

2) Составить систему  уравнений  для заполненных клеток. При найти потенциалы всех поставщиков и потребителей .

3) Определить косвенные  стоимости свободных ячеек по  формуле: 

4) Если все косвенные  стоимости неотрицательны, то план  перевозок оптимальный.

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

6) Найти максимальное  значение l при условии сохранения неотрицательности всех перевозок, составить новый опорный план, рассчитать стоимость перевозок.

7) Перейти к п.2.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

10. Пример решения транспортной задачи

 

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

Мощность  поставщиков	Мощность  потребителей
	12	12	9	12
24	5	4	3	4
21	3	2	5	5
9	1	6	3	2

 

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

24 + 21 + 9 = 54 – суммарные запасы.

12 + 12 + 9 + 12 = 45 – суммарные  запросы.

54 > 45 – имеется избыток груза.

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

Теперь нам нужно  свести модель к закрытой – для  этого введем фиктивного потребителя  с мощностью 54 – 45 = 9. И только теперь можно приступать к определению  оптимального плана методом наименьших потенциалов.

По этому методу выбирается клетка с минимальным тарифом, и  в нее вписывается максимально  возможная поставка. В результате либо полностью будет удовлетворена  чья-то потребность, либо полностью  вывезен чей-то груз; тогда соответствующий потребитель или поставщик выбывает. Продолжая такое рассмотрение – переходим к опорному (начальному) плану перевозок. Наш опорный план будет выглядеть так:

 

 

 

Мощность  поставщиков		Мощность  потребителей
		12		12		9		12		9 (Ф.)
24		5		4		9          3		12          4		3          10	U1 = 0
21		3           3		12          2		5		5		6          10	U2 = 0
9		9          1		6		3		2		10	U3 = 2
V1 = 3	V2 = 2		V3 = 3		V4 = 4		V5 = 10

 

Теперь нам предстоит  проверить оптимальность рассматриваемого плана перевозок. Для этого введем потенциалы U_i для поставщиков и V_j - для покупателей. Эти потенциалы подбираются таким образом, чтобы для каждой заполненной клетки таблицы выполнялось равенство: V_j = U_i + C_ij