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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

2. изучить теорию по решению задали ЛП графическим методом;

3. разработать алгоритм решения такого рода задач;

4. Решить конкретную задачу ЛП графическим методом;

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



1 ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ и методы ЕЕ решения

1.1 Постановка задачи

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

( 1.1)

и, кроме того, обращали бы в минимум линейную целевую функцию (ЦФ)

Очевидно, случай, когда ЦФ нужно обратить не в минимум, а в максимум, легко сводится к предыдущему, если изменить знак функции и рассмотреть вместо нее функцию

Допустимым решением ОЗЛП называют любую совокупность переменных , удовлетворяющую уравнениям (1.1).

Оптимальным решением называют то из допустимых решений, при котором ЦФ обращается в минимум.

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

Рассмотрим задачу линейного программирования с ограничениями-неравенствами, которые имеют вид

(1.2)

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

Введём уравнения:

(1.3)

где - добавочные переменные, которые также как и являются неотрицательными.

Таким образом, имеем общую задачу линейного программирования - найти неотрицательные , чтобы они удовлетворяли системе уравнений (1.3) и обращали в минимум .

Коэффициенты в формуле (1.3) перед равны нулю.

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

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

Пусть задача линейного программирования задана в двумерном пространстве, т.е. ограничения содержат две переменные. Найти максимальное значение функции z = c₁x₁ + c₂х₂ при следующих ограничениях:

(1.4)

Дадим геометрическую интерпретацию элементов этой задачи.

Каждое из ограничений (1.4) задает на плоскости x₁Ox₂ некоторую полуплоскость. Их пересечение является областью допустимых решений задачи.

а) ОДР - выпуклый многоугольник	б) ОДР - неограниченная выпуклая многоугольная область
в) ОДР - единственная точка	г) ОДР - прямая линия	д) ОДР - пустое множество

Рисунок 1 - Различные вариации ОДР

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

Рассмотрим геометрическую интерпретацию области допустимых решений. Каждое из неравенств системы ограничений задачи геометрически определяет полуплоскость, содержащую граничные прямые и расположенную по одну сторону от неё. Для определения полуплоскости, являющейся решением неравенства, необходимо выбрать точку с известными координатами на плоскости. Выбранная точка не должна принадлежать граничной прямой. Координаты этой точки требуется подставить в исследуемое неравенство. Если после подстановки координат точки в неравенство будет получено справедливое неравенство, то полуплоскость, определенная исследуемым неравенством, содержит данную точку. Иначе, полуплоскость, определенная исследуемым неравенством не содержит данную точку.

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

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

Перейдем к геометрической интерпретации целевой функции. Уравнение при фиксированном значении z=h () определяет на плоскости прямую . При изменении h получаем семейство параллельных прямых, которое называется линиями уровня. В каждой точке этой прямой (линии уровня) целевая функция принимает фиксированное значение, равное h.

Рассмотрим функцию , дифференцируемую в некоторой точке .

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

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

Вектор - показывает направление наибольшего убывания целевой функции.

Графический метод решения задачи линейного программирования заключается в построении на одном рисунке многоугольника допустимых решений, вектора , исходной линии уровня =0 и определении такой угловой точки этого многоугольника, в которой целевая функция принимает экстремальное (наибольшее или наименьшее) значение. Для определения точки с указанными характеристиками рассматривают положение исходной линии уровня по отношению к многоугольнику допустимых решений задачи. Если исходная линия уровня пересекает многоугольник решений, то линию уровня параллельно смещают до пересечения с последней угловой точкой в направлении вектора , при поиске максимума функции , и в направлении вектора - при поиске минимума функции (рис.2).

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

Рисунок 2 - Многоугольник допустимых решений и исходная линия уровня пересекаются, вектор лежит во втором квадранте

Рисунок 3 - Многоугольник допустимых решений и исходная линия уровня не пересекаются, вектор лежит в первом квадранте

В процессе решения задачи линейного программирования возможны случаи, когда система ограничений задачи линейного программирования несовместна (рис. 4) и задача решений не имеет; целевая функция на множестве допустимых решений неограниченно возрастает или неограниченно убывает (рис. 5); целевая функция принимает экстремальное значение в любой точке некоторого отрезка (рис. 6).

Рисунок 4 - Система ограничений задачи линейного программирования несовместна



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

