Российский экономический



Download 4,38 Mb.
Pdf ko'rish
bet73/134
Sana01.12.2022
Hajmi4,38 Mb.
#876044
TuriУчебник
1   ...   69   70   71   72   73   74   75   76   ...   134
Bog'liq
Модели исследования операций Фомин

6.
2. Примеры задач 
целочисленного программирования 
В параграфе рассматриваются примеры решения задач, ни одна из кото-
рых не является ярко выраженной задачей целочисленного программирования. 
Значительно больший интерес представляют открываемые целочисленным 
112


программированием возможности приведения «некорректных» задач к стан-
дартному виду задач математического программирования. Использование спе-
циальных приемов позволяет получить решение в ряде случаев, когда решить 
задачу с помощью прямых методов оказывается крайне затруднительным. 
 
Пример 
(задача с постоянными элементами затрат).
 
В одной из типичных за-
дач планирования производства рассматривается 
N
видов промышленной про-
дукции. Затраты на производство продукции вида 
j
складываются из постоянных 
затрат в объеме 
𝐾
𝑗
, не зависящем от количества произведенной продукции и те-
кущих издержек 
𝑐
𝑗
на производство единицы продукции.
 
Таким образом, если 
𝑥
𝑗
— объем выпуска продукции вида 
j
, функцию сум-
марных затрат можно записать следующим образом: 
𝐶
𝑗
(𝑥
𝑗
) = {
𝐾
𝑗
+ 𝑐
𝑗
𝑥
𝑗
, 𝑥
𝑗
> 0
0, 𝑥
𝑗
= 0

Естественным выглядит стремление минимизировать величину суммарных 
затрат: 
𝑧 = ∑
𝐶
𝑗
(𝑥
𝑗
) → min
𝑁
𝑗=1

Рассматриваемый критерий не является линейным по переменной 
𝑥
𝑗
вслед-
ствие разрыва в начале координат. Поэтому задача с целевой функцией 
z
оказы-
вается непригодной для дальнейшего исследования классическими методами. 
Введение дополнительных булевых переменных позволяет преобразовать за-
дачу к виду, «более приемлемому» с аналитических позиций. Пусть: 
𝑦
𝑗
= {
0, 𝑥
𝑗
= 0
1, 𝑥
𝑗
> 0

что можно переписать в форме (линейного) неравенства: 
𝑥
𝑗
≤ 𝑀𝑦
𝑗

Здесь 
М > 0
достаточно велико, чтобы условие 
𝑥
𝑗
≤ 𝑀
выполнялось для всех 
допустимых объемов выпуска продукции. Теперь исходную задачу можно 
сформулировать следующим образом: 
𝑧 = ∑
𝐶
𝑗
𝑥
𝑗
+ 𝐾
𝑗
𝑦
𝑗
→ min
𝑁
𝑗=1

0 ≤ 𝑥
𝑗
≤ 𝑀𝑦
𝑗
, 𝑗 = 1, … , 𝑁

𝑦
𝑗
∈ {0,1}, 𝑗 = 1, … , 𝑁

Рассмотрим подробнее ограничение 
𝑥
𝑗
≤ 𝑀𝑦
𝑗
. При условии 
𝑥
𝑗
> 0
имеем 
𝑦
𝑗
= 1
, и целевая функция включает постоянные затраты 
𝐾
𝑗
. Если 
𝑥
𝑗
= 0
, то 
𝑦
𝑗
может принимать значения 0 или 1, однако поскольку 
𝐾
𝑗
> 0
и 
z
требуется ми-
нимизировать, переменная 
𝑦
𝑗
, должна быть равна нулю. 
Следует подчеркнуть, что исходная задача с постоянными элементами 
затрат не имеет никакого отношения к целочисленному программированию. 
Тем не менее «преобразованная» задача представляет собой частично целочис-
ленную задачу с булевыми переменными («0 – 1» задачу). Необходимость рас-
смотренного преобразования была обусловлена исключительно аналитически-
ми соображениями. В самом деле, введенные булевы переменные являются 
вспомогательными, так как ассоциированную с ними информацию можно 
назвать полезной лишь условно. Например
𝑦
𝑗
= 0
в оптимальном решении 
означает, что 
𝑥
𝑗
> 0


Download 4,38 Mb.

Do'stlaringiz bilan baham:
1   ...   69   70   71   72   73   74   75   76   ...   134




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish