Часть 3. Методы математического программирования

§0. Оптимизационные задачи

f(x) V   V (V, f, ) f –целевая функция,   допустимое множество

x₀ f(x₀)  f(x) x (V, f, )_max  (V,  f, )_min

f(x₁,x₂,…,x_n) методы математического программирования

линейное, целочисленное, выпуклое, нелинейное программирование, вариационное исчисление, теория оптимального управления

Глава 1. Линейное и целочисленное программирование

§1. Задачи линейного программирования

V = Rⁿ,  - множество решений системы линейных уравнений и нестрогих линейных неравенств, f – линейная

а) f(x) = б) в) тип задачи, max(min)

1.  =  либо выпукло 2.   , f  f^   max (оптимальное решение)

3. Оптимальное решение – на границе , если не единственно, то выпукло

§2. Примеры экономических задач.

1. Задача о распределении производственной программы

3 вида продукции, 2 вида ресурсов

Ресурсы	Виды продукции			Запасы ресурсов
	I	II	III
1	а11	а12	а13	b1
2	а21	а22	а23	b2
Стоимость	с1	с2	с3

2. Задача о диете

2 вида кормов Питательные вещества ₁, ₂, ₃ не менее b₁, b₂, b₃ ед. для нормального развития

Питательные вещества	Корма		Минимальная норма
	А	В
1	a11	a12	b1
2	a21	a22	b2
3	a31	a32	b3
Стоимость	c1	c2

3. Транспортная задача

2 поставщика однородной продукции А₁, А₂, их запасы (мощности) а₁, а₂

3 потребителя этой продукции В₁, В₂, В₃ их потребности (емкости) b₁,b₂,b₃

c_ij стоимость перевозки 1 ед. продукции от A_i к B_j а₁+ а₂ = b₁+ b₂+ b₃ закрытая

а1+ а2 = b1+ b2+ b3		B1	B2	B3
		b1	b2	b3
A1	a1	c11	c12	c13
A2	a2	c21	c22	c23

§3. Графический метод решения двумерных задач линейного программирования.

2 переменных, нет ограничений-равенств f(x) = c₁x₁ + c₂x₂  max

a_i1x₁ + a_i2x₂  b_i, i = 1,…,m

Пересечение 1-й четверти и полуплоскостей x₁  0, x₂  0

 а)  б) многоугольник в) неограниченное многоугольное множество

Градиент f=(c₁, c₂) n неизвестных, n – 2 равенства (уравнения) rank A = n – 2

§4. Каноническая форма задачи линейного программирования.

Основная задача Все ограничения – равенства (уравнения)

Любая задача сводится к основной введением новых переменных в неравенствах (разность между большей и меньшей частями)

Для задачи 1 х₄, х₅ – остатки ресурсов, для задачи 2 (о диете) х₃, х₄, х₅ – избыток питательных веществ сверх минимальных норм.

При неотрицательных правых частях неравенства  сводятся к уравнениям с «+x_i»,   с «x_i».

Каноническая задача а) каждое уравнение содержит базисную переменную

б) правые части всех уравнений неотрицательны

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

a₁₁x₁ + a₁₂x₂ + x₃ = b₁ Каноническая задача всегда имеет план

a₂₁x₁ + a₂₂x₂ + x₄ = b₂ Базисный план канонической задачи (0, 0, b₁, b₂)

x₁  0, x₂  0, x₃  0, x₄  0 Базисных планов много

Оптимальный план следует искать среди базисных