misle.ru страница 1
скачать файл

メ褌à 2. ハ瑙í顆褥à… à 鈞萵. テ韜 åä 湜… 鈞萵 蓁… n=2 è n>2


Задачи линейного программирования могут представляться по-разному, но все их можно привести к каноническому виду.

Правила приведения задачи линейного программирования к каноническому виду состоят в следующем:

  • нахождение минимума функции цели равносильно нахождению максимума функции: .

Таким образом, если целевая функция исходной задачи исследуется на минимум, т.е. , то можно рассмотреть функцию с противоположным знаком, которая будет стремиться к максимуму: ;

  • если в ограничениях правая часть отрицательна, то следует умножить это ограничение на –1;

  • если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства. Если неравенства вида «≤», то в левую часть неравенства прибавляется дополнительная неотрицательная переменная, если неравенства вида «≥», то из левой части неравенства вычитается дополнительная неотрицательная переменная;

  • дополнительные переменные в целевую функцию входят с нулевыми коэффициентами, т.е. .

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

Пример. Представить следующую ЗЛП в канонической форме:



Решение. Заменим функцию на . Из левых частей ограничений–неравенств вида «≥» вычтем неотрицательные переменные , и . К левым частям ограничений–неравенств вида «≤» прибавим неотрицательные переменные и . В итоге получаем ЗЛП в канонической форме:



Пример. Привести к симметричной форме ЗЛП, заданную в общем виде:



Решение. Исключим из системы ограничений–равенств любые три переменные. В данном случае удобно исключить из первого ограничения переменную , из второго – и из третьего – . Учитывая неотрицательность переменных, получим:

Опустив переменные , и , придем к эквивалентным неравенствам. Подставив переменные , и в целевую функцию, получим функцию, зависящую только от двух переменных и :





Пример. Привести к симметричной форме ЗЛП, заданную в каноническом виде:



Решение. Находим общее решение системы ограничений, например методом Гаусса:

В полученных равенствах опустим неотрицательные переменные , и и перейдем к эквивалентным неравенствам:



Исключим из целевой функции переменные и . Получаем



.

В итоге получим ЗЛП в симметричной форме:




Запишем задачу ЛП в матричной и векторной форме. Для этого рассмотрим:

  • – матрица коэффициентов системы ограничений;

  • – матрица-строка коэффициентов целевой функции;

  • – матрица-столбец свободных членов;

  • – матрица-столбец неизвестных.

Тогда каноническая задача ЛП в матричной форме имеет следующий вид:

,

где 0 – нулевая матрица-столбец той же размерности, что и Х.

В векторной форме каноническая задача ЛП имеет следующий вид:

,

где , ,…, – вектора условий функции при соответствующих переменных (столбцы), 0 – нулевая матрица-столбец той же размерности, что и Х.


Задачи


  1. Представить ЗЛП в канонической форме.

  1. Представить ЗЛП в симметричной форме.


テ褓å顆褥à… 竟…
è 胙瑶顆褥îå 湜å 鈞萵 è淲鳫魲î ð魲ì頏魵瑙


Графический метод решения задачи линейного программирования является наиболее простым и наглядным. Этот метод целесообразно использовать для решения задач с двумя переменными, когда ограничения выражены неравенствами. В случае трех переменных графическое решение становится менее наглядным, а при большем числе переменных – даже невозможным.

Данный метод основывается на возможности графического изображения области допустимых решений задачи и целевой функции, и нахождении среди них оптимального решения.

Рассмотрим стандартную задачу ЛП относительно двух переменных:

.

Геометрическая интерпретация области допустимых решений.

Каждое из неравенств системы ограничений на координатной плоскости Ох1х2 определяет некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих полуплоскостей.

Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР) и представляет собой выпуклую фигуру, обладающую следующим свойством: если две произвольные точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей.

Область допустимых решений графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством.

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

Геометрическая интерпретация целевой функции.

Выражение целевой функции в зависимости от значения Z представляет собой семейство параллельных прямых, называемых линиями уровня. Причем в точке (0,0) целевая функция Z=0, а с увеличением Z прямые семейства «приближаются» к границе области допустимых решений, которые определяются системой линейных неравенств.

Оптимальное значение целевой функции достигается в одной (или нескольких) граничных точках области допустимых решений.

Для нахождения экстремального значения целевой функции используют вектор градиент . Направление вектора показывает направление возрастания целевой функции, а противоположный вектор (антиградиент) – направление убывания целевой функции.



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

Суть графического метода решения задач ЛП основывается на следующих утверждениях:



  1. совокупность опорных планов задачи ЛП совпадает с системой вершин многоугольника решений;

  2. целевая функция достигает оптимального значения на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

Если в одной и той же системе координат изобразить область допустимых решений системы неравенств задачи и семейство параллельных прямых , то задача определения экстремума функции Z сведется к нахождению точки в области допустимых решений, через которую проходит прямая из семейства Z = const, и которая соответствует экстремальному значению параметра Z.

Для практического решения задачи линейного программирования графическим методом используется следующая методика.



  1. Составляется задача ЛП в общем виде.

  2. Строится многоугольник решений. Для этого необходимо:

  • построить прямые, уравнения которых получаются в результате замены в системе ограничений знаков неравенства на знаки точных равенств;

  • найти полуплоскости, определяемые каждым из ограничений задачи и определить многоугольник решений;

