13. Постановка взаимно-двойственных задач. Поясните (можно на примере) экономическую суть понятия двойственности.

Если задана общая задача ЛП

f (x) = c₁x₁+c₂x₂+c₃x₃ max

a₁₁x₁ +a₁₂x₂ +a₁₃x₃ <= b₁,

a₂₁x₁ +a₂₂x₂ +a₂₃x₃ <= b₂,

x_i ≥ 0 i=1,2,3

то двойственной по отношению к ней будет:

(x) = b₁y₁+b₂y₂ min

a₁₁y₁ +a₂₁y₁ ≥ c₁,

a₁₂y₁ +a₂₂y₂ ≥ c₂,

a₁₃y₁ +a₂₃y₃ ≥ c₃,

y₁ ≥ 0, y₂ ≥ 0

Экономическую суть понятия двойственности можно пояснить на примере задачи об использовании ресурсов.

Т₁,Т₂,Т₃ – товары S₁,S₂ – сырье

товары сырье	S1	S2	Прибыль
Т1	1	2	8
Т2	3	4	10
Т3	5	6	12
Запасы	40	25

x₁,x₂,x₃ – объем производства товаров Т₁,Т₂,Т₃

t = 8x₁+10x₂+12x₃ max

x₁+3x₂+5x₃ ≤ 40

2x₁+4x₂+6x₃ ≤ 25

x_i ≥ 0

y₁, y₂ - цены ресурсов

y₁+2y₂≥ 8

3y₁+4y₂ ≥10

5y₁+6y₂ ≥12

y_i ≥ 0 i=1,2

=40y₁+25y₂ min

14.Постановка транспортной задачи как задачи линейного программирования. Закрытая и открытая модель транспортной задачи. Приведите примеры.

A₁,…A_m – пункт производства

B₁,…B_n – потребители

а_i ≥ 0 запасы A₁

b_j ≥ 0 полезность B₁

b_ij тарифы перевозок от A₁ к B₁

b_ij объем перевозок от A₁ к B₁

Требуется составить такой план перевозок, при котором спрос

всех потребителей был бы выполнен и при этом общая стоимость всех

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

F= ∑_(i=1)^m▒〖∑_(j=1)^n▒〖c_(ij ) x_ij→L ∑_(i=1)^m▒〖x_ij=〗 b_(ij ,) j=1…n ∑_(j=1)^n▒〖x_ij=〗 a_(ij ,) i=1…m x_ij ≥ 0

X = x_ij план ТЗ

: Fmin = F(X^*) оптимальный план ТЗ

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

∑_(i=1)^m▒а_(1 ) =∑_(j=1)^n▒b_ij . С неправильным балансом (открытая модель):  ∑_(i=1)^m▒а_(1 ) ≠∑_(j=1)^n▒b_ij .

Пример:

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	B1	B2	B3	B4	Запасы
A1	1	2	4	3	6
A2	4	3	8	5	8
A3	2	7	6	3	10
Потребности	4	6	8	8

Проверим необходимое и достаточное условие разрешимости задачи.  

	B1	B2	B3	B4	B5	Запасы
A1	1	2	4	3	0	6
A2	4	3	8	5	0	8
A3	2	7	6	3	0	10
Потребности	4	6	8	8	2

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равным 2 (26-24). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.