Вопрос 23

Общая задача линейного программирования. В общем случае задача линейного программирования сводится к описыванию такого решения x=(x₁,x₂,…,x_n) системы m линейных уравнений с n неизвестных

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

a₂₁x₁+ a₂₂x₂+…+a_2nx_n=b₂ (1)

a_m1x₁+ a_m2x₂+…+a_mnx_n=b_m

при которых целевая функция F(x₁,x₂,…,x_n) достигает max/min значений. При формулировке общей задачи линейного программирования предполагается, что оптимальное решение (F(x₁,x₂,…,x_n)=c₁x₁+c₂x₂+…+c_nx_n) числа переменных m<n. Краткая форма записи системы (1): ∑ a_ij x_j=b_i (j=1,…,m). Целевая функция F=∑ с_i x_j. Матричная форма записи АХ=В, где А=(a₁₁ a₁₂ … a_1n и т.д.) Х=(х₁ и т.д.) В=(b₁ и т.д.). Если система ограничений задачи линейного программирования записана в системе (1), то говорят, что она приведена к каноническому виду. В большинстве задач ограничения задаются в виде системы неравенств, причем встречаются системы смешанные, т.е. есть неравенства ≥/≤. Но любую систему уравнений введением добавочных переменных. Если дано неравенство: a₁₁x₁+ a₁₂x₂+…+a_1nx_n≤b₁. Вводим добавочную переменную x_n+1≥0, тогда неравенство можно привести к уравнению: a₁₁x₁+ a₁₂x₂+…+a_1nx_n+x_n+1=b₁. Если дано неравенство: a₂₁x₁+ a₂₂x₂+…+a_2nx_n≥b₂ Вводим добавочную переменную х_n+2 и неравенство к уравнению переведется следующим образом: a₂₁x₁+ a₂₂x₂+…+a_2nx_n+x_n+2=b₂. Таким образом, количество добавочных переменных совпадает с количеством неравенств. Любая задача линейного программирования может быть приведена к каноническому виду. Система из n уравнений с m неизвестными (m<n) – либо не имеет решений, либо имеет бесконечное множество решений. Если система несовместна, то условия задачи противоречивы, задача не имеет решений. Система совместна, если rang A=rang A₁, A₁ – расширенная матрица системы. Допускается, что в системе ограничений нет зависимых уравнений. Пусть система совместна и имеет бесконечное множество решений. Базисных решений у системы может быть: C^m_n=n!/m!(n-m)! базисных переменных m штук, свободных (n-m) штук. Базисные решения дают допустимые решения задачи; по одному допустимому необходимо найти оптимальное решение задачи.

Вопрос 24

Основные теоремы задач линейного программирования. Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым. Множество точек в пространстве называется выпуклым, если пересекает продолжение границ самого множества; не обязательно, что множество замкнутое. Множество решений задач линейного программирования геометрически изображается в виде выпуклого многогранника, на плоскости выпуклый многоугольник. Такой многогранник имеет C^m_n вершин. Теорема 2. Если существует и единственно оптимальное решение задачи линейного программирования, то оно совпадает с одной из угловых точек (вершин) множества допустимых решений. Теорема 2 позволяет сделать вывод: для поиска оптимального решения достаточно перебрать конечное число точек. Для этого нужно уметь строить многогранник, но это возможно в дву- и трехмерном случае. Необходим аналитический метод поиска вершин, из которых найдется оптимальное решение. Теорема 3. Каждому допустимому базисному решению соответствует вершина области допустимых решений системы ограничений. Теорема 4. Каждой угловой точке множества допустимых решений системы ограничений соответствует допустимое базисное решение задач линейного программирования. Вывод: Если существует и единственно оптимальное решение, то оно совпадает с одним из базисных решений системы ограничений.