Математика (3 сем-р) (стр. 3 )

Теорема. Если основная задача линейного программирования имеет оптимальный план , то является оптимальным планом двойственной задачи.

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

Применительно к рассмотренному нами примеру матрица. Вектор . Тогда: .

Эти значения и находятся в индексной строке последней таблицы.

В.4. Экономическая интерпретация двойственных оценок

Согласно первой теореме двойственности, , следовательно, можем записать: (11)

т. е. доход зависит от объёмов ресурсов: . Вычислим градиент этой функции: (12)

Сделаем следующие выводы:

Формула (11) отражает общий принцип баланса результатов производства и затрат . Двойственные оценки обеспечивают этот баланс.

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

Из (11) и (12) следует, что при изменении отдельно взятого ресурса на единицу увеличивается ровно на величину двойственной оценки этого ресурса:

(13)

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

Замечание. Формула (13) верна только при достаточно малом изменении объёмов ресурсов по сравнению с их общим количеством. Если это изменение велико, то учетная цена того или иного ресурса может стать нулевой. Точные количественные границы такого изменения рассмотрим ниже.

В.5. Устойчивость двойственных оценок

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

Теорема. При изменении объёма ресурсов двойственные оценки будут устойчивыми, если выполняется неравенство: (14)

В формуле (14) вектор означает первоначальный объём ресурсов. Матрица составлена, как уже указывалось выше, из столбцов последней симплекс-таблицы, соответствующих первоначальному базису.

Например, если изменить запасы ресурсов в ранее рассмотренной задаче на величину (штрих означает транспонирование), то можно проверить условие устойчивости так:

=

Таким образом, при данном изменении объёмов ресурсов двойственные оценки не изменятся (будут устойчивыми).

Новое значение целевой функции при измененных ресурсах можно определить по выражению:

.

Значение находим с использованием первой теоремы двойственности:

.

Применяя результаты нашего примера, получим

. Отсюда .

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

Тема 4. Транспортная задача (ТЗ)

В.1. Экономико-математическая модель ТЗ. Общая постановка

Транспортная задача - частный случай ЗЛП, который в силу своих особенностей допускает решение более простыми методами.

Пример 1. Имеется 3 поставщика и 4 потребителя. Запасы поставщиков, спрос потребителей, а также затраты на перевозку единицы груза для каждой пары «поставщик – потребитель» приведены в таблице поставок:

Поставщики	Запасы	Потребители, спрос
B1	B2	B3	B4
20	110	40	110
А1	60	1	2	5	3
А2	120	1	6	5	2
Аm	100	6	3	7	4

В левом верхнем углу произвольной клетки (i, j) (которой соответствуют поставщик Аi и потребитель Вj) стоит т. н. коэффициент затрат (тариф) – затраты на перевозку единицы груза от поставщика Аi к потребителю Вj.

Необходимо определить объёмы перевозок для каждой пары поставщик – потребитель так, чтобы:

1. запасы всех поставщиков были реализованы;

2. спрос всех потребителей был удовлетворён;

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

Построить ЭММ задачи.

Общая постановка:

В задаче имеются следующие исходные данные:

q  есть m пунктов отправления (ПО), или поставщиков, или баз , где находятся запасы груза ;

q  есть n пунктов назначения (ПН), или потребителей, или получателей , подавших заявки на единиц груза;

q  известны тарифы , или стоимость перевозки единицы груза от i-го поставщика к j-му потребителю.

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

Обозначим через объём перевозок от i-го поставщика к j-му потребителю. Рассмотрим распределительную (транспортную) таблицу:

ПО	Запасы	ПН, спрос
B1	B2	…	Bn
		…
А1		C11 x11	C12 x12	…	C1n x1n
А2		C21 x21	C22 x22	…	C2n x2n
…	…	…	…	…	…
Аm		Cm1 xm1	Cm2 xm2	…	Cmn xmn

Строки таблицы соответствуют базам, а столбцы - заказчикам. Например, перевозка груза с 3-й базы 2-му заказчику соответствует клетке на пересечении строки А3 и столбца В2.

Составим экономико-математическую модель задачи. Будем считать, что общее количество запасов на всех базах равно общему объёму заявок потребителей (такая ТЗ называется закрытой).

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

(1) – уравнения баланса по строкам.

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

(2) – уравнения баланса по столбцам.

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

(3)

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

(4)

Математическая формулировка: На множестве неотрицательных решений системы (1)-(2) найти такое решение , при котором значение линейной функции (4) минимально.

