Экономико-математические методы и модели (стр. 3 )

Б			9	5	4	3	2	0
	4	10	2/3	0	1	1/3	0	1/3
	5	7	1/6	1	0	1/3	0	-1/6
	2	63	9/2	0	0	1	1	3/2
	201	7/2	0	0	2	0	7/2

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

.

Ответ: при .

в) Оптимальное решение двойственной задачи находим по формуле:

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

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

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

Исходные данные транспортной задачи обычно записываются в таб­лице:

bi ai	b1	b2	…	bn
a1	c11	c12		c1n
a2	c21	c22		c2n
…
am	cm1	cm2		cmn

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

Пример. Четыре предприятия используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырьё сосредоточено в трёх пунктах, а запасы соответственно равны 160, 140 и 170 ед. Тарифы перевозок заданы матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной?

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

Минимальный тариф равный 1 находится в клетке (1,3). х13 = min(A1,B3)=A1=160. Запишем это значение в соответствующую клетку и временно исключим из рассмотрения строку А1. Теперь потребности пункта B3 считаем равными 190-160=30 ед. В оставшейся части таблицы наименьший тариф находится в клетке (3,2) и равен 2. х32 = min(A3,B2)=B2=50. Внесём значение в соответствующую клетку и исключим из рассмотрения столбец B2. Запасы пункта А3 считаем равными 170-50=120 ед. В оставшейся части (строки А2, А3 и столбцы В1, В3, В4) минимальный тариф равен 3 и находится в клетке (3,3). х33 = min(A3,B3)=В3=30. И так далее пока не исчерпаем запасы и не удовлетворим потребности. Получим следующую таблицу.

Потребности Запасы	B1=120	B2=50	B3=190	B4=110
β1=2	β2=2	β3=3	β4=6
A1=160	α1=-2	7	8	1 160	2
A2=140	α2=2	4 120	5	9	8 20
A3=170	α3=0	9	2 50	3 30	6 90

Число заполненных клеток равно 6 и m+n-1=3+4-1=6 – план невырожденный. Оптимальный план найдём методом потенциалов.

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

, положим , тогда.

(Обычно равным нулю принимают потенциал строки или столбца с наибольшим числом заполненных клеток.)

Теперь проверим пустые клетки на выполнение неравенства .

.

Для клетки (1, 4) неравенство не выполняется, значит в неё нужно "ввезти" груз. Строим цикл.

Цикл перерасчёта таблицы - это последовательность ячеек, начинающаяся и заканчивающаяся в одной и той же клетке, с вершинами, лежащими в занятых клетках, кроме одной.

Вершина цикла – клетка, в которой происходит поворот под прямым углом.

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

1.  каждой из клеток, связанных циклом присваивается знак: пустой ячейке "+", остальным - поочерёдно знаки "-" и "+" .

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

В нашем примере цикл образуют четыре ячейки: (1,4) – пустая, для которой не выполняется неравенство, и (1,3), (3,3), (3,4) – заполненные.

х = min(160, 90)=90. Значит в плюсовые клетки "завозим" 90 ед. груза, из минусовых "вывозим". Получим новый опорный план:

Потребности Запасы	B1=120	B2=50	B3=190	B4=110
β1=0	β2=2	β3=3	β4=4
A1=160	α1=-2	7	8	1 70	2 90
A2=140	α2=4	4 120	5	9	8 20
A3=170	α3=0	9	2 50	3 120	6

Расставим потенциалы и проверим пустые клетки на выполнение неравенства .