Графический метод решения задачи линейного программирования. Решение задач линейного программирования графическим методом
Графические методы связаны прежде всего с геометрическим изображением функциональной зависимости при помощи линий на плоскости. Графики используются для быстрого нахождения значения функций по соответствующему значению аргумента, для наглядного изображения функциональных зависимостей.
В экономическом анализе применяются почти все виды графиков: диаграммы сравнения, диаграммы временных рядов, кривые распределения, графики корреляционного поля, статистические картограммы. Особенно широко распространены в анализе диаграммы сравнения - для сравнения отчетных показателей с плановыми, предшествующих периодов и передовых предприятий отечественных или зарубежных. Для наглядного изображения динамики экономических явлений (а в анализе с динамическими рядами приходится иметь дело очень часто) используются диаграммы временных рядов.
С помощью координатной сетки строятся графики зависимости, например, уровня издержек от объема произведенной и реализованной продукции, а также. графики, на которых можно изображать и корреляционные связи между показателями. В системе осей координат изображение показывает влияние различных факторов на тот или иной показатель.
Широко применяется графический метод для исследования производственных процессов, организационных структур, процессов программирования и т. д. Например, для анализа эффективности использования производственного оборудования строятся расчетные графики, в том числе графики множественных факторов.
Обозначения: каждый круг считается одной из вершин графика; цифра в верхнем секторе каждой вершины означает ее порядковый номер; нз номеров двух соседних вершин складывается шифр работы; цифра в нижнем секторе каждой вершины является порядковым номером предшествующей вершины, а линия, соединяющая эти две вершины, означает определенную работу. Внизу под линией записана плановая продолжительность данной работы; цифра в левом секторе каждой вершины означает общую продолжительность всех предшествующих работ, цифра в правом секторе отличается от цифры в левом на величину резерва (запаса времени). Такнм образом, для вершин, лежащих на критическом пути, цифры в левом и правом секторах вершины совпадают, поскольку запас времени равен 0.
В математически формализованной системе анализа, планирования и управления особое место занимают сетевые графики. Они дают большой экономический эффект при строительстве и монтаже промышленных и других предприятий.
Сетевой график (рис. 6.1) позволяет выделить из всего комплекса работ наиболее важные, лежащие на критическом пути, и сосредоточить на них основные ресурсы строительномонтажных организаций, устанавливать взаимосвязь между различными специализированными организациями и координировать их работу. Работы, лежащие на критическом пути, требуют наиболее продолжительного ожидания поступления очередного события. На стадии оперативного анализа и управления сетевой график дает возможность осуществлять действенный контроль за ходом строительства, своевременно принимать меры по устранению возможных задержек в работе.
Применение сетевых графиков анализа, планирования и управления обеспечивает, как показывают многие примеры, сокращение сроков строительства на 20-30%, повышение производительности труда на 15-20%.
При анализе, осуществляемом непосредственно на стройках, использование материалов сетевого планирования и управления способствует правильному определению причин, влияющих на ход строительства, и выявлению предприятий, не обеспечивающих выполнение порученных им работ или поставку оборудования в сроки, установленные графиком.
Разработка сетевого графика в строительстве осуществляется при наличии: норм продолжительности строительства и срока ввода в действие объекта или комплекса объектов, проектно-сметной документации, проекта организации строительства и производства работ, типовых технологических карт, действующих норм затрат труда, материалов и работы машин. Кроме того, при составлении графика используются опыт выполнения отдельных работ, а также данные о производственной базе строительных и монтажных организаций.
На основе всех этих данных составляется таблица работ и ресурсов, где в технологической последовательности производства работ указываются их характеристика, объем, трудоемкость в человеко-днях, исполнитель (организация и бригада), численность рабочих, сменность, потребность в механизмах и материалах, источники их поступления, общая продолжительность выполнения работы в днях, а также предшествующее задание, после окончания которого можно начинать данную работу. Исходя из показателей такой таблицы, подготавливают сетевой график, который может иметь различную степень детализации в зависимости от принятой схемы произ
водства работ и уровня руководства; кроме общего графика исполнители разрабатывают график выполняемых ими работ.
Основные элементы сетевого графика: событие, работа, ожидание, зависимость.
При анализе хода строительства объекта следует устанавливать, правильно ли составлен сетевой график, не допущено ли при этом завышение критического пути, учтены ли при оптимизации графика все возможности его сокращения, нельзя ли какие-либо работы выполнять параллельно или сократить время, затрачиваемое на них, путем увеличения средств механизации и др. Это особенно важно в тех случаях, когда продолжительность работ по графику не обеспечивает окончание строительства в срок.
Основным материалом сетевого планирования, используемого при анализе, является информация о ходе работ по графику, который обычно составляется не реже одного раза в декаду. В качестве примера приводится карта задания и информации о ходе работы по объекту строительства, осуществляемому по сетевому графику (табл. 6.1). По данным карты, критические работы выполнялись в начале месяца с опережением графика, однако затем было допущено отставание монтажа подкрановых балок по ряду Б, а последующая работа - монтаж подкрановых балок по ряду А - закончена с отставанием на один день.
Оптимизация сетевых графиков осуществляется на стадии планирования посредством сокращения критического пути, т. е. минимизации сроков выполнения строительных работ при заданных уровнях ресурсов, минимизации уровня потребления материальных, трудовых и финансовых ресурсов при фиксированных сроках выполнения строительных работ. Возможен и смешанный подход: для одной части работ (более дорогостоящих) - минимизировать уровень потребления ресурсов при фиксированных сроках выполнения работ, для другой - минимизировать сроки при фиксированном уровне ресурсов.
Решение оптимизационных задач существенно облегчается наличием пакетов прикладных программ (ППП), приспособленных к составлению оптимальных сетевых графиков на ЭВМ.
В зарубежной практике системного анализа распространен графо-математический метод, получивший название «дерево решений». Суть этого метода заключается в следующем.
Путем предварительной оценки потребностей, предварительного анализа возможных организационных, технических или технологических условий намечаются все предполагаемые варианты решения данной задачи. Вначале разрабатываются
| | Задание | | Информация | Резерв времени по работам | Чис тый |
|||||||
| Наименование работ | шифр | дата начала | дата оконча | плановая продол | Ре зерв вре | % тех- | требуемое время для | при чина | фактическая дата | находя щимся | не находящимся | резерв времени с |
| | работ | работ (план) | ния работ (план) | житель ность, дней | мени | кой готов ности | оконча ния работ, дней | задер жки | оконча ния работ | на критическом пути | аа критическом пути | начала месяца, дней |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| Разработка грунта | 1-2 | 1/IV | 6/IV | 5 | 0 | 100 | - | - | 6/IV | ¦- | - | - |
| Бетонирование фундаментов под котлы | 2-3 | 7/IV | 17/1V | 9 | 0 | 100 | 14/IV | 2 | 2 |
|||
| Бетонирование фундаментов по ряду А | 2-4 | 7/IV | 14/1V | 7 | 2 | 100 | 14/IV | | | |
||
| То же по ряду Б | 2-5 | 7/IV | 14/IV | 7 | 2 | 100 | - | - | 14/IV | | | |
| Устройство трубной разводки | 6-18 | 18/IV | 21/IV | 4 | 19 | 100 | - | - | 29/IV | -7 |
||
| Устройство обратной засыпки | 6-7 | 18/IV | 19/IV | 2 | 0 | 100 | 17/IV | 2 | 2 |
|||
| Монтаж сборных железобетонных ко | | | | | | | | | | | | |
| лонн: по ряду Б | 7-8 | 20/IV | 22/IV | 3 | 1 | 100 | - | - | 22/IV | _ | - | - |
| по ряду А | 7-9 | 20/IV | 22/IV | 3 | 1 | 100 | - | - | 22/IV | - | - | - |
Устройство подкрановых путей и монтаж башенного крана 7-10
Установка опорных рам на фундамент под оборудование 7-16 Монтаж подкрановых балок:
по ряду Б 8-11
20/IV 24/IV 4
20/IV 24/IV 4
24/IV 25/IV 2
по ряду А 10-12 25/IV 26/IV
Монтаж первой части балок и плит покрытия 12-13 27/IV 4/V
Монтаж подкрановых путей мостового lt;3 крана 12-14 27/IV 3/V
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 0 | 100 | - | - | 22/IV | 1 | - | 1 |
| 14 | 100. | - | - | 29/IV | - | -5 | - |
| 1 | 100 | за- | 27/IV | -2 |
27/IV -1
держ- ка с поставкой ж/б конструкций
- 100 -
укрупненные варианты. Затем по мере введения дополнительных условий каждый из них расчленяется на ряд вариантов. Графическое изображение этих вариантов позволяет исключить менее выгодные из них и избрать наиболее приемлемый.
Этот метод может найти у нас применение при определении порядка обработки тех или иных деталей на нескольких станках в целях минимизации общего времени обработки; при установлении размеров ресурсов для минимизации общих производственных издержек; при распределении капиталовложений и других ресурсов по промышленным объектам; при решении транспортных и других задач.
Рассмотрим сначала простейший случай, когда в ЗЛП включены ровно две переменные:
Каждое из неравенств (a)-(b) системы ограничений задачи (3.8) геометрически определяет полуплоскость соответственно с граничными прямыми , Х 1 =0 и Х 2 =0. Каждая из граничных прямых делит плоскость х 1 Ох 2 на две полуплоскости. Все решения исходного неравенства лежат в одной из образованных полуплоскостей (все точки полуплоскости) и, следовательно, при подстановке координат любой ее точки в соответствующее неравенство обращает его в верное тождество. С учетом этого и определяется та полуплоскость, в которой лежат решения неравенства, т.е. путем выбора любой точки из какой-либо полуплоскости и подстановки ее координат в соответствующее неравенство. Если неравенство выполняется для данной точки, то оно выполняется и для любой другой точки из этой же полуплоскости. В противном случае решения неравенства лежат в другой полуплоскости.
В том случае, если система неравенств (a)-(b) совместна, то область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей выпуклое, то область допустимых решений задачи (3.8) является выпуклое множество, которое называется многоугольником решений (введённый ранее термин “многогранник решений” обычно употребляется, если n 3). Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.
Таким образом, исходная ЗЛП состоит в нахождении такой точки многоугольника решений, в которой целевая функция F принимает максимальное (минимальное) значение.
Эта точка существует тогда, когда многоугольник решений не пуст и на нём целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины строят линию уровня L: c 1 x 1 +c 2 x 2 =h (где h – некоторая постоянная), перпендикулярную вектору-градиенту и проходящую через многоугольник решений, и передвигают её параллельно вдоль вектора-градиента до тех пор, пока она не пройдёт через последнюю её общую точку пересечения с многоугольником решений (при построении вектора-градиента откладывают точку (с 1 ; с 2) в плоскости х 1 Ох 2 и проводят к ней из начала координат направленный отрезок). Координаты указанной точки и определяют оптимальный план данной задачи.
Суммируя все выше изложенное, приведем алгоритм графического метода решения ЗЛП.
Алгоритм графического метода решения ЗЛП
1. Построить многоугольник решений, задаваемый системой ограничений исходной ЗЛП.
2. Если построенный многоугольник решений – пустое множество, то исходная ЗЛП решений не имеет. В противном случае построить вектор-градиент и провести произвольную линию уровня L, перемещая которую при решении задачи на максимум в направлении вектора (или в обратном направлении для задачи на минимум) определить крайнюю точку многоугольника решений, где и достигается максимум (минимум) целевой функции задачи.
3. Вычислить координаты найденной оптимальной точки 
, решив систему уравнений двух граничных прямых, пересекающихся в ней.
4. Подстановкой найденного оптимального решения в целевую функцию задачи вычислить оптимальное ее значение, т.е.: 
.
При графическом построении множества допустимых решений ЗЛП (многоугольника решений) возможны следующие ситуации.
Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции F*(X) = -F(X) . Также имеется возможность составить двойственную задачу .Решение происходит в три этапа:
- Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b (F(X) → extr) сводится к виду ax = b , F(X) → max ;
- Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
- Решение симплексным методом;
Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .
Переход от задачи минимизации целевой функции к задаче максимизации
Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .Проиллюстрируем этот факт графически:
| F(x) → min
|
F(x) → max
 |
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).
Ведущий (разрешающий) элемент
– коэффициент свободной неизвестной, которая становится базисной, а сам коэффициент преобразуется в единицу.
Направляющая строка
– строка ведущего элемента, в которой расположена с единичным коэффициентом базисная неизвестная, исключаемая при преобразовании (строка с минимальным предельным коэффициентом, см. далее).
Направляющий столбец
– столбец ведущего элемента, свободная неизвестная которого переводится в базисную (столбец с максимальной выгодой, см. далее).
Переменные x 1 , …, x m , входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми - в остальные, называются базисными
или зависимыми
. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса-Жордана . Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (x m +1 ,…, x n) называются небазисными
или независимыми переменными
.
Базисное решение
называется допустимым базисным решением
, если значения входящих в него базисных переменных x j ≥0, что эквивалентно условию неотрицательности b j ≥0.
Допустимое базисное решение является угловой точкой
допустимого множества S задачи линейного программирования и называется иногда опорным планом
.
Если среди неотрицательных чисел b j есть равные нулю, то допустимое базисное решение называется вырожденным
(вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной
.
Пример №1
. Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x 1 + 2x 2 - 2x 3 → min при ограничениях:
4x 1 + 3x 2 - x 3 ≤10
- 2x 2 + 5x 3 ≥3
x 1 + 2x 3 =9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x 4 ; во втором неравенстве смысла (≥) вводим базисную переменную x 5 со знаком минус.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x 1 + 0x 2 + 2x 3 + 0x 4 + 0x 5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Переход к СЗЛП
.
Расширенная матрица системы ограничений-равенств данной задачи:
| 4 | 3 | -1 | 1 | 0 | 10 |
| 0 | -2 | 5 | 0 | -1 | 3 |
| 1 | 0 | 2 | 0 | 0 | 9 |
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x 4 .
2. В качестве базовой переменной выбираем x 2 .
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x 2 , получена в результате деления всех элементов строки x 2 на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 2 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
| 4-(0 3):-2 | 3-(-2 3):-2 | -1-(5 3):-2 | 1-(0 3):-2 | 0-(-1 3):-2 | 10-(3 3):-2 |
| 0: -2 | -2: -2 | 5: -2 | 0: -2 | -1: -2 | 3: -2 |
| 1-(0 0):-2 | 0-(-2 0):-2 | 2-(5 0):-2 | 0-(0 0):-2 | 0-(-1 0):-2 | 9-(3 0):-2 |
Получаем новую матрицу:
| 4 | 0 | 6 1 / 2 | 1 | -1 1 / 2 | 14 1 / 2 |
| 0 | 1 | -2 1 / 2 | 0 | 1 / 2 | -1 1 / 2 |
| 1 | 0 | 2 | 0 | 0 | 9 |
3. В качестве базовой переменной выбираем x 3 .
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x 3 , получена в результате деления всех элементов строки x 3 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 3 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
| 4-(1 6 1 / 2):2 | 0-(0 6 1 / 2):2 | 6 1 / 2 -(2 6 1 / 2):2 | 1-(0 6 1 / 2):2 | -1 1 / 2 -(0 6 1 / 2):2 | 14 1 / 2 -(9 6 1 / 2):2 |
| 0-(1 -2 1 / 2):2 | 1-(0 -2 1 / 2):2 | -2 1 / 2 -(2 -2 1 / 2):2 | 0-(0 -2 1 / 2):2 | 1 / 2 -(0 -2 1 / 2):2 | -1 1 / 2 -(9 -2 1 / 2):2 |
| 1: 2 | 0: 2 | 2: 2 | 0: 2 | 0: 2 | 9: 2 |
Получаем новую матрицу:
| 3 / 4 | 0 | 0 | 1 | -1 1 / 2 | -14 3 / 4 |
| 1 1 / 4 | 1 | 0 | 0 | 1 / 2 | 9 3 / 4 |
| 1 / 2 | 0 | 1 | 0 | 0 | 4 1 / 2 |
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
3 / 4 x 1 + x 4 - 1 1 / 2 x 5 = -14 3 / 4
1 1 / 4 x 1 + x 2 + 1 / 2 x 5 = 9 3 / 4
1 / 2 x 1 + x 3 = 4 1 / 2
Выразим базисные переменные через остальные:
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4
x 3 = - 1 / 2 x 1 +4 1 / 2
Подставим их в целевую функцию:
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
или
Система неравенств:
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4 ≥ 0
- 1 / 2 x 1 +4 1 / 2 ≥ 0
Приводим систему неравенств к следующему виду:
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 5 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 5 -10 1 / 2 → max
Упростим систему.
3 / 4 x 1 - 1 1 / 2 x 2 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 2 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → max
Пример №2
. Найдите сначала графическим методом, а затем симплекс-методом решение задачи
F(X) = x 1 + x 2 - x 3 + x 5 +15 → max (min) при ограничениях:
-3x 1 + x 2 + x 3 =3
4x 1 + 2x 2 - x 4 =12
2x 1 - x 2 + x 5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0
В линейном программировании используется графический метод, с помощью которого определяют выпуклые множества (многогранник решений). Если основная задача линейного программирования имеет оптимальный план, то целевая функция принимает значение в одной из вершин многогранника решений (см. рисунок).
Назначение сервиса . С помощью данного сервиса можно в онлайн режиме решить задачу линейного программирования геометрическим методом, а также получить решение двойственной задачи (оценить оптимальность использования ресурсов). Дополнительно создается шаблон решения в Excel .
Инструкция . Выберите количество строк (количество ограничений).
Если количество переменных больше двух, необходимо систему привести к СЗЛП (см. пример и пример №2). Если ограничение двойное, например, 1 ≤ x 1 ≤ 4 , то оно разбивается на два: x 1 ≥ 1 , x 1 ≤ 4 (т.е. количество строк увеличивается на 1).Построить область допустимого решения (ОДР) можно также с помощью этого сервиса .
Вместе с этим калькулятором также используют следующие:
Симплексный метод решения ЗЛП
Решение транспортной задачи
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Экстремум функции двух переменных
Вычисление пределов
Решение задачи линейного программирования графическим методом включает следующие этапы :
- На плоскости X 1 0X 2 строят прямые.
- Определяются полуплоскости.
- Определяют многоугольник решений;
- Строят вектор N(c 1 ,c 2), который указывает направление целевой функции;
- Передвигают прямую целевую функцию c 1 x 2 + c 2 x 2 = 0 в направлении вектора N до крайней точки многоугольника решений.
- Вычисляют координаты точки и значение целевой функции в этой точке.
Пример
. Компания изготавливает два вида продукции - П1 и П2. Для производства продукции используются два вида сырья - С1 и С2. Оптовые цены единицы продукции равна: 5 д.е. для П1 и 4 д.е. для П2. Расход сырья на единицу продукции вида П1 и вида П2 дан в таблице.
Таблица - Расход сырья на производство продукции
Требуется определить:
Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным?
- Сформулировать математическую модель задачи линейного программирования.
- Решить задачу линейного программирования графическим способом (для двух переменных).
Сформулируем математическую модель задачи линейного программирования.
x 1 - производство продукции П1, ед.
x 2 - производство продукции П2, ед.
x 1 , x 2 ≥ 0
Ограничения по ресурсам
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
Ограничения по спросу
x 1 +1 ≥ x 2
x 2 ≤ 2
Целевая функция
5x 1 + 4x 2 → max
Тогда получаем следующую ЗЛП:
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
x 2 - x 1 ≤ 1
x 2 ≤ 2
x 1 , x 2 ≥ 0
5x 1 + 4x 2 → max
