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

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

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

В некоторых задачах целочисленные значения могут быть равны только 0 или 1, тогда такие задачи называются задачами с булевыми переменными.

Задачу целочисленного линейного программирования можно решить как задачу линейного программирования, а затем округлить полученное решение. Однако такой способ допустим только при условии, что значения переменных настолько большие, что погрешностью, вызываемой округлением можно пренебречь. Если же в результате решения переменная принимает малое значение, то ее округление может привести к очень далекому от оптимального решения. Применяются два способа решения задач ЦЛП – метод отсечений и метод ветвей и границ.

Решение задачи ЦЛП методом отсечения:

1. Решение задачи как задачи ЛП.

2. Если мы получили целочисленное решение, то оно и является решением задачи ЦЛП.

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

Решение задачи ЦЛП методом ветвей и границ:

1. Решаем задачу как задачу ЛП.

2. Если мы получим оптимальные целочисленные решения задачи ЛП, то они являются также и оптимальными решениями задачи ЦЛП.

3. Если мы не получим целочисленных решений, то целевая функция Z₁ задачи ЛП становится верхней границей оптимального значения Z задачи ЦЛП, потому что значение целевой функции Z при введении в дальнейшем новых ограничений для получения оптимальных целочисленных решений уменьшается.

4. Затем производится ветвление по одному из нецелочисленных оптимальных решений задачи ЛП. Ветвление осуществляется с использованием некоторых правил по следующей схеме: если n x n+1, то 1) x n; 2) x n+1, где х – нецелочисленное оптимальное решение задачи ЛП, по которому мы осуществляем ветвление, n – ближайшее целое к х не превышающее х.

Правила ветвления:

1) Выбирается переменная, у которой дробная часть наиболее близка к 0,5.

2) Выбирается переменная с наибольшим приоритетом по какому — либо качественному или количественному значению.

3) Переменная выбирается произвольно.

Ограничения введенные при ветвлении добавляются к ограничениям задачи ЛП.

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

Вершина называется прозондированной, если:

1) Мы нашли в ней оптимальное целочисленное решение – решение задачи ЦЛП.

2) В данной вершине нет оптимальных решений задачи ЛП.

3) Значение Z в оптимальном решении задачи ЛП не больше текущей нижней границы.

Прочие вершины называются висящими.

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

Перепишем эту задачу в векторной форме: найти максимум функции

при условиях

(*)

,

где , ; - скалярное произведение; и — - мерные вектор- столбцы, составленные из коэфф-тов при неизвестных и свободных членах системы уравнений задачи:

; ; ;…; .

Сделаем следующие выводы.

Непустое множ-во планов основной задачи линейного программ-ния образует выпуклый многогранник. Каждая вершина этого многогранника опред-яет опорный план. В одной из вершин многогранника решений (т.о.для одного из опорных планов) значение целевой ф-ции является max (при условии, что функция ограничена сверху на множестве планов). Если max значение ф-ция принимает более чем в одной вершине, то это же значение она принимает в любой точке, являющейся выпуклой линейной комбинацией данных вершин.

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

Найдем решение задачи, состоящей в определении max значения функции

(а)

при условиях

, (б)

(в)

Каждое из нерав-тв системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми , и . В том случае, если система неравенств (б), (в) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как мн-во точек пересечения данных полуплоскостей — выпуклое, то областью допустимых решений задачи (а)—(в) является выпуклое множ-во, которое называется многоугольником решений (введенный ранее термин «многогранник решений» обычно употребляется, если ). Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.

Таким образом, исходная задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция F принимает максимальное значение. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указан­ных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим линию уровня (где — некоторая постоянная), проходящую через многоугольник решений, и будем передвигать ее в направлении вектора до тех пор, пока она не пройдет через последнюю ее общую точку с многоугольником решений. Коор-ты указанной точки и определяют оптимальный план данной задачи.

Заканчивая рассмотрение геометрической интерпретации

Рис. 1.1 Рис. 1.2

задачи, отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 1.1—1.4. Рис. 1.1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 1.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 1.3 изображен случай, когда целевая функция не ограничена сверху на множестве допустимых решений, а на рис. 1.4—случай, когда система ограничений задачи несовместна.

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

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

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

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

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

3. Находят многоугольник решений.

4. Строят вектор .

5. Строят прямую , проходящую через много­угольник решений.

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

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

Эк интерпретация

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

II. Практическая часть

1. Задача 1

Public Type struct

predmet As String * 1

prep As String * 1

group As String * 1

day As String * 1

para As String * 1

auditoria As String * 1

End Type

Dim c, k As Integer

Dim min, ind_min As Integer

Dim i, i2 As Integer

Public Sub listing(group As String, day As String)

Dim sved As struct

Open App.Path & "\db.txt" For Random As #1 Len = Len(sved)

c = LOF(1) / Len(sved)

k = 0

For i = 1 To c

Get #1, i, sved

If sved.group = group And sved.day = day Then

Print sved.prep

End If

Next i

End Sub

Private Sub Command1_Click()

listing "5", "1"

End Sub

2. Задача 2

3.