Математические методы в экономике

 

Шаг 3. Применяя правила вычисления элементов новой симплекс-таблицы, получим:

 

Базисные переменные	Свободные члены ур-я	Все переменные						Оценочное отношение
		x1	x2	x3	x4	w1	w2
x1	4/3	1	0	1/12	0	2/3	-1/12
x2	1/3	0	1	-1/6	0	-1/3	1/6
x4	3	0	0	1/4	1	0	-1/4
	7/3	0	0	-5/12	0	-(1+3М)/3	(3-9М)/8

 

Т.к. в поеследней строке нет  положительных чисел, отвечающих переменным и искусственные переменные имеют отрицательные значения, то полученное решение ЗЛП оптимально. Ему соответствуют x₁=3/4, x₂=1/3, x₄=3, w₁=w₂=0, min f(x) = 7/3.

Принимая во внимание связь исходной задачи ЗЛП с М-задачей, окончательно получаем min f(x) = 7/3 при x₁ = 4/3, x₂ = 1/3.

 

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

 

В практических приложениях ЛП наиболее часто встречается транспортная задача (Тз). Это классическая ЗЛП  о рационализации поставок важнейших  видов с/х и промышленной продукции, оптимального планирования грузопотоков, работы различных видов транспорта и др.

6.1. Простая транспортная задача.

 

Пусть имеется однородный  груз, сосредоточенный в m пунктах отправления в количестве а₁, а₂, …, а_m единиц, который необходимо доставить в n пунктов назначения в количествах  b₁, b₂, … , b_n единиц.

С_ij – транспортные издержки на перевозку единицы груза из i-го пункта отправления в j – пункт назначения, а x_ij – количество груза перевозимого по маршруту (i, j), тогда стоимость перевозки всего груза по маршруту (i, j) будет равна величине с_ijx_ij . Суммарная стоимость перевозки грузов от всех отправителей по всем пунктам назначения будет соответственно равна: f(x) =

Требуется найти такие х_ij для всех маршрутов (i, j) при которых f(x) будет минимальной.

Из условия задачи следует, что неизвестной величиной является количество единиц груза, перевозимого из пункта отправления в пункт назначения – x_ij ≥0.

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

 

Математическая  модель Тз

f(x) = → min   (1)

       (2)

x_ij ≥0,     .

Матрица X= (х_ij)  - называется планом перевозок, а  C = (с_ij)– матрицей транспортных  издержек.

 Тз представим в табличной  форме:

 

 

 

Таблица 1

Потребители                    Bj   Поставщики               Ai	B1	B2	…	Bn	Запасы
A1	c11 x11	c12 x12	…	c1n x1n	a1
A2	c21 x21	c22 x22	…	c2n x2n	a2
…	…	…	…	…	…
Am	cm1 xm1	cm2 xm2	…	cmn xmn	an
Потребности	b1	b2	…	bn

 

План называется допустимым, если  x_ij удовлетворяют ограничениям (2). Допустимый план называется оптимальным, если он минимизирует f(x).

Объектом исследования в Тз является планирование перевозок грузов. Цель исследования – составление плана  перевозки грузов, обеспечивающего  минимальные транспортные расходы. Критерий задачи – минимальные транспортные расходы. Обозначим    - количество груза у всех поставщиков,   - потребности в данном грузе всех потребителей.

Теорема Условие            =  (3)

 является необходимым  и достаточным для разрешимости Тз.

Модель транспортной задачи, для  которой выполняется (3) называется закрытой Тз.

Если условие (3) не выполняется, то такие задачи называются открытыми Тз. Чтобы решить открытую Тз, ее приводят к закрытой, вводя фиктивного потребителя или поставщика.

В случае, когда  >   вводят фиктивного потребителя с потребностью

b_n+1 =   - и с_i,n+1=0, так как груз не перевозится.

Если    <    вводят фиктивного поставщика с мощностью а_m+1 = -    и c_m+1,j=0, , так как груз не перевозится.

 

 

6.2. Построение первоначального плана транспортной задачи.

 

 Для решения исходные данные  Тз (1), (2) сводят в таблицу 1. Из  условия (3) следует, что система  ограничений линейно зависима  и содержит только m + n – 1 независимых уравнений, следовательно, невырожденный опорный план Тз содержит m + n – 1 положительных компонентов или перевозок, а остальные равны нулю. Клетки, в которых находятся отличные от нуля перевозки, соответствуют базисным переменным. Если количество заполненных клеток равно m + n – 1, то план является невырожденным, в противном случае – вырожденным.

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