Рисунок 5 - Целевая функция на множестве допустимых решений задачи линейного программирования неограниченно возрастает или неограниченно убывает

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



Рисунок 6 - Целевая функция принимает экстремальное значение в любой точке некоторого отрезка: минимальное значение - отрезок АВ, максимальное значение - отрезок CD

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

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

1.3. Алгоритм решения задач ЛП графическим методом

I. В ограничениях задачи (1.4) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

II. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (1.4). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.

Если неравенство истинное,

то надо заштриховать полуплоскость, содержащую данную точку;

иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

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

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

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

IV. Если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L - произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

V. Построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

VI. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ - против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).

VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .



2 ПРИМЕНЕНИЕ ГРАФИЧЕСКОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ПРАКТИКЕ

2.1 Решение обычной задачи ЛП графическим методом

Пример1.

Решение.

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

Этап 1. Строим прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

Границей полуплоскости является прямая . Рассмотрим первое уравнение , обозначим его цифрой (I) и выразим переменную через переменную . В результате преобразований получим следующее уравнение прямой . Данная прямая проходит через точки с координатами (0;5) и (6;3). Построим прямую на графике (рис. 9).

Для второго уравнения , обозначенного цифрой (II), выражение переменной через переменную примет следующий вид . Прямая (II) проходит через точки с координатами (3;4) и (4;1). Эту прямую также построим на графике (рисунок 7).

Этап 2. Находим полуплоскости, определяемые каждым из ограничений задачи.

Рассмотрим неравенство . Прямая (I) делит всю плоскость на две части и рассматриваемое неравенство определяет только одну из них. Для определения полуплоскости, заданной неравенством возьмем контрольную точку, не принадлежащую прямой (I), с известными координатами, например точку О(0;0). Координаты контрольной точки подставим в неравенство и получим выражение вида . Неравенство выполняется, координаты контрольной точки удовлетворяют ему, следовательно, полуплоскость, которой принадлежит точка О, и определяется исследуемым неравенством . На рисунке полуплоскость, заданную неравенством , отмечаем короткими штрихами.

Рисунок 7 - Многоугольник допустимых решений, исходная линия уровня и вектор задачи

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

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

Этап 3. Находим многоугольник решений как часть плоскости, которая одновременно удовлетворяет требованиям первого, второму неравенства и условию неотрицательности. В нашем случае, это выпуклый многоугольник ОАВС - область допустимых решений данной системы неравенств.

Этап 4. Строим исходную линию уровня . Прямая примет вид. Выразим переменную через переменную и получим равенство . Эта прямая проходит через точки с координатами (0;0) и (3;-2).

Этап 5. Строим вектор . Вектор =(2;3) перпендикулярен исходной линии уровня и указывает направление, в котором эта функция возрастает с наибольшей скоростью.

Этап 6. Определяем точку, в которой целевая функция z принимает максимальное значение. Для этого исходную линию уровня передвигаем в направлении вектора . При движении в этом направлении последней общей точкой прямой с многоугольником решений является точка В. В этой точке целевая функция принимает максимальное значение.

Этап 7. Определяем координаты точки B и вычисляем значение целевой функции в этой точке. Точка B лежит на пересечении прямых (I) и (II). Для нахождения координат точки В решим систему уравнений



В результате решения системы уравнений найдены координаты точки В(3;4). Подставим координаты этой точки в выражения для целевой функции и получим максимальное её значение .

Ответ: при х₁=3, х₂=4.

2.2 Экономическая постановка задачи линейного программирования

Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии 60 изделий, второй линии 80 изделий. На радиоприемник первой модели расходуется 15 однотипных элементов электронных схем, на радиоприемник второй модели 10 таких же элементов. Максимальный суточный запас используемых элементов равен 950 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны 40$ и 20$ соответственно. Определите оптимальные суточные объемы производства первой и второй моделей на основе графического решения задачи.

Переменные задачи

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

- суточный объем производства радиоприемников первой модели, [шт/сутки];

- суточный объем производства радиоприемников второй модели, [шт/сутки];

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

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

· их объемы производства, т.е. и радиоприемников в сутки;

· прибыль от их реализации - согласно условию, соответственно 40 и 20 $.

