Математическое программирование



Скачать 110.26 Kb.
Дата16.10.2012
Размер110.26 Kb.
ТипУрок
Лекция № 1

Тема: Математическое программирование

Цель урока: Ознакомить студентов с элементами математического программирования.

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

2) Задача выпуклого программирования.

3) Выпуклые множества и выпуклые функции.

В общем случае задача математического программирования формулируется следующим образом. Найти экстремум функции , где принадлежит п- мерному пространству Еп или некоторой части его. Функция в этом случае называется целевой. Если ограничения отсутствуют, то задача математического программирования сводится к задаче на безусловный экстремум. Если же записанные ограничения в виде равенства =0, то имеем задачу на условный экстремум. В математическом программировании выделяют линейное программирование – когда функции и линейны, квадратичное программирование, когда - квадратичная форма, а - линейные функции, и нелинейного программирования, когда u - нелинейные функции.

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

Определение 1. Множество Х  Rn называется выпуклым, если

При всех х1, х2 Х,   [0,1]. То есть множество Х выпукло, если оно вместе с любыми своими двумя точками х1 и х2 содержит соединяющий их отрезок, то есть множество вида



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

(1)

Где А – некоторая матрица размера m x n со строками а1, а2, ….., аm , b=(b1, b2,…..,bm) Rm (m=1,2,…..)

Множества вида (1) называются полиэдрами. Полиэдр – это множество решений некоторой системы конечного числа линейных неравенств.

Определение 2. Функция,  определенная на выпуклом множестве Х  Rn , называется выпуклой на Х, если

(2)

При всех х1, х2 Х,   [0,1]. Если при всех х1, х2 Х, х1х2 и   [0,1] неравенство (2) выполняется как строгое, то  называется строго выпуклой на Х.

Определение 3. Задача вид (3)

называется выпуклой, если Х – выпуклое множество,  - выпуклая функция на Х.

Теорема. Пусть функция  - выпукла на Rn и дифференцируема в точке х  Rn. Если , то х - точка минимума  на Х, то есть решение задачи (4).

(4)

Определение 4. Задача

i=1,2,….r. xP (5)-

называется задачей выпуклого программирования, если множество Р выпу-кло, функции , g1, g2,……,gr выпуклы на Р, функции gi+1, gi+2,….,gm – линей-ны.

Пример (планирование производства). Пусть имеется предприятие, выпускающее определенный товар и использующее при этом n – ресурсов. Предприятие характеризуется технологическим множеством Х Rn, указывающим всевозможные наборы ресурсов, из которых может быть получен данный товар, и производственной функцией (х), показывающий объем выпуска при наборе затраченных ресурсов х= (х12,…..,хn) Х. Множество Х определяется условиями

х1 0, ai x1  xi  bix1, i=1,2,…..n

где ai,bi – заданные числа, 0 ai bi, то есть пропорции между затратами первого и остальных ресурсов должны находится в определенных пределах. В качестве производственной функции часто фигурирует функция Кобба – Дугласа

где 0, 1  0, ………,n0 – заданные числа, . Отметим, что эта функция вогнута.

Пусть pi 0 – известная цена единицы i – го ресурса, р = (р12,……..n) – вектор цен на ресурсы. Тогда р, х - денежная стоимость данного набора ресурсов х. Если 0 – денежные средства предприятия, то сформулируем задачу о максимизации объема выпуска в рамках бюджетных и технологических ограничений:



Если задан параметр   0 – плановое задание предприятию по выпуску товара, то можно сформулировать задачу минимизации издержек производства при безусловном выполнении плана:



Лекция № 2

Тема: Линейные математические модели. Постановка задачи линейного программирования

Цель урока: Ознакомить студентов с математическими моделями, с постановкой задачи линейного программирования.

План урока: 1) Постановка задачи линейного программирования.

2) Линейное программирование в экономике.

Большое число задач оптимизации приводится к линейным математическим моделям. Традиционно оптимизационные линейные математические модели называются моделями линейного программирования. Под линейным программированием понимается линейное планирование, то есть получение оптимального плана – решения в задачах с линейной структурой.

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

Максимизировать (минимизировать) функцию:

(1)

При ограничениях



где хj – решение задачи, аij, bi – параметры,  - целевая функция.

Функция (1) – линейная, ограничения (2), (3), (4) – линейные.Задача содержит n – переменных и m – ограничений.

Решить задачу линейного программирования – это значит найти значения управляющих переменных хj, удовлетворяющих ограничениям (2), (3), (4), при которых целевая функция принимает максимальное или минимальное значения.

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

Ограничения характеризуют имеющиеся возможности решения задачи.

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

Решение, удовлетворяющее условиям задачи и соответствующее намеченной цели, называется оптимальным планом.

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

Условия задачи (ограничения) могут быть заданы также в виде неравенств. В этих случаях можно привести систему линейных ограничений к виду (2),(3), введя в каждое линейное ограничение дополнительные неотрицательные неизвестные:



Определение 1. Стандартной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (1) при выполнении условий (2) и (3).

Определение 2.Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (1) при выполнении условий (2).

Определение 3. Совокупность чисел Х=(х12, …… ,хn) – удовлетворяющих ограничениям задачи, называются допустимым решением (или планом).

