1
Нахождение максимума целевой функции
Мы используем модель, построенную для компании Reddy Mikks, чтобы показать оба этапа графического решения задачи ЛП.
Этап 1. Построение пространства допустимых решений.
Сначала проведем оси: на горизонтальной будут указываться значения переменнойx1 , а
на вертикальной — x2 . Далее рассмотрим условие неотрицательности переменных: x1 0 и x2 0. Эти два ограничения показывают, что пространство допустимых решений будет лежать в первом квадранте.
Чтобы учесть оставшиеся ограничения заменим неравенства на равенства, в результате чего получим уравнения прямых, а затем на плоскости проведем эти прямые.
Теперь рассмотрим, как графически интерпретируются неравенства. Каждое неравенство делит плоскость x1,x2 на два полупространства, которые располагаются по обе стороны прямой, которая соответствует данному неравенству. Точки плоскости,
расположенные по одну сторону прямой, удовлетворяют неравенству (допустимое полупространство), а точки, лежащие по другую сторону, — нет. “Тестовой” точкой,
проверяющей, точки какого полупространства удовлетворяют неравенству, а какого — нет,
может служить точка (0, 0). Например, эта точка удовлетворяет первому неравенству
6x1 4x2 24 (здесь 6*0 + 4*0 = 0 < 24). Это означает, что точки полупространства,
содержащего начальную точку (0,0), удовлетворяют этому неравенству. На рис. 1
допустимые полупространства показаны стрелочками.
Рис. 1
В том случае, когда точка (0,0) не удовлетворяет неравенству, допустимым полупространством будет то, которое не содержит эту точку. Если же прямая проходит через эту точку, следует в качестве “тестовой” взять какую-либо другую точку.
Этап 2. Нахождение оптимального решения.
Точки пространства допустимых решений, показанного на рис. 1, удовлетворяют
2
одновременно всем ограничениям. Это пространство ограничено отрезками прямых, которые соединяются в угловых точках А, В, С, D, Е и F. Любая точка, расположенная внутри или на границе области, ограниченной ломаной ABCDEF, является допустимым решением, т.е.
удовлетворяет всем ограничениям. Поскольку пространство допустимых решений содержит бесконечное число точек, необходима некая процедура поиска оптимального решения.
Нахождение оптимального решения требует определения направления возрастания целевой функции z 5x1 4x2 . Мы можем приравнять z к нескольким возрастающим значениям, например 10 и 15. Эти значения, подставленные вместо z в выражение целевой функции, порождают уравнения прямых; для значений 10 и 15 получаем уравнения прямых
5x1 4x2 10 и 5x1 4x2 15. На рис. 2 эти прямые показаны штриховыми линиями, а
направление возрастания целевой функции — толстой стрелкой. Целевая функция может возрастать до тех пор, пока прямые, соответствующие возрастающим значениям этой функции, пересекают область допустимых решений. Точка пересечения области допустимых решений и прямой, соответствующей максимально возможному значению целевой функции,
и будет точкой оптимума.
Рис. 2
На рис. 2 видно, что оптимальное решение соответствует точке С. Эта точка является местом пересечения прямых (1) и (2), поэтому ее координаты x1 и х2 находятся как решение системы уравнений, задающих эти прямые:
6x1 4x2 24
x1 2x2 6
Решением этой системы будет х1 = 3 и х2 = 1.5, при этом значение целевой функции равно z = 21. Полученное решение означает, что для компании Reddy Mikks оптимальным выбором будет ежедневное производство 3 т краски для наружных работ и 1.5 т — для внутренних работ с ежедневным доходом в 21 000.
В линейном программировании используется графический метод, с помощью которого определяют выпуклые множества (многогранник решений). Если основная задача линейного программирования имеет оптимальный план, то целевая функция принимает значение в одной из вершин многогранника решений.
Если что-то непонятно — вы всегда можете написать мне в WhatsApp и я вам помогу!
Введение в графический метод
Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.
Возможно эта страница вам будет полезна:
Задача линейного программирования в стандартной форме с двумя переменными имеет вид:
Эти задачи допускают простое геометрическое истолкование.
Рассмотрим вначале геометрическое истолкование системы ограничений задачи. Каждую совокупность значений переменных 
можно изобразить точкой на плоскости, если ввести систему координат и по одной оси откладывать 
, а по другой 
. Выясним, что геометрически означает совокупность решений одного отдельно взятого неравенства:
Рассмотрим прямую на плоскости с уравнением:
Эта прямая делит плоскость на две полуплоскости, в одной из которых справедливо наше неравенство, а в другой — противоположное. Для того чтобы проверить, какая из полуплоскостей состоит из решений нашего неравенства, следует взять точку из какой-либо полуплоскости и проверить, выполняется ли наше неравенство в этой точке. Множество решений отдельно взятого линейного неравенства представляет собой полуплоскость. Для системы из нескольких таких неравенств точки, координаты которых удовлетворяют всем неравенствам одновременно, должны находиться во всех соответствующих полуплоскостях, т. е. принадлежать теоретико-множественному пересечению этих полуплоскостей. Множество точек на плоскости, удовлетворяющих системе ограничений, составляет, таким образом, некоторую выпуклую многоугольную область (область допустимых решений). Условия неотрицательности переменных 
приводят к тому, что эта область находится в первой координатной четверти.
При решении двумерных задач линейного программирования возможны следующие ситуации (ОДР — область допустимых решений):
Таким образом, исходная задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция 
принимает максимальное значение. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим линию уровня 
(где 
— некоторая постоянная), проходящую через многоугольник решений, и будем передвигать ее в направлении вектора 
до тех пор, пока она не пройдет через последнюю ее общую точку с многоугольником решений. Координаты указанной точки и определяют оптимальный план данной задачи.
Отметим, что при нахождении решения задачи (5.1)-(5.3) могут встретиться случаи, изображенные на рис. 5.2- 5.5. Рис.5.2 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке 
. Из рис. 5.3 видно, что максимальное значение целевая функция принимает в любой точке отрезка 
. На рис.5.4 изображен случай, когда целевая функция неограничена сверху на множестве допустимых решений, а на рис.5.5 — случай, когда система ограничений задачи несовместна, т. е. если система неравенств (5.1) при условии (5.2) не имеет решений.
Также отметим, что нахождение минимального значения линейной функции при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня передвигается не в направлении вектора , а в противоположном направлении.
Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минимального значения.
Алгоритм графического метода решении задач линейного программирования
- Построить область допустимых решений.
- Если область допустимых решений является пустым множеством, то задача не имеет решения ввиду несовместности системы ограничений.
- Если область допустимых решений является непустым множеством, построить нормаль линий уровня
и одну из линий уровня, имеющую общие точки с этой областью. - Линию уровня переместить до опорной прямой в задаче на максимум в направлении нормали, в задаче на минимум — в противоположном направлении.
- Если при перемещении линии уровня по области допустимых решений в направлении, соответствующем приближению к экстремуму целевой функции, линия уровня уходит в бесконечность, то задача не имеет решения ввиду неограниченности целевой функции.
- Если задача линейного программирования имеет оптимальное решение, то для его нахождения решить совместно уравнения прямых, ограничивающих область допустимых решений и имеющих общие точки с соответствующей опорной прямой. Если целевая функция задачи достигает экстремума в двух угловых точках, то задача имеет бесконечное множество решений. Оптимальным решением является любая выпуклая линейная комбинация этих точек. После нахождения оптимальных решений вычислить значение целевой функции на этих решениях.
и одну из линий уровня, имеющую общие точки с этой областью.Пример задачи №1
Пусть имеется два станка 
, на каждом из которых можно производить два вида продукции 
. Станок 
производит единицу продукции 
за 1 час, а единицу продукции 
— за 2 часа. Станок 
затрачивает на единицу продукции — 2 часа, а на единицу продукции — 1 час. Станок может работать в сутки не более 10 ч., а станок — не более 8 ч. Стоимость единицы продукции составляет 
руб., а стоимость единицы продукции — 
руб. Требуется определить такие объемы выпуска продукции и на станок, чтобы выручка от реализации производственной продукции была максимальной.
Решение:
Для наглядности сведем условие задачи в таблицу 5.1.
Составим математическую модель задачи. Обозначим через и количества продукции и , которые планируется произвести на каждом отдельном станке. Стоимость произведенной продукции 
. Мы должны назначить и так, чтобы величина была максимальной.
Переменные не могут принимать произвольных значений. Их значения ограничены условиями производства, а именно тем, что станки могут работать ограниченное время. На изготовление продукции станок тратит 
часов, а на изготовление продукции 
часов. Поскольку время работы станка не превосходит 10 ч, то величины и должны удовлетворять неравенству:
Аналогично можно получить неравенство для станка 
. Кроме того, величины и не могут быть отрицательными:
по смыслу задачи. Такие задачи кратко записываются следующим образом:
Итак, математическая модель задачи: найти такой план выпуска продукции 
, удовлетворяющий системе (5.4) и условию (5.5), при котором функция (5.6) принимает максимальное значение.
Решения, удовлетворяющие системе ограничений (5.4) и требованиям неотрицательности (5.5), являются допустимыми, а решения, удовлетворяющие одновременно и требованию (5.6) — оптимальными.
Рассмотрим геометрическое истолкование задачи:
Возьмем 
и 
.
Математическая модель задачи:
Построение области допустимых решений целевой функции :
1.Построим прямоугольную систему координат. Так как, и неотрицательны, то можно ограничиться рассмотрением первого квадранта.
Рассмотрим первое ограничение:
Рассмотрим второе ограничение:
Отложим полученные точки на числовых осях и найдем полуплоскости, которые соответствуют данным ограничениям.
Двумерные задачи линейного программирования решаются графически.
Для случая 
можно рассмотреть трехмерное пространство и целевая функция будет достигать своего оптимального значения в одной из вершин многогранника.
В общем виде, когда в задаче участвуют 
неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в 
-мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах.
Для решения ЗЛП любой размерности существует универсальный способ решения задач линейного программирования, называемый симплекс-методом.
Графический метод решения задач линейного программирования
Множество решений системы ограничений задачи ЛП образует область допустимых решений (ОДР).
Графический метод решения задач ЛП основывается на возможности графического изображения ОДР и нахождении среди них оптимального решения. Этот метод применяется для задач ЛП с одной, двумя или тремя переменными, для которых система ограничений стандартна (состоит из неравенств), и задач со многими переменными, для которых система ограничений содержит переменных и 
или 
линейно независимых уравнений.
ОДР задачи строится как пересечение областей решений каждого из ограничений и представляет собой выпуклый многогранник (многоугольник, интервал). Область допустимых решений может содержать бесконечное число точек. Для того чтобы найти решение ЗЛП, нужно рассмотреть поведение целевой функции в ОДР.
I. Одномерное пространство переменных
Решение системы ограничений есть пересечение лучей, что определяет интервал решений (ОДР): точку, отрезок, луч или всю числовую прямую.
Значения целевой функции в угловых точках интервала решений определяют наименьшее (наибольшее) значение исследуемой целевой функции, монотонно убывающей (если 
) или монотонно возрастающей (если 
).
В случае неограниченности ОДР задача ЛП может и не иметь оптимума.
II. Двумерное пространство переменных
Областью решений линейного неравенства
является одна из полуплоскостей, на которые прямая делит всю координатную плоскость. Для того, чтобы определить, какая из двух координатных полуплоскостей является областью допустимых решений неравенства, достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство: если оно удовлетворяется, то областью решений является полуплоскость, содержащая данную точку; если же неравенство не удовлетворяется, то областью решений является полуплоскость, не содержащая данную точку.
Решение системы ограничений есть пересечение полуплоскостей с граничными прямыми
многоугольник решений (ОДР).
Линией уровня называется прямая, на которой целевая функция задачи принимает постоянное значение. Уравнение
задаёт семейство линий уровня исследуемой целевой функции 
— параллельные прямые с нормальным вектором 
, который определяет направление роста функции 
, т. к. является её градиентом.
Замечание.
Т. о., если линию уровня 
перемещать параллельно самой себе в направлении вектора нормали, то значение целевой функции будет увеличиваться; если линию уровня перемещать параллельно самой себе в направлении противоположном вектору нормали, то значение целевой функции будет уменьшаться. Поскольку требуется найти оптимальное решение, при котором целевая функция стремится к максимуму или минимуму, то необходимо перемещать линию уровня до положения касания с ОДР (положения опорной прямой).
• Прямая
имеющая с многоугольником решений, расположенным по одну сторону от неё, хотя бы одну общую точку, называется опорной. ОДР любой задачи имеет не более двух опорных прямых, на одной из которых может находиться оптимальное решение.
Значение 
есть экстремальное значение исследуемой целевой функции.
Графически опорная прямая определяет оптимум целевой функции в угловой точке многоугольника решений. Поэтому перебором значений целевой функции во всех угловых точках можно так же выбрать искомый оптимум.
Замечание. Если заданы ограничения неотрицательности переменных, то все построения проводятся в первой четверти.
Особые случаи
Алгоритм графического метода решения задач линейного программирования с двумя переменными
- Находим область допустимых решений из системы ограничений. Если ОДР является пустым множеством, то задача ЛП неразрешима (не имеет решения) в виду несовместности системы ограничений.
- Если область допустимых решений является непустым множеством, строим направляющий вектор прямой и параллельно ему проводим линию уровня .
- Строим вектор нормали перпендикулярно прямой .
- Линию уровня перемещаем до положения опорной прямой в направлении вектора для задач на максимум или в направлении, противоположном для задач на минимум. Т. е. перемещение проводится до тех пор, пока линия уровня не коснется области допустимых решений. Общая точка (точки) будет точкой экстремума (оптимума) целевой функции в ОДР.
- Находим координаты точки экстремума и значение целевой функции в ней, т. е. оптимум задачи ЛП.
прямой 
и параллельно ему проводим линию уровня 
перпендикулярно прямой Пример задачи №2
Найти 
, при котором функция достигает экстремума:
если имеются ограничения:
Решение:
Система ограничений определяет граничные прямые:
С учётом исходной системы неравенств строим ОДР.
Прямая
имеет вектор нормали 
(5;4) и направляющий вектор 
(-4;5). Опорное положение максимума линия уровня функции 
занимает в точке 
(направление роста вектора нормали); в точке 
— опорное положение минимального значения линия уровня функции.
Т. о. имеем:
Тогда
Ответ:
Пример задачи №3
Найти план
при котором:
Решение:
Строим ОДР, проводим линии уровня :
и вектор = (4; 2). Т. к. решается задача на отыскание минимума функции, то фиксируем положение опорной прямой в направлении, противоположном вектору . В результате опорная прямая совпадает с граничной прямой 
и проходит через две угловые точки 
и 
. Задача имеет бесконечно много оптимальных решений, являющихся точками отрезка 
.
Общее решение (выпуклая линейная комбинация точек отрезка ) имеет вид:
Вычисляем
Ответ:
Пример задачи №4
Найти план
при котором
Решение:
Строим ОДР, проводим линию уровня :
и вектор = (3;7). В данной задаче необходимо найти максимум целевой функции, поэтому линию уровня фиксируем в направлении нормального вектора. В виду того, что в направлении вектора нормали ОДР не ограничена, линия уровня уходит в бесконечность, т. е. max 
Таким образом, задача ЛП не имеет решения в виду неограниченности целевой функции.
Пример задачи №5
Найти план
при котором
Решение:
Строим прямые линии, соответствующие неравенствам системы ограничений и находим полуплоскости, являющиеся областями решений этих неравенств. Область допустимых решений задачи является пустым множеством. Задача не имеет решения в виду несовместности системы ограничений.
III. Трёхмерное пространство переменных
Решение системы ограничений — многогранник решений (ОДР) — пересечение полупространств с граничными плоскостями
Уравнение
задаёт семейство поверхностей уровня функции 
, т.е. параллельных плоскостей с нормальным вектором 
, который определяет направление роста целевой функции 
, т. к. является её градиентом.
Плоскость
имеющая с многогранником решений, расположенным по одну сторону от нее, хотя бы одну общую точку, называется опорной. Значение 
есть экстремальное (оптимальное) значение целевой функции.
Графический метод в виду большой размерности реальных практических задач ЛП достаточно редко применяется, однако он позволяет уяснить одно из основных свойств ЛП- если в задаче ЛП существует оптимальное решение, то, по крайней мере, одна из вершин допустимой области определяет собой оптимальное решение.
IV. С помощью графического метода может быть решена основная ЗЛП, система ограничений (уравнений) которой удовлетворяет условию 
где 
— число неизвестных системы, 
— ранг системы. Если уравнения системы ограничений линейно независимы, то ранг равен числу уравнений системы 
.
Основной случай: система ограничений содержит переменных и 
линейно независимых уравнения:
Расширенную матрицу системы с помощью элементарных преобразований строк можно привести к виду:
Тогда соответствующая система уравнений примет вид:
Выражая базисные неизвестные 
и учитывая их неотрицательность, получим систему неравенств с неизвестными 
:
Подставляя полученные выражения для базисных неизвестных в целевую функцию, получим:
Преобразованная задача ЛП содержит только два неизвестных. Следовательно, возможен графический способ её решения на плоскости.
Найденное решение 
подставляют в систему (*) и получают искомый оптимальный план
При этом оптимум:
Пример. Решить задачу ЛП:
Решение. Метод применим,так как 
. Методом Жордана-Гаусса приведём систему уравнений ограничений задачи к равносильной путём выделения базисных и свободных переменных. Одновременно исключим базисные переменные из целевой функции.
Используя последнюю часть табл., запишем задачу ЛП в преобразованном виде:
Отбросим в уравнениях-ограничениях неотрицательные базисные переменные 
, и заменим знаки равенства знаками неравенства 
.
Получим вспомогательную задачу ЛП с двумя переменными:
Решаем задачу графическим методом. Свободный член 22 в целевой функции не влияет на отыскание оптимального решения и учитывается только при вычислении значения целевой функции.
Находим оптимальное решение вспомогательной задачи 
:
Вычисляем минимальное значение целевой функции
Находим оптимальное решение исходной задачи:
Т. о., получаем:
Возможно эти страницы вам будут полезны:
- Решение задач по математическому программированиюПримеры решения задач по математическому программированиюЗаказать работу по математическому программированиюПомощь по математическому программированиюЗадачи математического программированияЗадача линейного программированияРешение задач по линейному программированиюМетоды решения задач линейного программированияГрафическое решение задач линейного программированияЗаказать работу по линейному программированиюПомощь по линейному программированиюКонтрольная работа по линейному программированиюЛинейное программирование в ExcelКурсовая работа по линейному программированию
Задача 1 Найти максимальное значение целевой функции F = 4 x 1+3 x 2 → max, при системе ограничений: 3 x 1+2 x 2≤ 16 (1) 2 x 1+3 x 2≤ 18 (2) x 1≥ 0 (3) x 2≥ 0 (4) где x 1, x 1 – целые числа. Построим область допустимых решений, т. е. решим графически систему неравенств (для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи F = 4 x 1+3 x 2 → max. Построим прямую, отвечающую значению функции F = 0: F = 4 x 1+3 x 2 = 0. Поскольку нас интересует максимальное решение, поэтому будем двигать прямую параллельным образом до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Задача 1 x 1 = 2. 4, x 2 = 4. 4
Область допустимых решений представляет собой многоугольник. Прямая F(x) = const пересекает область в точке C, которая получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых: 3 x 1+2 x 2≤ 16 2 x 1+3 x 2≤ 18 Решив систему уравнений, получим: x 1 = 2. 4, x 2 = 4. 4 Откуда найдем максимальное значение целевой функции: F(X) = 4*2. 4 + 3*4. 4 = 22. 8 Оптимальное значение переменной x 1=2. 4 оказалось нецелочисленным.
Разбиваем задачу 1 на две подзадачи 11 и 12. В первой из них к условиям задачи 11 добавляется условие х1 ≥ 3, а к задаче 12 — условие х1 ≤ 2. Эта процедура называется ветвлением по переменной х1. Решим графически задачу 11 как задачу ЛП. 3 x 1+2 x 2≤ 16 (1) 2 x 1+3 x 2≤ 18 (2) x 1≥ 3 (3) x 1≥ 0 (4) x 2≥ 0 (5) Область допустимых решений представляет собой треугольник.
Прямая F(x) = const пересекает область в точке B. (получена в результате пересечения прямых (1) и (3)), ее координаты удовлетворяют уравнениям этих прямых: 3 x 1+2 x 2≤ 16 x 1≥ 3 Решив систему уравнений, получим: x 1 = 3, x 2 = 3. 5 Откуда найдем максимальное значение целевой функции: F(X) = 4*3 + 3*3. 5 = 22. 5
x 1 = 3, x 2 = 3. 5 задача 11
Решим графически задачу 12 как задачу ЛП. 3 x 1+2 x 2≤ 16 (1) 2 x 1+3 x 2≤ 18 (2) x 1≤ 2 (3) x 1≥ 0 (4) x 2≥ 0 (5) Область допустимых решений представляет собой многоугольник. Прямая F(x) = const пересекает область в точке D, которая получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых: 2 x 1+3 x 2≤ 18 x 1≤ 2 Решив систему уравнений, получим: x 1 = 2, x 2 = 4. 6667 Откуда найдем максимальное значение целевой функции: F(X) = 4*2 + 3*4. 6667 = 22
задача 12 x 1 = 2, x 2 = 4. 6667
Оптимальное значение переменной x 2=3. 5 оказалось нецелочисленным. Разбиваем задачу 11 на две подзадачи 111 и 112. В первой из них к условиям задачи 111 добавляется условие х2 ≥ 4, а к задаче 112 — условие х2 ≤ 3. Решим графически задачу 111 как задачу ЛП. 3 x 1+2 x 2≤ 16 (1) 2 x 1+3 x 2≤ 18 (2) x 1≥ 3 (3) x 2≥ 4 (4) x 1≥ 0 (5) x 2≥ 0 (6) Задача не имеет допустимых решений. ОДР представляет собой пустое множество (рис. б).
Многоугольные области: а – ограниченное множество; б – пустое множество; в – неограниченное множество
Задача 111 не имеет решения, поэтому для нее процесс ветвления прерываем. Решим графически задачу 112 как задачу ЛП 3 x 1+2 x 2≤ 16 2 x 1+3 x 2≤ 18 x 1≥ 3 x 2≤ 3 x 1≥ 0 x 2≥ 0 (1) (2) (3) (4) (5) (6)
Область допустимых решений представляет собой многоугольник Прямая F(x) = const пересекает область в точке C, которая получена в результате пересечения прямых (1) и (4), ее координаты удовлетворяют уравнениям этих прямых 3 x 1+2 x 2≤ 16 x 2≤ 3 Решив систему уравнений, получим: x 1 = 3. 3333, x 2 = 3 Откуда найдем максимальное значение целевой функции: F(X) = 4*3. 3333 + 3*3 = 22. 3333
Оптимальное значение переменной x 1=3. 33 оказалось нецелочисленным. Разбиваем задачу 112 на две подзадачи 1121 и 1122. В первой из них к условиям задачи 1121 добавляется условие х1 ≥ 4, а к задаче 1122 — условие х1 ≤ 3. Решим графически задачу 1121 как задачу ЛП. 3 x 1+2 x 2≤ 16 2 x 1+3 x 2≤ 18 x 1≥ 3 x 2≤ 3 x 1≥ 4 x 1≥ 0 x 2≥ 0 (1) (2) (3) (4) (5) (6) (7)
Область допустимых решений представляет собой треугольник. Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (5), то ее координаты удовлетворяют уравнениям этих прямых: 3 x 1+2 x 2≤ 16 x 1≥ 4 Решив систему уравнений, получим: x 1 = 4, x 2 = 2 Откуда найдем максимальное значение целевой функции: F(X) = 4*4 + 3*2 = 22
Решение задачи получилось целочисленным. Новое значение текущего рекорда будет равно F(X) = 22. Так как найденная точка является первым целочисленным решением, то ее и соответствующее ей значение ЦФ следует запомнить. Сама точка называется текущим целочисленным рекордом или просто рекордом, а оптимальное значение целочисленной задачи — текущим значением рекорда. Это значение является нижней границей оптимального значения исходной задачи Z*. Решим графически задачу 1122 как задачу ЛП.
Сведем систему ограничений к следующему виду: 3 x 1+2 x 2≤ 16 2 x 1+3 x 2≤ 18 x 1≥ 3 x 2≤ 3 x 1≥ 0 x 2≥ 0 (1) (2) (3) (4) (5) (6) (7) 3 x 1+2 x 2≤ 16 (1) 2 x 1+3 x 2≤ 18 (2) x 1=3 (3) x 2≤ 3 (4) x 1≥ 0 (5) x 2≥ 0 (6)
Область допустимых решений представляет собой одну точку. Прямая F(x) = const пересекает область в точке B, которая получена в результате пересечения прямых (3) и (4), то ее координаты удовлетворяют уравнениям этих прямых: x 1=3 x 2≤ 3 Решив систему уравнений, получим: x 1 = 3, x 2 = 3 Откуда найдем максимальное значение целевой функции: F(X) = 4*3 + 3*3 = 21 Текущий рекорд Z = 22 ≥ 21, поэтому прекращаем ветвление из этой вершины
![22, 8 [2, 4; 4, 4] 22, 5 [3; 3, 5] пусто 12 11](https://present5.com/presentation/140128842_283929754/image-26.jpg "22, 8 [2, 4; 4, 4] 22, 5 [3; 3, 5] пусто 12 11")
22, 8 [2, 4; 4, 4] 22, 5 [3; 3, 5] пусто 12 11 111 22, 0 [4; 2] 1 1121 22, 3 [3, 3; 3] 1122 21, 0 [3; 3]
Для первой вершины оптимальное значение переменной x 2=4. 4 оказалось нецелочисленным. Разбиваем задачу 1 на две подзадачи 11 и 12. В первой из них к условиям задачи 11 добавляется условие х2 ≥ 5, а к задаче 12 — условие х2 ≤ 4. Эта процедура называется ветвлением по переменной х2.
Решим графически задачу 11 как задачу ЛП. 3 x 1+2 x 2≤ 16 (1) 2 x 1+3 x 2≤ 18 (2) x 2≥ 5 (3) x 1≥ 0 (4) x 2≥ 0 (5)
Область допустимых решений представляет собой треугольник. Прямая F(x) = const пересекает область в точке C, еоторая получена в результате пересечения прямых (2) и (3), ее координаты удовлетворяют уравнениям этих прямых: 2 x 1+3 x 2≤ 18 x 2≥ 5 Решив систему уравнений, получим: x 1 = 1. 5, x 2 = 5 Откуда найдем максимальное значение целевой функции: F(X) = 4*1. 5 + 3*5 = 21
Текущий рекорд Z=22≥ 21, поэтому прекращаем ветвление из этой вершины
Решим графически задачу 12 как задачу ЛП. 3 x 1+2 x 2≤ 16 (1) 2 x 1+3 x 2≤ 18 (2) x 2≤ 4 (3) x 1≥ 0 (4) x 2≥ 0 (5)
Область допустимых решений представляет собой многоугольник Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых: 3 x 1+2 x 2≤ 16 x 2≤ 4 Решив систему уравнений, получим: x 1 = 2. 6667, x 2 = 4 Откуда найдем максимальное значение целевой функции: F(X) = 4*2. 6667 + 3*4 = 22. 6667
Оптимальное значение переменной x 1=2. 67 оказалось нецелочисленным. Разбиваем задачу 12 на две подзадачи 121 и 122. В первой из них к условиям задачи 121 добавляется условие х1 ≥ 3, а к задаче 122 — условие х1 ≤ 2. Решим графически задачу 121 как задачу ЛП. 3 x 1+2 x 2≤ 16 (1) 2 x 1+3 x 2≤ 18 (2) x 2≤ 4 (3) x 1≥ 3 (4) x 1≥ 0 (5) x 2≥ 0 (6)
Область допустимых решений представляет собой треугольник. Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (4), то ее координаты удовлетворяют уравнениям этих прямых: 3 x 1+2 x 2≤ 16 x 1≥ 3 Решив систему уравнений, получим: x 1 = 3, x 2 = 3. 5 Откуда найдем максимальное значение целевой функции: F(X) = 4*3 + 3*3. 5 = 22. 5
Решим графически задачу 122 как задачу ЛП. 3 x 1+2 x 2≤ 16 (1) 2 x 1+3 x 2≤ 18 (2) x 2≤ 4 (3) x 1≤ 2 (4) x 1≥ 0 (5) x 2≥ 0 (6)
Область допустимых решений представляет собой многоугольник Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (3) и (4), то ее координаты удовлетворяют уравнениям этих прямых: x 2≤ 4 x 1≤ 2 Решив систему уравнений, получим: x 1 = 2, x 2 = 4 Откуда найдем максимальное значение целевой функции: F(X) = 4*2 + 3*4 = 20
Текущий рекорд Z=22≥ 20, поэтому прекращаем ветвление из этой вершины Оптимальное значение переменной x 2=3. 5 оказалось нецелочисленным. Разбиваем задачу 121 на две подзадачи 1211 и 1212. В первой из них к условиям задачи 1211 добавляется условие х2 ≥ 4, а к задаче 1212 — условие х2 ≤ 3.
Решим графически задачу 1211 как задачу ЛП 3 x 1+2 x 2≤ 16 2 x 1+3 x 2≤ 18 x 2≤ 4 x 1≥ 3 x 2≥ 4 x 1≥ 0 x 2≥ 0 (1) (2) (3) (4) (5) (6) (7) Сведем систему ограничений к следующему виду: 3 x 1+2 x 2≤ 16 (1) 2 x 1+3 x 2≤ 18 (2) x 2=4 (3) x 1≥ 3 (4) x 1≥ 0 (5) x 2≥ 0 (6)
Задача не имеет допустимых решений. ОДР представляет собой пустое множество (рис. б).
Многоугольные области: а – ограниченное множество; б – пустое множество; в – неограниченное множество
Задача 1211 не имеет решения, поэтому для нее процесс ветвления прерываем. Решим графически задачу 1212 как задачу ЛП. 3 x 1+2 x 2≤ 16 2 x 1+3 x 2≤ 18 x 2≤ 4 x 1≥ 3 x 2≤ 3 x 1≥ 0 x 2≥ 0 (1) (2) (3) (4) (5) (6) (7)
Область допустимых решений представляет собой многоугольник Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (5), то ее координаты удовлетворяют уравнениям этих прямых: 3 x 1+2 x 2≤ 16 x 2≤ 3 Решив систему уравнений, получим: x 1 = 3. 3333, x 2 = 3 Откуда найдем максимальное значение целевой функции: F(X) = 4*3. 3333 + 3*3 = 22. 3333
Оптимальное значение переменной x 1=3. 33 оказалось нецелочисленным. Разбиваем задачу 1212 на две подзадачи 12121 и 12122. В первой из них к условиям задачи 12121 добавляется условие х1 ≥ 4, а к задаче 12122 — условие х1 ≤ 3. Решим графически задачу 12121 как задачу ЛП. 3 x 1+2 x 2≤ 16 2 x 1+3 x 2≤ 18 x 2≤ 4 x 1≥ 3 x 2≤ 3 x 1≥ 4 x 1≥ 0 x 2≥ 0 (1) (2) (3) (4) (5) (6) (7) (8)
Область допустимых решений представляет собой треугольник. Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (6), то ее координаты удовлетворяют уравнениям этих прямых: 3 x 1+2 x 2≤ 16 x 1≥ 4 Решив систему уравнений, получим: x 1 = 4, x 2 = 2 Откуда найдем максимальное значение целевой функции: F(X) = 4*4 + 3*2 = 22
Текущий рекорд Z=22≥ 22, поэтому прекращаем ветвление из этой вершины Решим графически задачу 12122 как задачу ЛП. 3 x 1+2 x 2≤ 16 2 x 1+3 x 2≤ 18 x 2≤ 4 x 1≥ 3 x 2≤ 3 x 1≥ 0 x 2≥ 0 (1) (2) (3) (4) (5) (6) (7) (8) Сведем систему ограничений к следующему виду: 3 x 1+2 x 2≤ 16 2 x 1+3 x 2≤ 18 x 2≤ 4 x 1=3 x 2≤ 3 x 1≥ 0 x 2≥ 0 (1) (2) (3) (4) (5) (6) (7)
Область допустимых решений представляет собой одну точку. Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (4) и (5), то ее координаты удовлетворяют уравнениям этих прямых: x 1=3 x 2≤ 3 Решив систему уравнений, получим: x 1 = 3, x 2 = 3 Откуда найдем максимальное значение целевой функции: F(X) = 4*3 + 3*3 = 21
Текущий рекорд Z=22≥ 21, поэтому прекращаем ветвление из этой вершины F(X) = 22, x 1 = 4 x 2 = 2 Дерево решения задачи
Для определения переменной, по которой производится начальное ветвление, разработан ряд правил. • 1. Выбор целочисленной переменной, значение которой в оптимальном решении ЛП-1 имеет наибольшее дробное значение. • 2. Приоритетной является переменная, коэффициент которой в целевой функции превосходит остальные. • 3. Выбор переменной с наименьшим номером. Для дальнейшего ветвления выбираются следующие вершины. • Следует выбирать вершину, соответствующую наибольшему оптимальному значению целевой функции. • Произвольнымвершина является прозондированной в том случае, если она удовлетворяет хотя бы одному из следующих образом выбирается задача ЛП, решавшаяся последней. Промежуточная условий • 1. Оптимальное решение, соответствующее данной вершине целочисленно. • 2. Задача ЛП, соответствующая рассмотренной вершине, не имеет допустимых решений. • 3. Оптимальное значение f (x) соответствующей задачи ЛП не превосходит текущей нижней границы. При использовании метода ветвей и границ выбор вершины для дальнейшего ветвления происходит до тех пор, пока остаётся хотя бы одна не прозондированная вершина. Прозондированная вершина с наилучшим значением f (x) даёт оптимальное решение исходной задачи ЦЛП. Получение перед реализацией метода ветвей и границ допустимого целочисленного решения задачи ЦЛП может оказаться весьма полезным, так как оно даёт начальную нижнюю границу, используемую до получения лучшей нижней границы по методу ветвей и границ. Анализ опыта решения практических задач привёл к выработке ряда рекомендаций который можно использовать для уменьшения времени вычислений. • 1. Количество целочисленных переменных следует уменьшить насколько возможно. Например, целочисленные переменные, значения которых должны быть не меньше 20, можно рассматривать как непрерывные. • 2. Добавление новых ограничений, особенно включающих целочисленные переменные, обычно уменьшает время решения задач ЦЛП. • 3. По возможности следует получать близкие друг к другу верхнюю и нижнюю границы значений целочисленных переменных. • 4. Можно заканчивать реализацию метода ветвей и границ, если для задач максимизации выполняется соотношение: . • 5. Рекомендуется выбирать для ветвления целочисленные переменные в порядке убывания их приоритета, назначаемого в соответствии с технико – экономической интерпретацией переменных и опытом пользователя. В задачах с большим количеством переменных более эффективным является метод отсечения Гомори, который основан на введении дополнительных условий и анализе значений базисных и небазисных переменных , т. е. выполняется модифицированный симплекс-метод. Кроме того, данный метод может применяться в параметрическом программировании, когда исходные данные (коэффициенты) в ЦФ и ограничениях являются не постоянными величинами, а функциями, зависящими определенным образом от некоторых параметров.
Задача № 2 не имеет допустимых значений
