Главная » Программирование

Общая задача линейного программирования определение

Содержание
  1. Общая, стандартная и основная задачи линейного программирования
  2. Геометрическая интерпретация задачи линейного программирования
  3. Общая и основная задачи линейного программирования.
  4. Свойства задач линейного программирования. Графический метод решения задач линейного программирования.
  5. Определение задачи линейного программирования (злп), общая, симметричная и каноническая формы записи задачи линейного программирования
  6. Переход от одной формы злп к другой
  7. Математические модели экономических задач Задача об оптимальном использовании ресурсов

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

Определение 1. Общей задачей ЛП называется задача нахождения максимального (минимального) значения линейной целевой функции (1) при условиях , (2) , (3) , ,(4), где ,,— заданные постоянные величины и. Определение.2. Функция Z называется целевой функцией задачи (1 — 4), —проектными параметрами задачи, а условия (2 — 4) ограничениями данной задачи. Определение 3. Стандартной задачей ЛП называется задача нахождения целевой функции (1) при выполнении условий (2), (4), где k=m,l=n, т.е. когда ограничения заданы только в виде неравенств (2), и все проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде равенств отсутствуют: , , . Определение 4. Канонической (или основной) задачей ЛП называется задача нахождения максимального (минимального) значения функции (1) при выполнении условий (3), (4), где k=0,l=n,mn, т.е. когда ограничения заданы только в виде равенств (3), и все проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде неравенств (2) отсутствуют: , , ,. Определение 5. Совокупность значений проектных параметров , удовлетворяющих ограничениям задачи (2-4), называетсядопустимым решением, или планом. Определение 6. План , при котором целевая функция (1) принимает свое максимальное (минимальное) значение, называетсяоптимальным, т.е. . Все три формы задачи ЛП эквивалентны, ибо каждая из них с помощью некоторых преобразований может быть переписана в форме другой задачи. При этом необходимо пользоваться следующими правилами:

  1. Задачу минимизации функции можно свести к задаче максимизации, и, наоборот, путем замены знаков коэффициентов на противоположные, поскольку.
  2. Ограничения-неравенства (2) можно заменить эквивалентными ограничениями-равенствами путем введения дополнительных неотрицательных переменных следующим образом:
Читайте также:  Средства разработки приложений oracle

Ограничение-неравенство вида преобразуется в ограничение-равенство,, а ограничение-неравенство вида— в ограничение-равенство,. При этом число дополнительных переменных равно числу преобразуемых неравенств. Вводимые дополнительные переменные имеют вполне определенный смысл. Так, например, для задачи распределения ресурсов числовое значение дополнительной переменной равно объему неиспользованного соответствующего ресурса. С математической точки зрения основные и дополнительные переменные играют одинаковую роль. Поэтому целесообразно их единообразное обозначение.

  1. Каждое ограничение-равенство вида (3) можно записать в виде двух неравенств .
  2. Переменная , неограниченная условием неотрицательности вида (4), можно заменить разностью двух дополнительных неотрицательных переменных:,,.

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

Рассмотрим задачу, состоящую в определении максимального значения функции: (5) при условиях , (6) , (7). Эта задача ЛП в стандартной форме с двумя переменными. Каждое неравенство вида (6), (7) геометрически определяет полуплоскость соответственно с граничными прямыми (8). При этом вектор , как градиента функции, указывает ту полуплоскость, которая определяется неравенством, а вектор— полуплоскость, определяемую неравенством. Если система неравенств (6), (7) совместна, то область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Пересечение этих полуплоскостей образует выпуклый многоугольник решений, или область допустимых решений (ОДР). Таким образом, исходная задача ЛП состоит в нахождении таких точек многоугольника решений, в которых целевая функция Z принимает максимальное (минимальное) значение. Эта точка существует тогда, когда многоугольник решений не пуст, и на нем целевая функция ограничена. Линейная целевая функция достигает точек экстремума только на границе выпуклого многоугольника. Рассмотрим градиент функции цели . Это будет вектор(см. рис.2.), указывающий направление возрастания функции цели. Очевидно, если взять обратное направление, то это будет направлением убывания функции цели. Если построить произвольную прямую— const, то её движение параллельно самой себе в направлении вектора приведет к возрастанию функции цели. При этом для допустимости решения эта прямая должна иметь хотя бы одну общую точку с многоугольником решений. Два крайних положения этой прямой в ОДР соответствуют наименьшему и наибольшему значениям целевой функции. При этом могут встретиться случаи, изображенные на рис.2-5, когда исходная задача имеет единственное решение (минимальное и максимальное значение) (рис.2), множество решений (координаты любой точки прямойна рис.3), и решение исходной задачи не существует в силу неограниченности целевой функции (рис.4) или несовместности системы неравенств (6), (7) (рис.5).

Источник

Общая и основная задачи линейного программирования.

Общая задача. Найти максимальное значение линейной целевой функции. z = c1x1+ c2x2+ … + cnxn при линейных ограничениях xj>= 0,j= 1,n= n> Определение 1.1. Совокупность чисел х = (х1, х2. хn), удовлетворяющих ограничениям (1.2), называется допустимым решением или планом. Определение 1.2. План х* =(х1 * , х2 * . хn*), при котором целевая функция (1.1) принимает свое максимальное значение, называется оптимальным.Каноническая форма. Задачу линейного программирова­ния будем считать приведенной к каноническому виду, если 1) требуется найти максимум целевой функции; 2) система ограничений (1.2) содержи! только равенства; 3) правые части системы ограничений неотрицательны. Переход от общей формы к канонической: 1) если в задаче требуется найти минимум целевой функции, то вводим новую целевую функцию z1 = -z, тогда max z1 = -min z; 2) чтобы перейти от неравенства к равенству в системе огра­ничений, необходимо прибавить (вычесть) дополнительную не­отрицательную переменную к левой части неравенства; 3) если в правой части системы ограничений имеются отрица­тельные числа, то необходимо умножить на «-1» обе части равен­ства, в котором в правой части стоит отрицательное число. Задачу линейного программирования в канонической фор­ме называют основной задачей.

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

