Вопрос 27

Прямая и двойственная задачи линейного программирования. Каждой задаче линейного программирования можно сопоставить другую, называемую двойственной или сопряженной к данной задаче. Определение. Пусть дана задача нахождения max функции F=c₁x₁+c₂x₂+…+c_nx_n при ограничениях:

a₁₁x₁+ a₁₂x₂+…+a_1nx_n≤b₁

a₂₁x₁+ a₂₂x₂+…+a_2nx_n≤b₂

a_m1x₁+ a_m2x₂+…+a_mnx_n≤b_m

Двойственной задачей к ней будет следующая: Найти min функции F*=b₁y₁+b₂y₂+…+b_my_m при ограничениях:

a₁₁y₁+ a₁₂y₂+…+a_m1y_m≥c₁

a₂₁y₁+ a₂₂y₂+…+a_m2y_m≥c₂

a_1ny₁+ a_2ny₂+…+a_mny_n≥c_n

y₁,…,y_m≥0

Двойственная задача составляется по следующим правилам: 1. Если целевая функция исходной задачи max, то целевая функция двойственной задачи – min; 2. Матрица исходной задачи

A=(a₁₁ a₁₂ … a_1n и т.д.)

Матрица двойственной задачи – транспонированная матрица к ней A’=(a₁₁ a₂₁ … a_1n и т.д.)

3. Число переменных в двойственной задаче равно числу ограничений в исходной задаче. 4. Коэффициенты при целевой функции исходной задачи становится столбцом свободных членов двойственной задачи. И наоборот, столбец свободных членов исходной задачи составляет коэффициенты целевой функции двойственной. 5. Если в системе ограничений в исходной задачи есть неравенство ≥, то умножить его на (- 1) и получить ≤. Исходная задача содержит неравенство ≤ или =, двойственная задача будет содержать только неравенства ≥.

Вопрос 28

Транспортная задача. В m пунктах отправления А₁, А₂,…, А_n (поставщики) находится соответственно a₁,a₂,…,a_m единиц однородного груза. Этот груз надо доставить в n пунктов назначения B₁,B₂,…,B_n (потребители) в количестве b₁,b₂,…,b_n единиц. Стоимость перевозок единицы груза из пункта A_i в B_j задана C_ij i=1,…,m; j=1,…,n. Требуется составить такой план перевозок, при котором их общая стоимость минимальна. x_ij - объем груза, перевозимого из пункта A_i в B_j. Матрица планирования:

Поставщики	Потребители						Запасы груза
	B1	B2	…	Bj	…	Bn
A1	C11	C12	…	C1j	…	C1n	a1
A2	C21	C22	…	C2j	…	C2n	a2
…	…	…	…	…	…	…	…
Ai	Ci1	Ci2	…	Cij	…	Cin	ai
…	…	…	…	…	…	…	…
Am	Cm1	Cm2	…	Cmj	…	Cmn	am
Потребители	b1	b2	…	bj	…	bn	∑ ai=a ∑ bj=b

Если суммарные запасы ∑ a_i=a совпадает с суммой потребности. ∑ b_j=b, то имеем закрытую модель транспортной задачи. Если задача не закрытая, то возможны два случая (a≠b): 1. Количество запасов больше потребности a>b. Вводим фиктивного потребителя B_n+1 с потребностью(a-b) цена поставки из каждого пункта назначения A_i к B_n+1 равна нулю C_in+1 =0. 2. Общие потребности больше общих запасов b>a. Вводим фиктивного поставщика с запасом груза (b-a) и цена поставки от этого поставщика A_m+1 ко всем потребителям 0 C_m+1j=0. Таким образом, задача сведется к закрытой.