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

Введение     

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

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

Тема «Решение задач линейного программирования графическим методом» актуальна в современном мире,  потому что графический метод довольно прост и нагляден для решения задач линейного программирования. Графический метод применяется при решении задач линейного программирования возникшего во многих областях, например экономике.      

Цель  курсовой работы  – решение  задачи линейного программирования графическим методом.     

Для реализации поставленной цели были поставлены следующие задачи:

-Изучить теоретический материал по теме курсового проекта.

-Построить математическую модель данной задачи.

-Решить задачу графическим методом.

-Решить задачу с помощью электронных таблиц Excel.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

1.1 Линейное программирование

 

          Линейное программирование является разделом, с которого начала развиваться дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и других задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.

Итак, линейное программирование возникло после  Второй мировой войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря  возможности широкого практического  применения, а так же математической «стройности».   
       Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых, может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.

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

 Линейное программирование представляет собой наиболее часто  используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

- рационального использования сырья и материалов; задачи оптимизации раскроя;

- оптимизации производственной программы предприятий;

- оптимального размещения и концентрации производства;

- составления оптимального плана перевозок, работы транспорта;

- управления производственными запасами;

и многие другие, принадлежащие сфере оптимального планирования.     

     Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций.     

     Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике. 

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

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

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

В самом общем виде задача математически записывается так:

U = f(Х)  max; X є W, (1.1)

где X = (x1, х2, ..., хn);

W — область допустимых  значений переменных х1, х2, ..., хn;

F(X) — целевая функция.

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

ее оптимальное решение, т. е. указать Х0 є W такое, что f(x0) ≧  f(X)

при любом X є W, или для случая минимизации – f(X0) ≦ f(X) при

любом X є W.

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

          Методы решения оптимизационных задач зависят как от вида целевой функции f(X), так и от строения допустимого множества W. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического  программирования.

В математическом программировании принято выделять следующие основные задачи в зависимости от вида целевой функции f(X) и от области W:

 • задачи линейного  программирования, если f(X) и W линейны;

• задачи целочисленного программирования, если ставится 

условие целочисленности переменных x1,x2,…,xn;

• задачи нелинейного программирования, если форма f(X) носит нелинейный характер.

 

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

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

(1.2)

(1.3)

(1.4)

(1.5)

При этом система линейных уравнений (1.3) и неравенств (1.4),

(1.5), определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f(X) называется целевой функцией, или критерием оптимальности.

В частном случае, если I = Ø, то система (1.3) — (1.4) состоит только из линейных неравенств, а если / = М, то — из линейных уравнений.

Если математическая модель задачи линейного программирования имеет вид:

(1.6)

  (1.7)

;

, (1.8)

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

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

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

1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

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

3) если среди ограничений  имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

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

Пример 1. Приведение к канонической форме задачи линейного программирования:

Решение

Введем в каждое уравнение системы ограничений  выравнивающие переменные х4, х5, х6. Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений  переменные х4, Х6 вводятся в левую часть со знаком «+», а во второе уравнение вводится х5 со знаком «—».

Итак:

2х2 - х3 + Х4 = 5;

X1 + х2 - х3 - х5 = - 1;

2х1-х2 + х6 = - 3;

х4 > 0, х5> 0, х6 > 0.

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на - 1:

2x2 - Х3 +x4 = 5;

-X1— х2 + х3 + х5 = 1;

-2x1 + х2 — х6 =3;

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

, где  , 

Подставляя данное выражение в систему ограничений и целевую функцию и записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме:

 

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

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

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

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

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

Запишем задачу линейного программирования с двумя 

переменными:

целевая функция:

 (1.9) 

ограничения:

(1.10)

    (1.11)

          Каждое из неравенств (1.10) – (1.11) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми  ; ( ; х1 = 0; х2 = 0. В том случае, если система неравенств (1.10) – (1.11) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых значений является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей.

 Областью допустимых решений системы неравенств (1.10) – (1.11) может быть: 
- выпуклый многоугольник;

- выпуклая многоугольная  неограниченная область;

- пустая область;

- луч;

- отрезок;

- единственная точка.

Целевая функция (1.9) определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значение  Z.

Вектор  с координатами с2 и с1, перпендикулярный к этим прямым, указывает направление наискорейшего возрастания Z, а противоположный вектор – направление убывания Z. 
Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (1.10) – (1.11) и семейство параллельных прямых (1.9), то задача определения максимума функции Z сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z = const, и которая соответствует наибольшему значению параметра Z. 
Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. 
Для определения данной вершины построим линию уровня  , проходящую через начало координат и перпендикулярную вектору  , и будем передвигать ее в направлении вектора   до тех пор, пока она не коснется последней крайней (угловой) точки многоугольника решений. Координаты указанной точки и определяет оптимальный план данной задачи. 
Заканчивая рассмотрение геометрической интерпретации задачи (1.10) – (1.11), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 1 –4. Рис. 1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 3 изображен случай, когда максимум недостижим, а на рис. 4 – случай, когда система ограничений задачи несовместна. Отметим, что нахождение минимального значения Z при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня Z передвигается не в направлении вектора  , а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минимального значения.