Задачи линейного программирования и их решение в современных вычислительных

Лекция №12

быть математически сформулированы как задачи нахождения максимума (минимума) функции многих

переменных, при заданной системе ограничений на основные переменные задачи.
Функция, для которой определяется точка максимума или минимума (оптимума), называется целевой функцией. Часто она обозначается буквами F или С.
С(x1, x2, …, xn)  max (min)
G1(x1, x2, …, xn)≥0
….
Gm(x1, x2, …, xn)≥0

Функции С и G могут быть как линейными, так и нелинейными. Ограничения могут быть нестрогими неравенствами (≥ или/и ≤) или равенствами.
Кроме того, могут быть специфические ограничения. Например, целочисленность одной или нескольких переменных х.

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

линейных ограничений.
Основные математические предположения ЛП:
Линейность целевой функции (ЦФ) и ограничений.
Определенность (детерминированность) – предполагается, что все параметры модели известны точно или могут быть оценены.
Делимость – предполагается, что все основные переменные задачи могут принимать произвольные вещественные значения в определенном диапазоне (бесконечно делимы).
Основателем линейного программирования является советский математик Леонид Витальевич Канторович (1939г.).

описательную модель задачи.
Выбрать основные переменные задачи.
Выбрать некоторую количественную меру эффективности

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

переменных модели.

равенства + условие положительности всех переменных:
Или в сокращенной записи:
i=1, 2,

…, m,
J=1, 2, …, n.

(≤) + условие положительности всех переменных:
Или в сокращенной записи:
i=1, 2,

…, m,
J=1, 2, …, n.

+ условие положительности всех переменных:
Или в сокращенной записи:
i=1, 2, …,

m,
J=1, 2, …, n.

неравенства с разными соотношениями (≥, ≤) и равенства.
Условие положительности может

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

…, xn, удовлетворяющих системе ограничений, называется решением этой системы. Решение системы также

часто называется планом, и немного реже – программой, но именно отсюда и пошло название «линейное (или математическое) программирование».
Оптимальным решением задачи линейного программирования называется решение системы, при которых функция цели в оптимум.
Решение задачи линейного программирования называется вырожденным, если в нём некоторые переменные равны нулю. В противном случае решение является невырожденным.

х1 и х2 (n=2)

Симплекс-метод

П2  требуется четыре вида ресурсов (сырья):  S1 , S2 , S3 , S4

.
Запасы сырья – соответственно,  b1,  b2 , b3 , b4  единицы. На производство единицы продукции Пj требуется ai,j единиц сырья Si, j=1, 2; i=1, …, 4.
Доход от реализации одной единицы продукции П1 равен  c1 у.е., а доход от реализации одной единицы продукции П2  равен c2 у. е.
Требуется узнать, сколько единиц  П1 и сколько единиц  П2 нужно изготовить из имеющегося запаса сырья, чтобы получить максимальный доход.

П2

виде таблицы:
П2

П1,
х2 –количество изготовляемых единиц продукции П2.
Тогда ЦФ равна:
C=С(x1, x2)=c1x1+c2x2.
Ограничения

на расход сырья запишутся в виде:

В левой части i-го ограничения записан общий расход сырья Si на производство продукции двух видов, а в правой части – запас сырья Si. Кроме того, количество продукции не может быть отрицательным: x1≥0, x2≥0.

имеется, соответственно, a1  и  a2  единиц некоторого груза. Этот груз

следует доставить в три пункта назначения  B1, B2, B3,  и в каждый из них должно быть завезено, соответственно, b1,  b2, b3 единиц этого груза. Стоимость перевозки одной единицы груза из пункта  Ai  в пункт  Bk  равна  ci,k. Составить такой план перевозок, чтобы суммарная стоимость перевозок была минимальной.
Считать, что количество всего груза на двух пунктах отправления равно потребности в грузе на всех трех пунктах назначения, то есть:
a1  +  a2 = b1 +  b2 + b3.

таблицы:

пункта Ai в пункт Bk . Тогда ЦФ (которую нужно

минимизировать) равна:

Ограничения:

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

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

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

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

переменных: х1 и х2
Пусть ограничения имеют вид:
Кроме того, переменные x1

и х2 – неотрицательные. Надо найти значения x1 и х2, на которых ЦФ
С =с1х1+с2х2
принимает оптимальное значение.

удовлетворяющих ограничениям –многоугольник. Например, пятиугольник АВСDE.
Черная линия, проходящая через

начало координат – это линия уровня ЦФ С=0. Перпендикулярный вектор (градиент) к линии уровня показывает направление увеличения ЦФ.

Линии уровня (параллельные черной) mn и MN являются ОПОРНЫМИ (имеют одну общую точку с многоугольником решений). Точка А является точкой минимума ЦФ, точка С – точкой максимума ЦФ.

х2, на которых ЦФ
С =х1+3х2
принимает максимальное значение.

допустимых значений – четырехугольник АВСD.
Черная линия, проходящая через начало

координат – это линия уровня ЦФ С=0. Перпендикулярный вектор к линии уровня (градиент) показывает направление увеличения ЦФ.

Перемещая линию уровня в направлении градиента, найдем опорные прямые. Точка А является точкой минимума ЦФ, точка В – точкой максимума ЦФ. Подставляя в ЦФ координаты точки В x1=2, x2=4, найдем максимальное значение ЦФ: Cmax=14.

х2, на которых ЦФ
С =5х1+6х2
принимает минимальное значение.

линия, проходящая через начало координат – это линия уровня ЦФ

С=0. Перпендикулярный вектор к линии уровня (градиент) показывает направление увеличения ЦФ.

Ближайшее от начала координат опорной положение линии уровня – в точке B. Эта точка является точкой минимума ЦФ точкой максимума ЦФ. Подставляя в ЦФ координаты точки В x1=2, x2=2, найдем минимальное значение ЦФ: Cmax=22.

одного базисного решения (вершины многогранника решений) системы ограничений задачи линейного

программирования к другому базисному решению до тех пор, пока функция цели не примет оптимального значения (максимума или минимума).
Симплекс метод был предложен американским математиком Р.Данцигом в 1947 году, с тех пор для нужд промышленности этим методом нередко решаются задачи линейного программирования с тысячами переменных и ограничений.

задач ЛП
Matlab: функция linprog