Letysite.ru

IT Новости с интернет пространства
1 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

Структура оптимизационных задач.

Оптимизационные задачи (ОЗ) решаются с помощью оптимизационных моделей (ОМ) методами математического программирования.

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

o управляемых переменных;

o неуправляемых переменных;

o формы функции (вида зависимости между ними).

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

Если система ограничений несовместима, то область допустимых решений является пустой. Ограничения подразделяются:

а) на линейные ( I и II ) и нелинейные ( III и IV )

б) детерминированные ( А , В ) и стохастические (группы кривых С i )

Стохастические ограничения являются возможными, вероятностными, случайными.

ОЗ решаются методами математического программирования, которые подразделяются:

o на линейное программирование;

o нелинейное программирование;

o динамическое программирование;

o целочисленное программирование;

o выпуклое программирование;

o исследование операций;

o геометрическое программирование и др.

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

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

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

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

· задача об оптимальном использовании ресурсов при производственном планировании;

· задача о смесях (планирование состава продукции);

· задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или «задача о рюкзаке»);

· транспортные задачи (анализ размещения предприятия, перемещение грузов).

Задача линейного программирования (стандартная, каноническая и общая) и ее геометрическая интерпретация.

Задачи

Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида [3] :

Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования (ОЗЛП)

,

.

Задача линейного программирования будет иметь канонический вид, если в основной задаче вместо первой системы неравенств имеет место система уравнений с ограничениями в форме равенства [4] :

,

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

Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств [5] .

Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты с обратным знаком.

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

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

1. Формулировка задачи.

Даны линейная функция

и система линейных ограничений

где а ij , Ь j и С j — заданные постоянные величины

Найти такие неотрицательные значения х 1 , х 2 , …, х n , которые удовлетворяют системе ограничений (1.2) и доставляют линейной функции (1.1)минимальное значение

Общая задача имеет несколько форм записи

Векторная форма записи.Минимизировать линейную функцию Z = СХ при ограничениях

где С = (с 1 , с 2 , …, с N ); Х = (х 1 , х 2 , …, х N ); СХ – скалярное произведение; векторы

состоят соответственно из коэффициентов при неизвестных и свободных членах

Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А , Х 0, где С = (с 1 , с 2 , …, с N ) – матрица-cтрока; А = (а ij ) – матрица системы;

Х – матрица-столбец, А — матрица-столбец

Запись с помощью знаков суммирования.Минимизировать линейную функцию Z = С j х jпри ограничениях

0пределение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х 1 , х 2 , …, х N ), удовлетворяющий условиям (1.2) и (1.3)

0пределение 2. План Х = (х 1 , х 2 , …, х N ) называется опорным, если векторы А (i = 1, 2, …, N), входящие в разложение (1.4) с положительными коэффициентами х , являются линейно независимыми

Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М

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

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

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

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

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

Читать еще:  Семантика языка программирования это

На рис. 2.1 изображено выпуклое множество (выпуклый многоугольник), а на рис. 2.2 — невыпуклое.

Определение 2. Пересечение конечного числа выпуклых множеств также выпуклое множество.

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

Утверждение 1. Множеством решений системы m линейных неравенств с n переменными является выпуклый многогранник в n-мерном пространстве(исключая случай, когда система несовместна).

Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.
Ранее говорилось, что ограничениями любой задачи линейного программирования являются либо система линейных уравнений, либо система линейных неравенств. Совокупность решений таких систем при условии их совместности, образует выпуклые множества с конечным числом угловых точек. В частном случае, когда в систему ограничений — неравенств входят только две переменные x1 и x2 это множество можно изобразить на плоскости (см.3).

Теорема 2. Если задача линейного программирования имеет оптимальное решение, то оно совпадает с одной (двумя) из угловых точек множества допустимых решений.
Справедливость этого утверждения иллюстрируется в примере 3.

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

Лекция 3: Математическое программирование. Линейное программирование. Виды задач линейного программирования. Постановка задач линейного программирования и исследование их структуры. Решение задач линейного программирования симплекс-методом

1. Понятие математического программирования

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

Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.

Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.

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

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

  • задачи линейного программирования,
  • задачи нелинейного программирования .

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

2. Понятие линейного программирования. Виды задач линейного программирования

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования . Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина » математическое программирование «. Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программы) для ЭВМ» не имеет, т.к. дисциплина » линейное программирование » возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин » линейное программирование » возник в результате неточного перевода английского » linear programming «. Одно из значений слова «programming» — составление планов, планирование. Следовательно, правильным переводом английского » linear programming » было бы не » линейное программирование «, а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термины линейное программирование , нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

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

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

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

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

Общая форма задачи имеет вид: найти при условиях

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

Лекция 3: Математическое программирование. Линейное программирование. Виды задач линейного программирования. Постановка задач линейного программирования и исследование их структуры. Решение задач линейного программирования симплекс-методом

1. Понятие математического программирования

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

Читать еще:  Программирование на ассемблере для pic

Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.

Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.

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

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

  • задачи линейного программирования,
  • задачи нелинейного программирования .

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

2. Понятие линейного программирования. Виды задач линейного программирования

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования . Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина » математическое программирование «. Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программы) для ЭВМ» не имеет, т.к. дисциплина » линейное программирование » возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин » линейное программирование » возник в результате неточного перевода английского » linear programming «. Одно из значений слова «programming» — составление планов, планирование. Следовательно, правильным переводом английского » linear programming » было бы не » линейное программирование «, а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термины линейное программирование , нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

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

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

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

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

Общая форма задачи имеет вид: найти при условиях

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

Линейное программирование

Введение в линейное программирование

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

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

Задача условной оптимизации называется задачей линейного программирования (ЛП), если целевая функция и все функции ограничений являются линейными функциями: (5.1)
где ci,bj,aij постоянные коэффициенты. Это есть стандартная форма задачи ЛП. В общем случае ограничения могут иметь знак „» или „=». Однако, умножая неравенство на -1 и заменяя равенство двумя неравенствами „≤» и „≥», можно придти к стандартной форме. Кроме того, взяв вместо f(x) функцию — f(x), можно получить задачу на минимум.
Обозначим через c=(c1 ,…,cn) — вектор коэффициентов целевой функции, b =(b1,…,bk) — вектор свободных членов ограничений, — матрицу коэффициентов ограничений и запишем нашу задачу в векторной форме: (5.2)
где — скалярное произведение двух векторов c и x. Такая компактная запись удобна для теоретических исследований.
Несколько примеров задач, которые сводятся к задачам линейного программирования:

Задача оптимального раскроя материала. Фирма изготовляет изделие состоящее из р деталей. Причем в одно изделие эти детали входят в количествах k1 . kr . С этой целью производится раскрой m партий материала. В i-ой партии имеется bi единиц материала. Каждую единицу материала можно раскроить на детали n способами. При раскрое единицы i-ой партии j-м способом получается аijr деталей r-го вида. Требуется составить такой план раскроя материала, чтобы из них получить максимальное число изделий.

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

Читать еще:  Синтаксис в программировании

Задача о назначениях на работу. Имеется n работ и n исполнителей. Стоимость выполнения работы i исполнителем j равна cij. Нужно распределить исполнителей на работы так, чтобы минимизировать затраты на оплату труда.

3адача о смесях (о рационе). Из m видов исходных материалов каждый из которых состоит из n компонент, составить смесь, в которой содержание компонент должно быть не меньше b1 . bn. Известны цены единиц материалов с1 . сm и удельный вес j-го компонента в единице i-го материала. Требуется составить смесь, в которой затраты будут минимальными.

Задача о рюкзаке. Имеется n предметов. Вес предмета i равен рi , ценность – сi (i=1. n). Требуется при заданной ценности груза выбрать совокупность предметов минимального веса.

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

Для любой задачи ЛП можно составить двойственную к ней задачу по следующим правилам.
1. Привести исходную задачу ЛП к стандартной форме.
2. Ввести новые переменные по числу основных ограничений исходной задачи.
3. Составить новые ограничения из новых переменных в виде линейных неравенств, знаки которых противоположны знакам неравенств исходной задачи, коэффициентами которых служат элементы транспонированной матрицы исходной задачи, а свободными членами — коэффициенты при целевой функции исходной задачи.
4. Для новых переменных написать условия неотрицательности.
В результате для исходной задачи (5.1) получим следующую двойственную задачу ЛП: (5.3)
Задача (5.1) относительно задачи (5.3) называется прямой задачей ЛП . Векторная форма задачи (5.3) имеет вид: (5.4)
Рассмотрение взаимно двойственных задач ЛП полезно как с теоретической, так и с практической точек зрения. Это видно из следующих утверждений.
1. Если одна из задач (5.1) и (5.3) имеет оптимальное решение, то и другая имеет оптимальное решение, причем
2. Если целевая функция одной из задач неограниченна, то ограничения другой задачи несовместны (т.е. множество допустимых решений пусто).
3. Для того, чтобы допустимое решение и были оптимальными решениями соответствующих задач (5.1) и (2.3) , необходимо и достаточно, чтобы

4. Для любых допустимых решений x 0 и y 0 справедливо неравенство f(x 0 ) ≤ z(y 0 ); если f(x 0 ) = z(y 0 ), то x 0 и y 0 — оптимальные решения задач (5.1) и (5.3).
5. Если прямая задача (5.1) моделирует максимизацию дохода при ограниченных ресурсах, то двойственная задача (5.3) при тех же предпосылках моделирует минимизацию затрат при фиксированном уровне дохода.

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

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

Постановка задачи — первый и наиболее важный этап построения модели, способный обеспечить правильное решение проблемы.

Даме необходимо похудеть, за помощью обратилась к подруге.

Построение модели — рассмотрение этого этапа и является главной целью.

Подруга посоветовала перейти на рациональное питание, состоящее из двух продуктов P и Q .

Суточное питание этими продуктами должно давать не более 14 единиц жира (чтобы похудеть), но не менее 300 калорий. На упаковке продукта Р написано, что в одном килограмме этого продукта содержится 15 единиц жира и 150 калорий, а на упаковке с продуктом Q — 4 единицы жира и 200 калорий соответственно. При этом цена 1 килограмма продукта Р равна 15 руб., а 1 кг продукта Q — 25 руб.

Так как дама была стеснена в средствах, но ее интересовал вопрос: в какой пропорции нужно брать эти продукты для того, чтобы выдержать условия диеты и истратить как можно меньше денег?

Перейдем к формализации данной ситуации на языке математических символов.

Обозначим через х количество продукта Р и через у количество продукта Q , требуемые для выполнения условий диеты.

Количество единиц жира, содержащегося в х кг продукта Р и в у кг продукта Q , равно 15х + 4 и по условию диеты не должно превосходить 14:

В свою очередь, количество калорий, содержащихся в х кг продукта Р и в у кг продукта Q , равно 150х + 200у и по условию диеты должно быть не меньше 300:

Теперь о стоимости z продуктов. Она равна

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

Последнее записывается так:

Тем самым мы получили систему формул:

которую решим графическим способом.

Нас интересует только та ее часть, которая лежит над треугольником BDE . Вычисляя значения z во всех трех вершинах этого треугольника

и сравнивая полученные результаты, замечаем, что наименьшее значение (35) достигается в вершине Е. Таким образом,

и искомая пропорция — 2 : 3.

2.2. Задача о выпуске продукции

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

Ссылка на основную публикацию
Adblock
detector