Свойства задач линейного программирования. Рассмотрим следующую основную задачу линейного про­граммирования: z = c1x1+ c2x2+ …+cnxnmax при ограничениях , Перепишем ограничения этой задачи к немирной форме: x1Р,+х2Р2+. + хnРn,(1.3) где Р1, . Рnи Р0 — k-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы ограничений основной задачи: Определение 1. План х = (x1,х2. хn) называется опорным планом основной задачи линейного программирования, если его положительные коэффициенты (хj >0) стоят при линейно независимых векторах Рj. Так как векторы Р: являются k-мерными, то из определения опорного плана следует, что число его положительных компо­нент не может быть больше числа К. Определение 2. Опорный план называется невырож­денным, если он содержит ровно k положительных компонент, в противном случае он называется вырожденным. Свойства задач линейного программирования тесным обра­зом связаны со свойствами выпуклых множеств. Определение 3. Пусть х(|). х(m) — произвольные точ­ки евклидова пространства Rn . Выпуклой линейной комбинацией этих точек называется сумма: а,х(|) + . + аmх(m) , где аi; -про­извольные неотрицательные числа, сумма которых равна 1. Определение 4. Множество называется выпуклым, ес­ли вместе с любыми двумя своими точками оно содержит и отре­зок прямой, соединяющий эти точки. Определение 5. Точка х выпуклого множества назы­вается угловой, если она не может быть представлена в виде вы­пуклой линейной комбинации каких-нибудь двух других различ­ных точек данного множества. Сформулируем первое свойство задач ЛП. Теорема 1.1. Множество планов любой задачи линейного программирования является выпуклым (если оно не пусто). Определение 7. Непустое множество планов задачи линейного программирования называется многогранником реше­ний, а всякая угловая точка многогранника решений — вершиной. Сформулируем второе свойство задач ЛП. Теорема 1.2. Если задача линейного программирования имеет оптимальный план, то экстремальное значение целевая функция задачи принимает в одной из вершин многогранника решений. Если экстремальное значение целевая функция прини­мает более чем в одной вершине, то она принимает его на ребре (грани), содержащем эти вершины. Теорема 1.3. Если система векторов Р1. Рm() ли­нейно независима и такова, что х1Р1+. + хmРm=Р0, где все хj>= 0, то точка х = (х,, х2. хт,0. 0) является верши­ной многогранника решений. Теорема 1.4. Если х = (х,,х2. хп) — вершина многогран­ника решений, то векторы Рj , соответствующие положительным хj > 0, линейно независимы.

Источник

Определение задачи линейного программирования (злп), общая, симметричная и каноническая формы записи задачи линейного программирования

,

называется общей задачей линейного программирования (ЗЛП).

Задача в краткой записи имеет вид

,

Определение 2. Задача, в которой требуется найти экстремум функции

,

называется задачей линейного программирования, заданной в канонической форме.

Определение 3. Задача, в которой требуется найти экстремум функции

,

называется задачей линейного программирования заданной в симметричной форме записи.

Определение 4. Функция

называется целевой функцией ЗЛП.

Определение 5. Совокупность чисел удовлетворяющая ограничениям ЗЛП, называется допустимым решением ЗЛП.

Определение 6. Допустимое решение, при котором целевая функция принимает максимальное (минимальное) значение, называется оптимальным решением ЗЛП.

Переход от одной формы злп к другой

Переход от неканонической формы ЗЛП к канонической.

Теорема 1. Каждому решению неравенства соответствует единственное решение уравнения и неравенства , и наоборот.

Из теоремы следует, что неравенство можно заменить уравнением и неравенством .

Переменную называют балансовой переменной.

Следовательно, чтобы привести задачу к каноническому виду, нужно заменить каждое неравенство системы ограничений соответствующим уравнением и неравенством , введя в каждое неравенство балансовую переменную с коэффициентом +1, если знак неравенства £, и с коэффициентом -1, если знак неравенства ³. В целевую функцию балансовые переменные вводятся с нулевыми коэффициентами.

Если на переменную не наложено условие на неотрицательность, то эту переменную надо представить в виде разности двух неотрицательных переменных: , где

Переход от канонической формы ЗЛП к симметричной форме.

Чтобы перейти от канонической формы ЗЛП к симметричной, нужно найти общее решение системы уравнений:

Так как все переменные должны быть неотрицательными, в том числе и базисные, получим систему неравенств:

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

Пример 1. Дана ЗЛП: найти наибольшее значение функции при ограничениях:

.

Приведем ее к каноническому виду.

Канонический вид задачи: найти наибольшее значение функции при ограничениях:

.

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

.

Разрешим систему относительно произвольного базиса, система примет вид

И так как , отбросив базисные переменные, получим систему неравенств

Выразим целевую функцию через свободные переменные:

Симметричный вид задачи: найти наибольшее значение функции при ограничениях:

.

Математические модели экономических задач Задача об оптимальном использовании ресурсов

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

Составим математическую модель данной задачи.

i — номер i-го вида ресурса, ;

bi — запасы i-го вида ресурса, ;

j — номер j-го вида продукции, ;

aij — затраты i-го вида ресурса на производство единицы j-го вида продукции;

cj — прибыль от реализации единицы j-го вида продукции.

Все данные занесем в таблицу:

1 2 … j … n

Источник

Оцените статью
© 2024 Программирование