Общая формулировка задачи линейного программирования
Аналогично транспортной задаче решается задача об оптимизации распределения ресурсов (трудовых, материальных, финансовых) и задача о диете. При всем разнообразии, по своему конкретному содержанию каждая из них была задачей на нахождение наиболее выгодного варианта. С точки зрения математической, в каждой задаче ищутся значения нескольких неизвестных, причем требуется, чтобы:
эти значения удовлетворяли некоторой системе линейных уравнений или неравенств;
при этих значениях некоторая линейная функция (линейная форма) от этих неизвестных обращалась в минимум (максимум);
эти значения были неотрицательными.
Задачами такого рода и занимается линейное программирование.
Говоря точнее, линейное программирование - это математическая дисциплина, изучающая методы нахождения наименьшего (или наибольшего) значения линейной функции нескольких переменных, при условии, что последние удовлетворят конечному числу линейных уравнений или неравенств. Общая математическая формулировка задачи линейного программирования выглядит следующим образом.
Дана система линейных уравнений:
а11x1+а12x2+ ... +а1nxn = b1
|
|
|
а21x1+а22x2+ ... +а2nxn = b2
(I ) í ... ... ... ... ... ... ... ...
аm1x1+аm2x2+ ... +аmnxn = bm
и линейная функция ¦=c1x1+c2x2+ ... +cnxn ( II ).
Требуется найти такие неотрицательные решения х1 ³ 0, х2 ³ 0 ... х n ³ 0 ( III ) системы ( I ) при которых функция ¦ принимает наименьшее (наибольшее) значение.
Уравнения ( I ) называются ограничениями данной задачи, уравнение ( II ) называется линейной формой, а уравнение ( III ), строго говоря, тоже являются ограничениями, однако их не принято так называть, поскольку они являются общими для всех задач линейного программирования, а не только конкретной задачи. Любое неотрицательное решение системы уравнений называется допустимым. Допустимое решение, дающее минимум функции ¦, оптимальное решение (если оно существует) не обязательно единственно; возможны случаи, когда имеется бесчисленное множество оптимальных решений. Наконец, саму функцию ¦ часто называют линейной формой или функцией цели.
|
|
|
Казалось бы, т.к. задача линейного программирования ставится как задача минимизации некоторой функции ¦, то можно применить классический прием дифференциального исчисления. Однако частные производные ¦ равны коэффициентам при неизвестных, которые в «нуль» одновременно не обращаются.
Графическая интерпретация
Решения задач линейного программирования
Задачу линейного программирования (ЛП)можно решать аналитическими и графическими методами. Аналитические методы являются основой для решения задачи на ЭВМ. Их единственный недостаток состоит в том, что в отличие от графических методов, они недостаточно наглядны. Графические методы очень наглядны, но они пригодны лишь для решения задач на плоскости, т.е. когда размерность пространства К=2. Однако, учитывая большую наглядность графических методов, с их помощью рассмотрим идею решения задачи ЛП на примере задачи распределения ресурсов.
Однако прежде чем заняться решением, сделаем некоторые замечания. Пусть мы имеем систему mуравнения с nнеизвестными (I).
|
|
|
Возможны следующие варианты:
Число неизвестных меньше, чем число уравнений n < m.
н апример: ì2x1=4, в этом случае n=1;
x1=5, тогда m=2 (число линейно независимых уравнений). (4.4)
Очевидно, что система (4.4) решения не имеет, и она несовместна;
Число неизвестных равно числу уравнений n = m.
В этом случае система имеет единственное решение или не имеет ни одного. Заметим, что m равно числу линейно независимых уравнений.
Для системы: ì2x=10, n=1, m=1;
x=30.
Если число неизвестных больше числа уравнений, то система имеет бесчисленное множество решений. Пусть n > m. Например:
2 x 1 + x 2 =2 (4.5)
Очевидно, что это уравнение прямой, и все значения x 1и x 2, лежащие на этой прямой, являются решением уравнения (4.2). Значит уравнение (4.5)имеет бесчисленное множество решений.
В случае, когда система имеет больше одного возможного решения, может быть поставлена задача оптимизации, суть которой в том, что из всех допустимых решений, удовлетворяющих ограничениям и граничным условиям, выбрать такое, которое придает целевой функции оптимум. Вспомним построение линейных зависимостей. Пусть дано уравнение:
|
|
|
a 1 x 1 + a 2 x 2 = b (4.6)
Преобразуем его к виду:
(4.7)
Запись (4.7) называют уравнением прямой в отрезках, что изображено на Рис. 4.1. Рассмотрим еще одну форму представления уравнения (4.6). Запишем это уравнение в виде:
a2x2=b-a1x1
или
или
x 2 = F - kx 1 (4.8)
Уравнение (4.8) изображено на рис. 4.2.
|
|
Вспомним неравенства. Если линейное уравнение с двумя переменными может быть представлено в виде прямой на плоскости, то неравенство вида:
a 1 x 1 + a 2 x 2 £ b (4.9)
изображается как полуплоскость, показанная на рис. 4.1. На этом рисунке часть плоскости, удовлетворяющая неравенству, заштрихована. Координаты всех точек, принадлежащих заштрихованному участку, имеют такие значения x 1 и x 2, которые удовлетворяют заданному неравенству. Значит, эти значения составляют область допустимых решений (ОДР). Саму прямую считаем принадлежащей каждой из двух указанных полуплоскостей. Предположим теперь, что задано не одно неравенство, а система:
а11x1+а12x2 £ b1
а21x1+а22x2 £ b2
(4.10) í ... ... ... ...
аm1x1+аm2x2 £ bm,
где первое неравенство определяет некоторую полуплоскость П1, второе - полуплоскость П2 и т.д.
если какая-либо пара чисел ( x 1 , x 2 ) удовлетворяет всем неравенствам (4.10), то, соответствующая точка Р( x 1 , x 2 ), принадлежит всем полуплоскостям П1, П2, ... П m одновременно. Другими словами, точка Р принадлежит пересечению (общей части) полуплоскостей П1, П2, ... П m, т.е. некоторой многоугольной области М (Рис. 4.3), которая является ОДР. Вдоль контура области изображены штрихи, идущие внутрь области. Они одновременно указывают, с какой стороны от данной прямой лежит соответствующая полуплоскость, то же самое указано и с помощью стрелок на каждой линии. Сразу же отметим, что ОДР не всегда бывает, ограничена: в результате пересечения нескольких полуплоскостей может возникнуть и неограниченная область (Рис. 4.4). Возможен и случай, когда область допустимых решений (ОДР) пуста. Это означает, что система (5.7) противоречива (Рис. 4.5). Многоугольник ОДР обладает весьма важным свойством: он является выпуклым.
|
|
фигура называется выпуклой, если вместе с любыми двумя своими точками А и В, она содержит и весь отрезок АВ.
В случае трех неизвестных, каждое уравнение представляет собой плоскость в пространстве. Каждая плоскость разбивает все пространство на два полупространства. Система неравенств определяет в пространстве выпуклый объемный многогранник, который представляет ОДР.
МЕТОДЫ РЕШЕНИЯ
Дата добавления: 2018-10-26; просмотров: 312; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!