Исходная транспортная матрица

 

В табл. 2.2 по строкам матрицы представлены пункты (станции) отправления от А₁ до А₄ и объемы погрузки в тоннах – 100, 150, 90, 30 т, а по столбцам – пункты (станции) назначения от В₁ до В₅ и объемы выгрузки – 40, 80, 110, 50, 90 т. Данная транспортная задача является сбалансированной (a_i = b_j = 370 т), поэтому добавлять фиктивного потребителя ФВ или фиктивного поставщика ФА не требуется. На пересечении строк и столбцов в клетках матрицы в маленьких квадратиках записаны показатели критерия оптимальности транспортной задачи, например, затраты на перевозку единицы груза или кратчайшие расстояния между соответствующими пунктами (станциями) погрузки и выгрузки. Расстояние между станцией погрузки А₁ и станцией выгрузки В₁, как следует из матрицы, равно 10 (или 100, 1000 и т. д.) км, потом – 9, 8, 5 км и т. д. Тогда целью, решения задачи явится отыскание совокупности объемов перевозок между всеми пунктами (станциями) погрузки и выгрузки (корреспонденций), обеспечивающей минимальный объем перевозочной работы (грузооборота) в тонно-километрах. Любую совокупность корреспонденций, обеспечивающую весь объем перевозок, будем называть планом, а совокупность, обеспечивающую минимум грузооборота, – оптимальным планом перевозок.

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

Операция 1. Построение опорного плана.

Опорным, называется любой допустимый, как правило, не оптимальный план, который является исходным для последующего решения. Для построения опорного плана существует ряд методов. Самый простой из них – метод северо-западного угла (табл. 2.3).

Графический метод решения задач нелинейного программирования

Графический метод можно использовать для решения задачи НП, которая содержит две переменных х₁ и х₂, например задачи следующего вида:

Z = f(x₁, x₂) → min (max);

g_i(x₁, x₂) ≤ b_i, .

Чтобы найти ее оптимальное решение, нужно выполнить следующие действия:

1. Найти ОДР, определяемую ограничениями задачи. Если окажется, что эта область пуста, то это означает, что задача не имеет решения.

2. Построить семейство линий уровня целевой функции f(х₁, х₂) = C при различных значениях числового параметра С.

3. При решении задачи на минимум определить направление убывания, а для задачи на максимум — направление возрастания линий уровня ЦФ.

4. Найти точку ОДР, через которую проходит линия уровня с наименьшим в задаче на минимум (соответственно, наибольшим в задачи на максимум) значением параметра С. Эта точка будет оптимальным решением. Если ЦФ не ограничена снизу в задаче на минимум (сверху — в задаче на максимум), то это означает, что задача не имеет оптимального решения.

5. Найти координаты точки оптимума и определить в ней значение ЦФ.

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

Классическая задача оптимизации

Обозначения.

Всюду ниже R — множество вещественных, N — натуральных, а C — комплексных чисел. С самого начала мы будем использовать векторные обозначения. Всегда через R ^m обозначается m-мерное вещественное линейное пространство. При этом мы всегда считаем, что в R ^m фиксирован базис и отождествляем R ^m с арифметическим m-мерным пространством (пространством упорядоченных наборов m вещественных чисел). Буква Q будет обозначать нуль пространства R ^m. Индекс внизу всегда обозначает координату вектора, например, x_i — это i-ая координата вектора x. Последовательности мы обычно будем обозначать индексом вверху: {xⁿ}.

Через (·, ·) обозначается каноническое скалярное произведение в Rm: (x, y) = å m i=1xiyi. Если не оговорено противное,, порожденную скалярным произведением: || · || =(å m i=1xi2)1/2.

Обозначение B(x₀, r) закреплено для шара в пространстве R ^m с центром в x₀ радиуса r: B(x₀, r) = {x Î R ^m: ||x - x₀|| £ r}.

Если A = {a_ij}^{n, m} _{i=1, j=1} —n× m-матрица, то через A также обозначается и линейный оператор из R ⁿ в R ^m, задаваемый этой матрицей.

Для двух векторов x, y Î R ^m мы будем писать x £ y, если x_i £ y_i при всех i = 1, ..., m; здесь x_i и y_i — i-е координаты векторов x и y, соответственно.

Мы будем различать обозначение f: X ® Y отображения, действующего из множества X во множество Y, и обозначение f: x ® y (или x ® f(x)) отображения, переводящего точку x в точку f(x), а также обозначение f отображения и обозначение f(x) значения отображения f в точке x.

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: