Инструменты пользователя

Инструменты сайта


examination:mo:question3

Вопрос №3. Задачи линейного программирования и их свойства. Графический метод решения.

Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.

Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи.

Система ограничений, определяющая множество планов, диктуется условиями задачи. Задачей линейного программирования (ЗЛП) является выбор из множества допустимых планов наиболее выгодного (оптимального).

Формулировка задачи ЛП:

<m>min z = c_{1}x_{1}+c_{2}x_{2}+{…}+c_{n}x_{n} ~~~~ (1)</m>, при условии что:

<m>delim{lbrace}{matrix{4}{1}{{a_{11}x_{1}+a_{12}x_{2}+{…}+a_{1n}x_{n}>=b_{1}} {a_{21}x_{1}+a_{22}x_{2}+{…}+a_{2n}x_{n}>=b_{2}} {……….} {a_{m1}x_{1}+a_{m2}x_{2}+{…}+a_{mn}x_{n}>=b_{m}}}}{} ~~~~ (2)</m>

<m>delim{lbrace}{matrix{4}{1}{{x_{1}>=0} {x_{2}>=0} {……….} {x_{n}>=0 }}}{} ~~~~ (3)</m> - условие неотрицательности переменных

где <m>x_{1},…,x_{n}</m> - варьируемые параметры

z - целевая функция

<m>с_{1},…,с_{n}</m> - коэф-ты целевой функции при варьируемых параметрах

<m>a_{ij}</m> - коэф-ты при варьируемых параметрах в ограничениях

<m>b_{1},…,b_{m}</m> - правые части ограничений

Необходимо найти такие значения варьируемых параметров <m>x_{1},…,x_{n}</m>, которые доставляют min функции z, при выполнении условий (2),(3)

Стандартная форма записи:

<m>min z=C^{T}X</m>

<m>Ax=b</m>

<m>X>=0</m>

где <m>C = (matrix{4}{1}c_1 {c_{2}} {…} {c_{n}}})</m>; <m>X=(matrix{4}{1}x_1 {x_{2}} {…} {x_{n}}})</m>; <m>b=(matrix{4}{1}b_1 {b_{2}} {…} {b_{m}}})</m>; <m>A=(matrix{3}{3}a_11 {…} {a_{n1}} {…} {…} {…} {a_{m1}} {…} {a_{mn}}})</m>

Если вместо неравенства <m>…>=b_{i}</m> будет равенство <m>…=b_{i}</m>, то равенство заменяется на 2 неравенства.

Если <m>x_{k}⇐0</m>, тогда заменяем нер-во на <m>-x_{k}>=0</m>

Если <m>x_{k}<>0</m>, то <m>x_{k}=x_{k1}-x_{k2}</m>, где <m>x_{k}^{1};x_{k}^{2} > 0</m>

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

<m>delim{lbrace}{matrix{3}{1}{{min z = C^{T}X} {Ax=b}{x>=0}}}{}</m>

Любую задачу ЛП можно записать в канонической форме, чтобы преобразовать <m>Ax>=b</m> в <m>Ax=b</m> добавляются слабые переменные:

<m>delim{lbrace}{matrix{4}{1}{{a_{11}x_{1}+a_{12}x_{2}+{…}+a_{1n}x_{n} - alpha_{1}=b_{1}} {a_{21}x_{1}+a_{22}x_{2}+{…}+a_{2n}x_{n}- alpha_{2}=b_{2}} {……….} {a_{m1}x_{1}+a_{m2}x_{2}+{…}+a_{mn}x_{n}- alpha_{m}=b_{m}}}}{} ~~~~~~~~~~ alpha_{i}>=0</m>

Графический метод

Графическая интерпретация возможна только, только если задача имеет 2 варьируемых параметра. Т.к. двухмерное построение на плоскости самое наглядное.

Пусть нам требуется найти минимальное значение функции <m>z = c_{1}x_{1}+c_{2}x_{2}</m>, при ограничениях <m>delim{lbrace}{matrix{4}{1}{{a_{11}x_{1}+a_{12}x_{2}⇐b_{1}} {a_{21}x_{1}+a_{22}x_{2}⇐b_{2}} {……….} {a_{m1}x_{1}+a_{m2}x_{2}⇐b_{m}}}}{}</m> при условии <m>x_{1}>=0; x_{2}>=0</m>. Допустим, что система ограничений при условии неотрицательности совместна и ее многоугольник решений ограничен (но в общем случае он может быть и не замкнут в каком-либо направлении).

Далее строим многоугольник решений системы ограничений и график линейной функции z при z = 0 (z=const - линия уровня).

Теперь необходимо найти точку многоугольника решений, в котором прямая z=const является опорной и функция z при этом достигает минимума. Значения z возрастают в направлении вектора N, поэтому прямую z = 0 передвигаем в направлении вектора N . Из рисунка выше видно, что линия уровня дважды становится опорной по отношению к многоульнику решений в точках А и С, причем минимальное значение приобретает в точке А. Координаты точки А можно найти из системы уравнений прямых АВ и АЕ - это и есть решение поставленной задачи.

Свойства задачи ЛП

Область допустимых решений задачи ЛП представляет собой выпуклый многогранник в пространстве варьируемых параметров задачи, где размерность пространства многогранника = m-n. Если m-n=2, то многогранник вырождается в многоугольник, он может быть незамкнут в каком-либо направлении.

Выпуклое множество: для любых двух точек множества отрезок, лежащий между ними будет входить в это множество

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

examination/mo/question3.txt · Последние изменения: 2014/01/15 08:19 (внешнее изменение)