Решение транспортной задачи методом потенциалов

Методами СЗУ и наим ст-и находится первое базисное реш-е. Для целевой фу-и оптим-е решение задачи сводится к выражению базисных неизв-х ч/з свободные неизвестные.

Т о, после отыскания первого базисного реш-я все неизвестные задачи оказываются разбитыми на две группы:

l)Xkl -базисные;

2) Xpg - свободные.

Целевую функцию можно представить в виде: Для определения коэфф при свободных неизвх используют метод потенциалов. В методе потенциалов каждому пункту отправления приписывают некоторую величину (потенциал) a_I (j=1,m), и каждому пункту назначения- величину (потенциал) b_I (j=1,n), т.е. для каждой базисной неизвестной стоимости перевозки разбивают на потенциалы:

Поскольку совокупность всех базисных неизвестных (с потенциалами ) образуют систему m+n-1 линейных уравнений с числом m+n неизвестных , то система в таком виде неразрешима. Для решения системы одному из неизвестных (потенциалов), оказавшимся свободным, приписывают любое числовое значение, чаще всего «0», и предварительно переходят к косвенным стоимостям С_pg. Тогда коэффициенты при свободных неизвестных будут равны

.

1. Если величины неотриц-ы, то исходное базисное реш-е будет опт-м, или если для любой не базисиой клетки матрицы перевозок (p,g) выполнимо нерав-о: ,то допустимое базисное реш-е оптимально.

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

Пример трансп зад

Исходная таблица:

Поставщик	Потребитель	Запасы груза
B1	B2	B3
A1
A2
A3
A4
Потребность

Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям.
Находим опорный план по правилу северо-западного угла:
Введем некоторые обозначения:
A_i^* - излишек нераспределенного груза от поставщика A_i
B_j^* - недостача в поставке груза потребителю B_j

Помещаем в клетку (1,1) меньшее из чисел A₁^*=10 и B₁^*=40
Т к запасы пост-ка A₁ исчерпаны, то строка 1 в дальнейшем в расчет не принимается и т д….

Поставщик	Потребитель	Запасы груза
B1	B2	B3
A1
A2
A3
A4
Потребность

Целевая функция Z= =250

Решаем задачу методом потенциалов:
Примем некоторые обозначения:
i - индекс строки; j - индекс столбца; m - количество поставщиков;
n - количество потребителей.

Этап 1

Полагая потенциал U₁=0, опред-м остальные пот-ы из соотн-я U_i+V_j=C_i,j (i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₁=C_1,1-U₁= 3 U₂=C_2,1-V₁=-1 U₃=C_3,1-V₁=1 V₂=C_3,2-U₃= 2 V₃=C_3,3-U₃= 1
U₄=C_4,3-V₃=0
Определяем значения оценок S_i,j=C_i,j-(U_i+V_j) для всех свободных клеток:
S_1,2 = c_1,2 - (u₁ + v₂) = 0. S_1,3 = c_1,3 - (u₁ + v₃) = 0. S_2,2 = c_2,2 - (u₂ + v₂) = 0.
S_2,3 = c_2,3 - (u₂ + v₃) = 4. S_4,1 = c_4,1 - (u₄ + v₁) = -1. S_4,2 = c_4,2 - (u₄ + v₂) = 1.

Задача нелинейного программирования, это если ограничения или целевая функция содержат нелинейные функции и X является подмножеством конечномерного векторного пространства.

 

Расчёт коэффициентов уравнений регрессии

Для квадратичных зав-ей:

Свободный член b1 вычисляем: ;

Коэфф-ы для лин-х членов определяем: ;

Коэфф-ы для квадр-х членов -:

Коэфф- при вза-х определяем:

Для линейных и не полных квадратичных зависимостей:

B1=сумма (у_u) / N1, у_u- эксперимент знач выходного парам(при повторении средн значение)_, N1- число точек плана

Коэфф для линх членов определяем:B1=сумма (у_u * x_iu) / N1

Коэфф парных взаимодействияй: B1=сумма (у_u * x_iu * x_ju) / N1