Произвольное допустимое решение системы (1)-(2) называется распределением поставок. Такое решение задает заполнение таблицы поставок.

Транспортная задача имеет закрытую модель, если суммарный запас равен суммарной потребности, то есть (5)

иначе будет открытая модель: (6)

ТЗ является ЗЛП, а, следовательно, может быть решена симплексным методом. Модификация симплексного метода применительно к ТЗ называется методом потенциалов (распределительным методом).

Решение задачи также осуществляется по шагам. Каждому шагу соответствует разбиение переменных на базисные (основные) и свободные (неосновные). Каждому разбиению переменных соответствует базисное решение. Клетки таблицы поставок, отвечающие базисным переменным, называются базисными (они являются заполненными), а остальные клетки – свободными (пустыми).

Число базисных переменных (а, следовательно, и заполненных клеток транспортной таблицы) закрытой ТЗ всегда равно (m+n-1), где (m – число поставщиков, n – число потребителей). В этом случае полученное распределение поставок (план) будет неврожденным

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

1.  На первом этапе находится первоначальный опорный план.

2.  На втором этапе на базе опорного плана методом потенциалов определяется оптимальный план.

Основные свойства ТЗ:

1.  ТЗ всегда имеет решение для закрытой модели.

2.  Число уравнений задачи (1)-(4) равно (m+n), а число переменных – mn.

3.  Коэффициенты при переменных в уравнениях (1) и (2) равны 1.

4.  Количество независимых уравнений будет (m+n-1), так как сумма m уравнений (1) всегда равна сумме n уравнений (2) (рассматривается закрытая модель). Значит, базисных переменных будет (m+n-1), а свободных переменных – (m-1)(n-1) (столько нулей, по крайней мере, будет в оптимальном плане).

В.2. Методы построения первоначального плана

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

Самыми простыми методами построения первоначального плана ТЗ являются:

·  Метод северо-западного угла (или диагональный метод).

·  Метод минимальной стоимости (или наименьших затрат, или минимального тарифа).

·  Метод двойного предпочтения.

Из методов оптимизации первоначального плана самым распространенным является метод потенциалов.

2.1. Метод северо-западного угла

В методе северо-западного угла, или диагональном, заполнение транспортной таблицы всегда начинается с клетки (1,1), т. е. “северо-западного угла” таблицы. Далее заполнение идет вокруг диагонали таблицы и всегда заканчивается в правом нижнем углу (клетка ). В каждой клетке объем перевозки определяется как наименьшее значение из двух чисел: остатка запаса на базе и остатка заявки потребителя.

Пример 1.1. Найти опорный план методом «северо-западного» угла для примера 1.

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

2.2. Метод минимальной стоимости (наименьших затрат, минимального тарифа)

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

Пример 1.2. Найти опорный план методом наименьших затрат для примера 1.

2.3. Метод двойного предпочтения

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

Как видим, данный метод фактически является модифицированным методом минимальной стоимости.

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

Пример 1.3. Найти опорный план методом двойного предпочтения для примера 1.

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

Особый случай:

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

Пример 2. Найти первоначальное базисное распределение поставок для следующей ТЗ: Имеется 3 поставщика и 3 потребителя.

	20	10	40
30	1	3	3
30	3	3	2
10	4	1	2

В.3. Алгоритм метода потенциалов

1. Находим опорный план.

2. Проверяем оптимальность полученного опорного плана.

Теорема о потенциалах (критерий оптимальности базисного решения):

План ( ) транспортной задачи является оптимальным тогда и только тогда, когда существуют числа такие ui (i = ), vj (j =), называемые соответственно потенциалами поставщиков и потребителей (строк и столбцов), при которых выполняются соотношения:

(7)

Как видим из системы (7), уравнения записываются для заполненных клеток, а неравенства – для свободных клеток. Справа везде стоят тарифы перевозок соответствующих клеток.

На этой теореме основывается сам алгоритм оптимизации планов транспортной задачи, который называется методом потенциалов.

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

Замечание 1. Потенциал строки (или столбца), избранный для начала м. б. любым, но после его фиксации, потенциалы других строк, столбцов определяется однозначно.

Проверяем выполнение неравенств (7) для свободных клеток.

Перепишем их в виде: , ; . Число называется оценкой клетки (i,j). Удобно оценки записывать в виде матрицы оценок .

Замечание 2. Для фиксированного опорного плана можно подобрать различные наборы потенциалов, но матрицы оценок для них будут одинаковыми.