Таким образом, доход от продажи суточного объема производства радиоприемников первой модели равен $ в сутки, а от продажи радиоприемников второй модели - $ в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи радиоприемников первой и второй модели:

[$/сутки]

Ограничения

Возможные объемы производства радиоприемников и ограничиваются следующими условиями:

· количество элементов электронных схем, израсходованное в течении суток на производство радиоприемников обоих моделей, не может превышать суточного запаса этих элементов на складе;

· суточный объем первой технологической линии (производство радиоприемников первой модели) не может превышать 60 шт в сутки, второй (производство радиоприемников второй модели) - 80 шт;

· объемы производства радиоприемников не могут быть отрицательными.

Таким образом, все ограничения задачи делятся на 3 группы, обусловленные:

1) расходом элементов электронных схем;

2) суточным объемом технологических линий;

3)неотрицательностью объемов производства.

Запишем эти ограничения в математической форме:

1) Т.к. из условия на радиоприемники первой и второй модели необходимо 15 и 20 элементов соответственно, то данное ограничение имеет вид:

[шт/сутки]

2) Ограничения по суточному объему первой и второй технологических линий имеют вид:

[шт/сутки]

3) Неотрицательность объемов производства задается как

.

Таким образом, математическая модель этой задачи имеет вид:

Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис.8).



прямая (2.1) - точки (0;95) и (63,(3);0), прямая (2.2) проходит через точку параллельно оси , прямая (2.3) проходит через точку параллельно оси .

Рисунок 8 - Графическое решение задачи о производстве радиоприемников

Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (1), получим , что является истинным неравенством, поэтому стрелкой обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (2.1). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис.8). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDE.

Целевую прямую можно построить по уравнению

Точки пересечения с осями - (0;75) и (37,5;0)

Строим вектор из точки (0;0) в точку (40;20). Точка D - это последняя вершина многоугольника допустимых решений ABCDE, через которую проходит целевая прямая, двигаясь по направлению вектора . Поэтому D - это точка максимума ЦФ. Определим координаты точки D из системы уравнений прямых ограничений (1) и (2)

Получили точку D(60;5) [шт/сутки].

Максимальное значение ЦФ равно [$/сутки].

Таким образом, наилучшим режимом работы предприятия является ежесуточное производство радиоприемников первой модели в количестве 60 штук и радиоприемников второй модели в количестве 5 штук. Доход от продажи составит 2500$ в сутки.

2.3 Решение задачи ЛП средствами программного продукта Gsimplex

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

После решения задачи, можно посмотреть и изучить соответствующую теорию, которая встроена в саму программу! Достаточно лишь нажать кнопку "Теория".

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

1. Необходимо задать количество ограничений нашей задачи.

Рисунок 9 - Ввод количества ограничений задачи

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

Рисунок 10 - Форма ввода основных коэффициентов

3. Остается нажать кнопку «ОК». Решение представляется в виде графика и текстового решения.

Рисунок 11 - Вывод готового решения



Заключение

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

Во второй части курсовой работы рассмотрены примеры решения задач линейного программирования графическим методом. Первый пример не несет никакой смысловой нагрузки; второй же несет строго экономический смысл. Следует также выделить основные достоинства и недостатки графического метода. Данный метод достаточно прост и нагляден, решение задачи отображается на одном чертеже. Недостатком данного метода является его ограниченность, т.е. так можно решить задачи содержащие в прямой или двойственной форме две переменные. А большинство экономических задач содержит гораздо больше переменных, поэтому применение графического метода ограничено.

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

Таким образом цель данной курсовой работы достигнута и все поставленные задачи выполнены.



СПИСОК ИСПОЛЬЗованных источников

1. Смородинский, С.С. Оптимизация решений на основе методов и моделей математического программирования: Учебное пособие / С.С.Смородинский, Н.В. Батин. -М.: Наука, 1989.

2. Вентцель, Е.С. Исследование операций / Е.С. Вентцель. М.: 1998.

3. Кузнецов, А. В. Математическое программирование / А. В. Кузнецов.- Минск, "Вышейшая школа", 1994 «Советское радио», 1972. 552 с.

4. Муну М. Математическое программирование. Теория алгоритмов / М .Муну. -М.: Наука,1990.

5. Таха, Х. Введение в исследование операций / Х.Таха. -М.: Мир,1985.

Размещено на Allbest.ru

...