• если а₁ < b₁, то х₁₁ = а_1.    строка i=1 исключается из дальнейшего рассмотрения, а потребность первого потребителя b₁ (столбец j=1) уменьшается на величину а₁;
• если а₁ > b_1, то х₁₁ = b_1, столбец j=1исключается из дальнейшего рассмотрения, а наличие груза у первого поставщика а₁ (строка i=1) уменьшается на величину b₁;
• если а₁ = b_1, то  х₁₁ = а₁ = b₁, строка i=1 или столбец j=1 исключаются из дальнейшего рассмотрения.

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

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

 

 

 

Пример 1. Определить первоначальный базисный план (ПБП) методом северо-западного угла для Тз, исходные данные которой приведены в таблице 2.

Таблица 2.

 

Ai\Bj	11	8	6	1
12	9	7	4	10
14	3	4	8	9

 

Решение. Применяя метод северо-западного угла, получаем ПБП, который приведен в таблице 3.

 

Таблица 3 

	Ai\Bj	11	8	6	1
	12	9      11	7        1	4	10
	14	3	4        7	8        6	9      1

 

Количество заполненных клеток в таблице 3 равно 5, m+n-1=2+4-1=5. Следовательно, полученный план невырожденный. Значение базисных переменных: х₁₁=11, х₁₂=1, х₂₂=7, х₂₃=6, х₂₄=1. Остальные переменные – небазисные  и их значения равны нулю. Транспортные расходы при данном плане перевозки будут равны: f(x)=c₁₁x₁₁+c₁₂x₁₂+c₂₂x₂₂+c₂₂x₂₃+c₂₄x₂₄=9×11+7×1+4×7+8×6+9×1=191.

В таблице 3 значения, соответствующие  базисным переменным отмечены знаком

 

Метод минимальной  стоимости. При построении ПБП в данном методе учитывается стоимость перевозок. Из всей таблицы стоимости выбирают наименьшую стоимость  и в клетку, которая ей соответствует помещают меньшее из чисел a_i или b_j. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Проверка полученного ПБП на вырожденность и расстановка (в  случае вырожденности плана) нулей  осуществляется так же, как это  описано для метода северо-западного угла.

 

Пример 2. Определить ПБП методом минимальной стоимости для Тз, исходные данные которой приведены в таблице 2

Решение. Применяя метод минимальной стоимости, получаем ПБП, который приведен в таблице 4.

Таблица 4

	Ai\Bj	11	8	6	1
	12	9	7        5	4       6	10        1
	14	3      11	4          3	8	9

Количество заполненных клеток в таблице 3 равно 5, следовательно, полученный план невырожденный. Значение базисных переменных: х₁₂=5, х₁₃=6, х₁₄=1, х₂₁=11, х₂₂=3. Остальные переменные – небазисные и их значения равны нулю. Транспортные расходы при данном плане перевозки будут равны:

f(x)=c₁₂x₁₂+c₁₃x₁₃+c₁₄x₁₄+c₂₁x₂₁+c₂₂x₂₂=144 условных единиц.

С точки зрения оптимальности ПБП  полученный вторым методом лучший.

 

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

 

 Построенный одним из описанных  выше методов ПБП, можно довести  до оптимального с помощью  метода потенциалов. На каждом  шаге решения Тз методом потенциалов  вычисляется система m+n чисел-потенциалов. Строкам в таблице сопоставляются числа U₁, U₂, … U_m, столбцам – V₁, V₂, … , V_n. Числа U_i(i= ) и V_j(j= ) называют потенциалами соответствующих поставщиков и потребителей и вычисляют из условий:

 U_j+V_j= С_ij

для всех занятых клеток.

 

Критерий оптимальности  плана Тз. Для того, чтобы план X=(x_ij) Тз был оптимальным, необходимо и достаточно, чтобы ему соответствовала такая система из m+n чисел U_i и V_j, для которой выполняются условия:

1. D_ij=c_ij-(U_i+V_j)=0 для всех занятых клеток
2. D_ij=c_ij-(U_i+V_j) ³ 0 для всех незанятых клеток.

 

Переход от заданного  плана Тз к другому плану с  не большим значением функции f(x).

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

 

D_lk=C_lk – (U_l+V_k)<0   (4)

 

Эта пустая клетка рекомендуется к  заполнению, в результате которого одна из заполненных клеток станет пустой. Процедура перепланировки соответствует  взаимной перемене  роли двух переменных в симплекс-методе.  Построим следующую цепь преобразований базисного решения (плана). Клетку (1, k) в которой выполняется (4) отметим c. Для нее строим замкнутую ломанную линию (цикл), вершины которой расположены в занятых клетках таблицы, а звенья – вдоль строк и столбцов. Причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, другое – в столбце. Если ломаная линия, образующая цикл, пересекается, то точки пересечения не являются вершинами. Для каждой свободной клетки таблицы можно построить единственный цикл. Вершинам цикла, начиная от вершины, находящейся в свободной клетке, присваиваем поочередно  знаки «+» и «–»