Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Лекция 1. Вводные понятия математического программирования

ВВЕДЕНИЕ

 

 

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

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


 

 

 

План

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

2. Задачи линейного программирования.

 

 

1. Введём необходимые термины.

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

методов и алгоритмов их решения.

Рассмотрим произвольную экономико-математическую модель с неиз-


вестными


x 1,


x 2,…,


xn. В зависимости от ситуации этими неизвестными могут


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

В общем виде задачи МП состоят в определении максимального или ми-

нимального значения целевой функции

Z = f (x 1; x 2;...; xn) → max (min), (1)

где f – функция произвольного типа.

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

– общие транспортные расходы предприятия, себестоимость продукции, коли-


чество отходов производства, риск инвестиций и т.д., то


Z → min.


Ресурсы – материальные, технические, человеческие, денежные и др. –


ограничены. Обозначим запасы ресурсов через


b 1,


b 2,…,


bm. Оптимальное ре-


шение должно удовлетворять системе ограничений:

⎪ 2 1 2 n 2
⎧Φ1(x 1; x 2;...; xn) ≤ b 1

⎪Φ (x; x;...; x) ≤ b

.................................


 

(2)


Φ m (x 1; x 2;...; xn) ≤ bm

Заметим, что ограничения могут быть неравенствами со знаками ≤ или ≥, а


также равенствами. Функции Φ i


(i =1, m) могут быть произвольными.


Если практический смысл задачи МП исключает отрицательные значения переменных, то дополнительно налагают условие не отрицательности:

x j ≥ 0 (j =1, n) (3)

Случается, что неизвестные могут быть только целыми числами. Напри-


мер,


x 1,


x 2,…,


xn отображают неделимые величины (количество тракторов,


 

комбайнов, автомобилей, построенных домов, единиц бытовой техники, чис-

ленность работников). Тогда налагают условие целочисленности:

x j ∈ ] (j =1, n), (4)

где ] – множество целых чисел. В отличие от целевой функции Z символ ]

пишут с двойной «спинкой».

Задачи с условием (4) выделяют в отдельный класс задач МП. Их назы-

вают задачами целочисленного программирования.

Бывает, что неизвестные – это переменные биномиального типа, т.е.

x j ∈{0;1} (j =1, n). (5)

Например, значение 0 характеризует факт, что экскаватор не назначен на

j -й объект, а значение 1 – экскаватор работает на данном объекте.

Допустимым решением (планом) называют любой n -мерный вектор

X = (x 1; x 2;...; xn), удовлетворяющий системе ограничений (2) (и условиям (3),

(4) или (5) при необходимости). Множество таких векторов образует область допустимых решений (далее ОДР). Оптимальным решением


X * = (x 1*; x 2*;...; xn *)


называется допустимое решение, при котором целевая


функция достигает экстремума.

При решении громоздких задач МП используют компьютерную технику.

Особенно популярны электронные таблицы и вычислительные математические системы (MS Excel, WinQSB и др.).

 

 

2. В рамках МП особое место занимают задачи линейного программирова-

ния (далее ЛП). В этом случае и целевая функция (1), и левые части ограниче-


ний (2) являются линейными функциями. Т.е. искомые переменные x j


(j =1, n)


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

Начало линейной оптимизации было положено в 1939 г., когда профессор

Ленинградского университета Л.В. Канторович (1912-1986) опубликовал свою работу «Математические методы организации и планирования производства».

Став впоследствии академиком, Л.В. Канторович удостоился звания лауреата

Ленинской премии (1964) и Нобелевской премии по экономике (1975).

Параллельно с советскими учёными схожими проблемами занимались и западные учёные. Термин «линейное программирование» впервые появился в

1951 г. в работах Дж. Данцига и Т. Купманса.

Пример 1 (Задача оптимального выпуска продукции). Пусть предпри-


ятием выпускается n видов продукции


P 1,


P 2,…, Pn


из m видов сырья


S 1,


S 2,…,


Sm. Известны запасы сырья


b 1,


b 2,…,


bm, расходы


aij


(i =1, m; j =1, n) i -


го сырья на производство единицы j -й продукции и цены реализации c j

ницы продукции j -го вида.


еди-


 

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

Решение. Составим табл. 1.

 

 

Табл. 1. Данные задачи

Сырьё Продукция Запасы сырья
P 1 P 2 … Pn
S 1 S 2 … Sm a 11 a 12 … a 1 n a 21 a 22 … a 2 n … … … … am 1 am 2 … amn b 1 b 2 … bm
Цена реализации единицы продукции c 1 c 2 … cn  
Количество продукции x 1 x 2 … xn

 

 


Здесь переменные x j


(j =1, n) – количество продукции j -го вида, кото-


рое предполагается выпускать. Тогда


c j x j


– стоимость продукции j -го вида.


Пусть Z – стоимость всей выпускаемой продукции. Поэтому целевая функция


приобретает вид


Z = c 1 x 1 + c 2 x 2 + ⋅⋅⋅ + cn xn. Затраты сырья


S 1 на всю выпускае-


мую продукцию составляют


a 11 x 1 + a 12 x 2 + ⋅⋅⋅ + a 1 nxn. Затраты не могут превы-


шать запасов


b 1, поэтому


a 11 x 1 + a 12 x 2 + ⋅⋅⋅ + a 1 nxnb 1. Аналогичные неравенства


будут получены и для остальных видов сырья. По смыслу задачи все перемен-

ные должны быть неотрицательными.

Математическая модель этой задачи ЛП имеет вид:

Z = c 1 x 1 + c 2 x 2 + ⋅⋅⋅ + cn xn → max, (6)

+ a x + ⋅⋅⋅ + a xb
a 11 x 1 + a 12 x 2 + ⋅⋅⋅ + a 1 n xnb 1

a 21 x 1 22 2 2 n n 2


⎪.......................................

⎪⎩ am 1 x 1 + am 2 x 2 + ⋅⋅⋅ + amn xnbm


(7)


x j ≥ 0 (j =1, n). (8)

Для примера 1 задача ЛП (6)-(8) составлена. Другими известными зада-

чами ЛП являются задача о рационе откорма животных, задача раскроя ма-

териалов, транспортная задача, задача о назначениях.

Домашнее задание. Самостоятельно найти в учебниках модели перечис-

ленных задач ЛП и записать в конспект лекций.

Т.о. математическая модель задачи ЛП составляется по схеме: 1) вводят переменные; 2) составляют целевую функцию; 3) записывают ограничения; 4)

при необходимости налагают условия не отрицательности, целочисленности,

биномиальности переменных.


 

<== предыдущая лекция | следующая лекция ==>
Методы политологии | Лекция 2. Геометрическая интерпретация решения задач линейного программирования
Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 660; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.046 сек.