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

При ЗЛП принимает вид

(3.1)

. (3.2)

Рассмотрим -мерное координатное пространство с упорядоченными совокупностями (точками).

Определение 3.1. Множество точек пространства , координаты которых удовлетворяют уравнению , где хотя бы одно из чисел ( ), отлично от нуля, называют гиперплоскостью пространства .

Определение 3.2. Множество точек пространства , координаты которых удовлетворяют неравенству , называют полупространством пространства , расположенным по одну сторону от

гиперплоскости .

В пространстве уравнение определяет прямую, неравенство определяет полуплоскость.

Определение 3.3. Множество точек пространства , координаты которых одновременно удовлетворяют системе гиперплоскостей ( ), называют пересечением гиперплоскостей.

Определение 3.4. Выпуклой линейной комбинацией точек , , …, пространства называют точку ( , ).

Выпуклая линейная комбинация двух точек пространства является отрезком, соединяющим эти точки.

Определение 3.5. Множество точек пространства называется выпуклым, если оно вместе с любыми двумя своими точками содержит и их произвольную линейную комбинацию (то есть содержит вместе с любыми двумя точками и все точки отрезка ).

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

Определение 3.7. Множество называют замкнутым, если оно содержит все свои граничные точки, в противном случае – открытым.

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

Определение 3.9. Множество называют ограниченным, если существует шар радиусом конечной длины с центром в любой точке множества, который полностью содержит в себе данное множество. В противном случае множество называют неограниченным.

Определение 3.10. Множество называют связным, если любые две его точки можно соединить ломаной (или непрерывной кривой), целиком лежащей в этом множестве.

Определение 3.11. Открытое связное множество называют областью.

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

Определение 3.13. Выпуклую замкнутую область, имеющую конечное число угловых точек, называют выпуклым -мерным многогранником.

Определение 3.14. Выпуклое замкнутое множество, имеющее конечное число угловых точек, называют выпуклой -мерной многогранной

замкнутой областью.

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

Определение 3.16. Непустое множество допустимых решений ЗЛП называютмногогранником планов (решений).

Определение 3.17. Угловую точку многогранника решений называют вершиной.

Определение 3.18. Вершину многогранника планов с неотрицательными координатами называют опорной. Соответствующий ей план называют опорным планом.

Из определений следует, что каждой вершине многогранника решений соответствует опорный план ЗЛП.

Определение 3.19. Опорный план называют невырожденным, если он содержит ровно положительных координат, и вырожденным, если положительных координат меньше .

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

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

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

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

Рассмотрим графический метод решения ЗЛП.

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

Рис. 3.1.

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

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

2) Построим градиент целевой функции (в данном случае геометрический вектор):

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

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

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

5) Найти координаты вершины многоугольника, являющейся точкой экстремума. Для этого нужно решить систему уравнений тех прямых, пересечением которых является данная вершина.

6) Вычислить значение целевой функции в полученной вершине.

Замечание 3.1. Если при движении вдоль градиента линия уровня не покидает множество допустимых решений, то это множество является неограниченным в направлении оптимизации. В этом случае условно полагают, что или .

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

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

Пример 3.1. Фирма выпускает два вида мороженого: сливочное и шоколадное. Для изготовления мороженого используются два исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы даны в таблице:

Исходный продукт	Расход исходных продуктов на 1 кг мороженого	Запас, кг
Сливочное	Шоколадное
Молоко	0, 8	0, 5
Наполнители	0, 4	0, 8

Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более, чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого 16 руб., шоколадного – 14 руб. Какое количество мороженого каждого вида должна производить

фирма, чтобы доход от реализации продукции был максимальным? [1; 2].

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

Составим неравенства для ресурсных ограничений. Ограничение по молоку имеет вид: ; по наполнителям: . Составим неравенства для рыночных ограничений по спросу. Разница в суточном спросе на 2 вида мороженого составляет . Ограничение на суточный спрос шоколадного мороженого .

Тогда математическая модель задачи будет иметь вид

Далее решим задачу графическим методом.

1) Построим множество допустимых решений. Неравенство определяет полуплоскость, расположенную левее и ниже прямой , то есть прямой . Неравенство определяет полуплоскость, расположенную левее и ниже прямой . Ограничение определяет полуплоскость, расположенную левее и ниже прямой . Ограничение определяет полуплоскость, расположенную левее прямой , ограничения , определяют первую координатную четверть. Множество допустимых решений ЗЛП не пусто. Обозначим вершины многоугольника решений: (рис. 3.2).

Рис. 3.2.

2) Построим градиент целевой функции :

3) Построим линию уровня целевой функции : . Линия уровня перпендикулярна вектору .

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

5) Найдем координаты точки как точки пересечения прямых и :

Следовательно, точка .

6) Найдем значение целевой функции в точке :

рублей.

⇐ Предыдущая 123 4 5 6 7 8 9 10 Следующая ⇒