49. Представление задачи оптимизации в канонической, стандартной и матричной форме. Постановка задачи линейного программирования. Математическая модель все типов задач линейного программирования.

ЗЛП называетсяС задача математич. Модель кот. м/б представлена в векторной, стандартной, матричной, симметричной и каноническом форме.

Матричная форма

Каноническая форма

Стандартная форма

К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов.Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например: задача об оптимальном использовании ресурсов при производственном планировании; задача о смесях (планирование состава продукции); задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке"); транспортные задачи (анализ размещения предприятия, перемещение грузов).  В общем виде модель записывается следующим образом: целевая функция:f(x) = c₁x₁ + c₂x₂ + ... + c_nx_n → max(min) (1)

 ограничения: a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n {≤ = ≥} b₁,

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n {≤ = ≥} b₂, (2)

a_m1x₁ + a_m2x₂ + ... + a_mnx_n {≤ = ≥} b_m

 требование неотрицательности: x_j ≥ 0, j=1,n. (3)

При этом a_ij, b_i, c_j (i=1,m;j=1,n).) - заданные постоянные величины.Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2) и (3).Систему ограничений (2) называют функциональными ограничениями задачи, а ограничения (3) - прямыми.Вектор  , удовлетворяющий ограничениям (2) и (3), называется допустимым решением (планом) задачи линейного программирования. План  , при котором функция (1) достигает своего максимального (минимального) значения, называется оптимальным.

50. Решение задач линейного программирования графическим методом.

Свойства решения задач линейного программирования.

Рассмотрим множество решений системы неравенств вида

Теорема. Множество решений совместной системы m линейных неравенств с 2-мя переменными х1,х2 является выпуклым многоугольником или выпуклой многоугольной областью.

Док-во. Каждое из неравенств определяет одну из полуплоскостей являющуюся выпуклым множеством. Множеством решений совместной системы линейных неравенств служат точки которые одновременно принадлежат полуплоскостям всех неравенств, т.е. принадлежат их пересечению.

Пересечение выпуклых множ-в, есть выпук.мн-во. Это множ-во явл-ся выпуклым многоугольником, либо выпуклой многоугольной областью.

 Алгоритм решения ЗЛП геометрическим методом

1. Посторить прямые уравнения кот. получ-ся после замены знаков нер-в на знаки рав-в

2. Найти полупл-ти опред-ые каждым из ограничений

3. Определить многоугольник решений

4. построить направл-ий вектор с берущий начало из точки нач.коорд.(0,0)

5. построить прямую и проходящую ч/з начала корд.

6. передвигать прямую z в напр-ии вектора с в результате чего находят т. в кот. цф принимает max,min знач-е. найти корд. Этой т.

7. Вычислить знач-е цф в т. max,min. Xmin(x1,x2), Xmax(x1’,x2’).

Zmin=Z(Xmin), Zmax=Z(Xmax).

51.Общая идея симплексного метода. Алгоритм решения задачи линейного программирования симплексным методом. Симплексные преобразования метода:построение начального опорного плана, признак оптимальности опорного плана, переход к нехудшему опорному плану. Симплекс таблицы. Метод искусственного базиса.

Метод реш-я ЗЛП. Нах-ся все крайние т-ки многоуг-ка реш-ий и из них выбир-ся оптимальное. Такой метод реш-я универсален, но чрезвычайно трудоемок, кол-во крайних реш-ий можно рассчитать по ф-ле

, n-кол-во переменных, m-кол-во огранич.(уравнений). Каждую из этих точек необходимо найти, затем подставить в цф, получ-ые знач-я сравнить и выбрать среди них оптим-е реш-е. Общая идея симпл.метода закл-ся в след-м: перемещаясь от данной крайней т. по смежному ребру к след-ей лучшей, а затем еще лучшей , найти оптим. Реш-е ЗЛП.

несколько приемов нахожд-е 1-го опорного плана или 1-го базисного реш-я ЗЛП.