Определение 4. План Х = (х1 2 , …… ,хn) – при котором целевая функция задачи принимает максимальное (минимальное) значение, называется оптимальным.

В случае, когда требуется найти минимум функции

,

можно перейти к нахождению максимума функции



Так как min F(X)=-max F1(X).

Ограничения – неравенства исходной задачи линейного программирования, имеющие вид «», преобразуется в ограничение – равенство с добавлением к левой части дополнительной неотрицательной переменной, а ограничение – неравенство вида «» - преобразуется в ограничение – равенство вычитанием из левой части дополнительной неотрицательной переменной.

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

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

(5)

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

Определение 5. План - называется опорным планом основной задачи линейного программирования, если система векторов , входящих в разложение (5) с положительными коэффициентами хj , линейно независима.

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

Определение 6. Опорный план называется невырожденным , если он содержит ровно m положительных компонент. Если в опорном плане число положительных компонент меньше m , то план является вырожденным.

В зависимости от целевой функции и ограничений можно выделить несколько типов задач линейного программирования: 1) общая линейная задача; 2) транспортная задача; 3) задача о назначениях.

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

Задача об оптимальном использовании сырья. Предприятие производит изделия трех видов, поставляет их заказчикам и реализует на рынке. Заказчикам требуется 1000 изделий первого вида, 2000 изделий второго вида и 2500 изделий третьего вида.

Условия спроса на рынке ограничивают число изделий первого вида 2000 единицами, второго – 3000 и третьего – 5000 единицами.

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

Как организовать производство, чтобы:

  1. Обеспечить заказчиков;

  2. Не допустить затоваривания;

  3. Получить максимальную прибыль?

Тип ресурсов

Виды изделий

Всего ресурсов

1

2

3

1

500

300

1000

25000000

2

1000

200

100

30000000

3

150

300

200

20000000

4

100

200

400

40000000

прибыль

20

40

50






Построение математической модели.

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

  1. Цели – получение максимальной прибыли.

  2. Параметрами являются все числовые данные, приведенные в условии задачи.

  3. Управляющие переменные:

х1 – число изделий первого вида;

х2 – число изделий второго вида;

х3 – число изделий третьего вида;

  1. Ограничения: обеспечить заказчиков, не превысь запас ресурсов, не допустить затоваривания рынка.

В соответствии с этими ограничениями выпишем область допустимых решений задачи:

(6)

Первые три неравенства в системе (6) соответствуют спросу заказчиков. Неравенства с четвертое по шестое формализуют спрос на рынке. Последние четыре неравенства соответствуют ограничениям по ресурсам.

  1. Целевая функция или критерий эффективности задачи имеет вид

P=20x1 + 40x2 + 50x3 max (7)

В формуле буквой Р обозначена прибыль. Ее надо максимизировать. Каждое слагаемое определяет прибыль от производства изделий каждого вида соответственно в количествах х1, х2, х3.

Формулы (6) – (7) - математическая модель поставленной задачи. Ограничения и целевая функция линейны по управляющим переменным, следовательно, данная модель является линейной.

Лекция № 3

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

Похожие:

Математическое программирование iconПеречень вопросов для вступительного экзамена в аспирантуру по специальности 05. 13. 18 «Математическое моделирование, численные методы и комплексы программ» Математические основы
Математическое программирование, линейное программирование, выпуклое программирование
Математическое программирование iconУчебной дисциплины «Выпуклый анализ и математическое программирование» для направления 010400. 62 Прикладная математика и информатика
Целями освоения дисциплины (модуля) «Выпуклый анализ и математическое программирование» являются
Математическое программирование iconРабочая программа по курсу "Функциональное программирование" Специальность: 351500. 65 «Математическое обеспечение и администрирование информационных систем»
«Функциональное программирование» составлена на основании Государственного образовательного стандарта высшего профессионального образования...
Математическое программирование iconЛинейное программирование задачи математического и линейного программирования
Соответствующие методы, позволяющие решать указанные задачи, объединяются под общим названием «математическое программирование»
Математическое программирование iconМоделирование потоков
Математическое программирование построения бухгалтерских и управленческих отчетов
Математическое программирование iconПрограмма конференции «математическое программирование и приложения»
Бердышев В. И. (Екатеринбург). Минимизация максимальной видимости движущегося объекта
Математическое программирование iconРабочая программа по курсу "Рекурсивно-логическое программирование" Специальность: 351500. 65 «Математическое обеспечение и администрирование информационных систем»
Специальность: 351500. 65 «Математическое обеспечение и администрирование информационных систем», дс
Математическое программирование iconЛинейная алгебра и математическое программирование
Понятие и свойства обратной матрицы. Присоединенная матрица и ее связь с обратной матрицей
Математическое программирование iconПрограмма дисциплины оптимизация и математическое программирование для аспирантов 2-го года обучения Разработана
В результате прохождения курса студент должен: получить целостное представление об оптимизационном подходе к проблемам управления...
Математическое программирование iconВопросы к зачету по дисциплине математическое программирование для студентов 2 курса экономического факультета очной и заочной формы обучения
Применимость задач линейного программирования к анализу деятельности экономического объекта
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org