Полуплоскости, координаты точек которых удовлетворяют каждому из неравенств системы, удобно определять с помощью точки начала координат О(0,0). Если при подстановке этой точки в неравенство системы знак неравенства выполняется, то за областью решения этого неравенства принимается та полуплоскость, где лежит начало координат, в противном случае за областью решения неравенства принимается полуплоскость, не содержащая начала. Аналогичные рассуждения проводятся по отношению к каждому неравенству. В итоге выделяется часть плоскости, которая ограничена прямыми системы, координаты точек которых будут одновременно удовлетворять всем неравенствам системы.

  1. Строится вектор-градиент который начинается в точке (0;0) и заканчивается в точке .

  2. Строится начальная прямая функции цели или .

Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

  1. Путем параллельного переноса прямой функции цели в направлении вектора определяется точка, в которой целевая функция принимает максимальное значение, либо множество точек с одинаковыми максимальными значениями целевой функции (если прямая сливается с одной из сторон многоугольника решений), либо устанавливают неограниченность функции сверху на множестве планов (Z→).

Если параллельно переносить прямую функции цели в направлении вектора , то определяется точка, в которой целевая функция принимает минимальное значение.



  1. Определяются координаты точки максимума (минимума) функции цели, для чего необходимо решить систему уравнений прямых, пересекающихся в этой точке.

  2. Вычисляется значение целевой функции в оптимальной точке.

Графическое решение задачи линейного программирования
со многими переменными

Задачу со многими переменными можно решить графически, если в ее канонической записи присутствуют не более двух свободных переменных, для этого число независимых переменных n и число линейно независимых уравнений m должны удовлетворять условию: .

Чтобы решить такую задачу, необходимо:


  • выделить некоторый базис переменных в системе уравнений-ограничений;

  • выразить целевую функцию через свободные переменные;

  • опустить базисные переменные и перейти к эквивалентной системе неравенств;

  • преобразованную двумерную задачу решить обычным графическим способом;

  • найдя две координаты оптимального решения, подставить их в ограничительные уравнения и определить остальные координаты оптимального плана.

Пример. Решить предыдущую задачу ЛП (о плане производства обувной фабрики) графическим способом:



Решение. Это задача с тремя переменными. Ее можно решить графически, если в канонической записи будет присутствовать не более двух свободных переменных. Приведем данную задачу в каноническую форму. Для этого из 2-го уравнения выразим базисную переменную : и подставим ее значение в целевую функцию:

.

Из условия следует , что равносильно неравенству . Следовательно, симметричная задача ЛП примет следующий вид:



Полученную задачу решим обычным графическим способом.



Так как , то область допустимых решений находится в первой координатной четверти. На плоскости Ох1х2 построим прямые, уравнения которых получаются в результате замены в системе ограничений знаков неравенства на знаки точных равенств



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




Построим вектор градиента . Перпендикулярно к нему построим одну из прямых семейства . Например, при получим z=8, причем эта прямая оказалась параллельной прямой . Полученную прямую будем параллельно передвигать в направлении вектора до последней точки пересечения с областью допустимых решений D. Наша прямая совпадает с прямой l3: . Поэтому исходных точек экстремума будет множество, т.е. все точки отрезка .
Координаты точек и можно определить из рисунка: и , но так как исходная задача имеет три переменные, то найдем, подставив значение переменной во 2-ое ограничение:

  1. при получим ;

  2. при получим .

Для аналитической записи любого оптимального решения необходимо составить выпуклую линейную комбинацию опорных решений и :

, где и .

Следовательно,



,

где и .

Тогда

.

Таким образом, чтобы получить максимальную прибыль, равную 18 ден.  ед., фабрике необходимо:



  1. по : выпускать 2 пары обуви А, 5 пар обуви В и 2 пары обуви С. При этом заготовки I и III видов будут израсходованы полностью (т.к. и );

  2. по : выпускать 4 пары обуви А, 3пар обуви В и не выпускать обувь вида С. При этом 2 заготовки I вида не будут использованы (т.к. ), а заготовки III вида будут израсходованы полностью (т.к. ).

Индивидуальные задания


Задание 1. Построить на плоскости область допустимых решений системы линейных неравенств и найти наибольшее и наименьшее значения линейной функции Z(X).

  1. Задание 2.Решитьграфическимметодомзадачуспеременными
  1. Контрольные вопросы


  1. Сформулируйте задачу планирования производства и составьте ее математическую модель.

  2. Сформулируйте задачу о диете и составьте ее математическую модель.

  3. Сформулируйте задачу о раскрое материалов и составьте ее математическую модель.

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

  5. Как записывается общая задача линейного программирования?

  6. Чем характеризуется каноническая задача линейного программирования?

  7. Что называется областью допустимых решений задачи линейного программирования?

  8. Что такое допустимое решение задачи линейного программирования?

  9. Что такое оптимальное решение задачи линейного программирования?

  10. Экономико-математическая модель простейшей задачи производственного планирования.

  11. Геометрическая интерпретация задачи линейного программирования.

  12. Какие задачи решаются графическим методом?

  13. В чем заключается графический метод решения задачи линейного программирования?

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

  15. Графическое решение задач линейного программирования, содержащих более двух переменных.

  16. В каком случае оптимальный план не является единственным?

  17. Как строится область допустимых решений в случае двух переменных?

  18. Как построить нормаль к линии уровня целевой функции?

  19. Как построить линии уровня целевой функции?

  20. Что характеризует градиент целевой функции?

  21. Какие типы решений могут получаться при решении задачи линейного программирования?

  22. Когда не существует решения задачи линейного программирования?

  23. В каком случае задача линейного программирования может быть сведена к задаче относительно двух переменных?

  24. Что называется базисным решением системы линейных алгебраических уравнений?

  25. Какие ограничения существуют для значений разрешающего элемента?
скачать файл


Смотрите также: