Invest-currency.ru

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читать еще:  Type mismatch паскаль

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

Задачи

Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида [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. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка области допустимых решений системы ограничений, и наоборот.

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

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

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

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

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

Читать еще:  Что значит crt паскаль

Задача оптимального раскроя материала. Фирма изготовляет изделие состоящее из р деталей. Причем в одно изделие эти детали входят в количествах 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) при тех же предпосылках моделирует минимизацию затрат при фиксированном уровне дохода.

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

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

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

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

Общий вид задач линейного программирования (ЗЛП):

1. Функция, чьи экстремумы надо найти

2. Система ограничений в виде равенств или неравенств

3. Условие не отрицательности входных параметров

В математическом виде ЗЛП записывается:

A — Матрица состоящая из коэффициентов при ограничений

b – Вектор ресурсов (вектор свободных коэффициентов)

с – вектор решений (коэффициенты целевой функции)

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

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

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

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

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

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

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

Найти неотрицательные значения переменных х1, х2, … хn, которые удовлетворяли бы условиям-равенствам и обращали бы целевую функцию в максимум.

Читать еще:  Классификация языков программирования

Для приведения произвольной ЗЛП к ОЗЛП необходимо:

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

a. Если левая часть меньше или равна свободному члену, то в левую часть добавляют новую переменную и знак неравенства меняют на знак равенства

b. Если левая часть больше или равна свободному члену, то в левую часть добавляют новую переменную со знаком минус и знак неравенства меняют на знак равенства

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

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

Дата добавления: 2015-01-12 ; просмотров: 12 | Нарушение авторских прав

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

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

Стандартная математическая формулировка общей задачи линейного программирования выглядит так: требуется найти экстремальное значение показателя эффективности (целевой функции)

или min

(линейной функции элементов решения ) при линейных ограничительных условиях, накладываемых на элементы решения:

где — заданные числа.

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

Ведь в данном случае целевая функция z=ax+by –задает уравнение плоскости в декартовой системе координат,

Задают область в плоскости xOy.

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

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

Вникать в эти методы решения на данном этапе нет смысла.

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

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

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

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

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

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

1. Задаем вопрос. Что мы хотим получить?

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

3. Определяем переменные, которые будем варьировать Xi, составляем целевую функцию,

4. Определяем граничные условия.

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

6. Проверяем решение на непротиворечивость. (если решение явно неверное, то возможны два случая :неверно определены параметры, либо не все условия мы учли).

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

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

Задача о диете (рационе)

Одна женщина посоветовала подруге перейти на рациональное питание, состоящее из двух продуктов 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) достигается в вершине Е. Таким образом,

В общем виде задача о диете, оптимальном рационе.

Кол-во единиц питательных веществ, содержащихся в единице продукции вида

Ссылка на основную публикацию
ВсеИнструменты 220 Вольт
Adblock
detector