Модели и методы линейного программирования

Модели и методы линейного программирования

4.1. Основные понятия

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

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

Пример 1. Фабрика на месячную производственную программу имеет ресурсы трех видов: рабочую силу (800 чел/дн), оборудование (1400 станков/ч), сырье (4080 т) и может выпускать четыре вида продукции, цены реализации на которые известны. Заданы нормы расхода ресурсов на производство единицы каждого вида продукции. Вся информация записывается в табл. 4.1.

 

Таблица 4.1

Требуется найти такой  план производства продукции, при котором  будет

максимальна общая стоимость  ее выпуска. Приведенная формулировка

называется экономической  постановкой задачи.

Экономико-математическая модель задачи имеет вид:

 

где X = (x1, x2, x3, x4)T – вектор объемов производства каждого вида продукции.

Задача (4.1) называется задачей  линейного программирования.

 

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

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

три формы: произвольную, симметричную и каноническую.

Транспортная  задача

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

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

Математическая постановка этой задачи имеет вид

перевозок, стоится замкнутый  прямоугольный цикл (цепочка) с вершинами  в заполненных клетках (в том числе символом 0).

Выбранной клетке присваивается  знак «+», следующей вершине цикла по (или против) часовой стрелке – знак «–», далее «+»,«–», и т.д. по циклу. Данная цепочка знаков обязательно заканчивается знаком «–». Цепочка называется вырожденной, если она состоит из одного элемента.

Среди клеток цикла, отмеченных знаком «–», выбирается клетка с наименьшим значением переменной Хij, затем из нагрузки клеток, отмеченных знаком «–», вычитают это значение, а клетки, отмеченных знаком «+», прибавляют это значение. Получают новый опорный план, который проверяют на невырожденность и в случае необходимости выполняют переход к невырожденному по варианту 1.

После этого осуществляется переход к шагу 1.

 

Maxsus hollar

1. Mahsulotlarni eltishni taqiqlash usuli.

Bunday masalalar, masalan, biror ta’minotchidan biror iste’molchi olib boruvchi yo’l berk bo’lishi (remont ishlari munosabati bilan) mumkin. Buni hal qilish uchun, marshrut mumkin bo’lmagan katakka minimallashtirish masalasida yetarli katta M>0 son qo’yib yechiladi. Qolgan barcha hisoblash ishlari risoladagidek davom ettiriladi.

2. Marshrut imkoniyati chegaralangan holat.

Ba’zan, marshrutlarning imkoniyati chegaralangan bo’lishi mumkin. Masalan, i-ta’minotchidan j-iste’molchiga yetaklovchi marshrut imkoniyati q birlik bo’lsin. Bunday holda j-iste’molchining ustuni ikki ustunga ajratiladi: va , . Birinchi ustundagi talab gat eng, ikkinchi ustundagi talab esa, gat eng deb olinadi. I-satrning ustunidagi katakning bahosi taqiqlangan katak deb hisoblab, uning qiymatinini M deb olamiz (M yetali katta musbat son). usuniga mos katak bahosi esa odatdagidek ga teng deb olinadi. Qolgan hisoblash ishlari odatdagidek davom ettiriladi.

3-Misol. 1- misolda keltirilgan transport masalasini qo’shimcha shart: barcha iste’molchilarning talabi tekis qondirilsin.

Bunday masalani yopiq transport masalasiga keltirish uchun, barcha iste’molchilarning talabi kamaytiriladi. Buning uchun iste’molchilarning talab miqdorlari koeffitsientga ko’paytiriladi. Sun’iy ta’minotchi kiritishga hojat qolmaydi.

Paketlar

Bu kabi masalalarni albatta kompyuter dasturlarida ishlash mumkin. Bular Maple, Tora, Per kabi dasturlaridir.

_***_

II-bob

+

Odnorodniy tovarlar emas boshqa tovarlar ham

3. Turli mahsulotli transport masalasi.

Iste’molchilarga har xil turdagi mahsulotlarni eltish zaruriyati tug’ilgan bo’lsin. Bunday masalalarni yechishda har bir ta’minotchi turli mahsulot bo’lsa, shuncha ta’minot shaxobchlariga ajratiladi; iste’molchilarning turli mahsuloti ta turli shartli iste’molchilarga ajratiladi.

Turli mahsulotli transport masalasiga misol ko’raylik.

Biror fermer xo’jaligi 3000 tonna 1-sort va 4000 tonna bug’doy urug’i bor. fermer xo’jaligida esa, mos ravishda 5000 tonna va 2000 tonna 1-va 2- sortli bug’doy urug’lari bor. Urug’lar ikki elevatorga etkazilishi kerak. Birinchi  elevatorga 2000 tonna 1-sort, 3000 tonna 2-sort va 2000 tonna ixtiyoriy sortdagi urug’larni etkazish lozim.

Xuddi shuningdek, 2-elevatorga 8250 tonna urug’  jo’natish kerak bo’lib, shulardan 1000 tonnasi 1-sort 1500 tonnasi 2- sort urug’lar bo’lishi kerak.

Bir tonna urug’ning transport harajatlari: dan va ga mos ravishda 1 va 1,5 birlikka, dan va ga mos ravishda 2 va 1 birlikka teng. Transport harajatini minimallashtiruvchi rejani aniqlash kerak.

Har bir ta’minotchini shartli ravishda (bug’doy turiga qarab) ikki ta’minotchiga ajratamiz: va . Har bir iste’molchilar shartli ravishda uchta iste’molchi shaxobchalariga ajratiladi: va (1-sort, 2-sort va ixtiyoriy sort) ; va . Talab taklifdan yuqori bo’lgani uchun, sun’iy ta’minotchi kiritamiz. Jadvalning ba’zi kataklarini yetarli katta son M bilan ajratamiz. Masalan, (1,2) katagini M bilan belgilaymiz, chunki, ta’minotchi iste’molchining talabini qondira olmaydi. ta’minotchida  iste’molchini qondiruvchi urug’ yo’q.

Natijada 38-i jadval hosil bo’ladi.

 

38- jadval

Iste’molchi   Ta’minotchi								Zahira (ming tonna)
		1	M	1	1,5	M	1,5	3
		M	1	1	M	1,5	1,5	4
		2	M	2	1	M	1	5
		M	2	2	M	1	1	2
		0	0	0	0	0	0	1,25
Taklif (ming tonna)		2	3	2	1	1,5	5,75

 

38- jadvaldan foydalanib optimal yechimni aniqlaymiz.

39- jadval

Iste’molchi   Ta’minotchi								Zahira (ming tonna)
		1 2	M	1 1	1,5	M	1,5	3
		M	1 3	1 1	M	1,5	1,5	4
		2	M	2	1 1	M	1 4	5
		M	2	2	M	1 1,5	1 0,5	2
		0	0	0	0	0	0	1,25
Taklif (ming tonna)		2	3	2	1	1,5	5,75

 

 39-jadvalga asosan 1-ta’minotchi 1-iste’molchiga 1-sort urug’dan, 2 ming tonna; 2-sortidan 3 ming tonna va ixtiyoriy sortdan (1- va 2-sortdan) 2 tonna (1-sortdan 1 ming, 2-sortdan 1 ming tonna junatadi).

Ikkinchi ta’minotchi ikkinchi elevatorga 1-sort bug’doydan 1 ming tonna, 2-sortidan 1,5 ming tonna, ixtiyoriy sortdan 4,5 tonna jo’natadi. Ikkinchi elevatorning ixtiyoriy sort uchun bo’lgan talabi to’la qondirilmaydi ( 1,25 ming tonna etkazilmaydi). Minimal harajat birlikka teng bo’ladi.

+

Cij – o’zgargan holiga e’tibor qaratish

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

 

 

при ограничениях:

 

 

где c_j, a_ij, b_i — постоянные величины. Однако на практике сталкиваются с тем, что эти величины изменяются в некоторых интервалах. Кроме того, определив оптимальное решение экономической задачи при заданных c_j, a_ij и b_i, целесообразно знать, в каких допустимых пределах можно их менять, чтобы решение оставалось оптимальным. Поэтому возникает необходимость исследовать поведение оптимального решения задачи линейного программирования в зависимости от изменения коэффициентов ее целевой функции, системы ограничений и коэффициентов целевой функции и системы ограничений. Ограничимся рассмотрением зависимости оптимального решения от изменения коэффициентов целевой функции.

 

 

 

25.4. Транспортная  параметрическая задача

 

Задача формулируется  следующим образом: для всех значений параметра δ ≤ λ ≤ φ, где δ, φ — произвольные действительные числа, найти такие значения x_ij (i = ; j = ), которые обращают в минимум функцию

 

 

при ограничениях:

 

 

Пользуясь методом потенциалов, решаем задачу при λ = δ до получения оптимального решения. Признаком оптимальности является условие:

 

u_i + v_j — [c'_ij + λс"_ij) ≤ 0 для незанятых клеток

и u_i + v_j = с' _ij + λс''_ij для занятых клеток,

где u_i, v_j — потенциалы строк, столбцов распределительной таблицы.

Условие совместимости транспортной задачи запишется в виде

 

 

Значения α_ij и β_ij определяются из условия

 

 

где u'_i, v'_i, u"_j, v"_j определяются из систем уравнений

 

 

Значения λ находятся в пределах λ₁ ≤ λ ≤ λ₂:

 

 

Алгоритм решения.

1) Задачу решаем при  конкретном значении параметра  λ = δ до получения оптимального решения.

2) Определяем α_ij и β_ij.

3) Вычисляем значения  параметра λ.

4) Если λ < φ, производим перераспределение поставок и получаем новое оптимальное решение. Если λ = φ, то процесс решения окончен.

 

25.5. Нахождение  оптимальных путей транспортировки  грузов при нестабильной загрузке  дорог

 

Имеются три поставщика однородного  товара с объемами поставок: а₁ = 100 т, а₂ = 200 т, a₃ = 100 т и четыре потребителя с объемами потребления b₁ = - 80 т, b₂ = 120 т, b₃ = 150 т, b₄ = 50 т. Стоимость транспортных расходов изменяется в определенном диапазоне в зависимости от загрузки дороги и задана матрицей

 

 

Определить оптимальное  решение перевозок, обеспечивающее минимальные транспортные затраты.

Решение. В матрицу расходов введем параметр λ, где 0 ≤ λ ≤ 3. Получим

 

 

Полагая λ = 0, решаем задачу методом потенциалов, определим оптимальное решение перевозок. Распределительная таблица этого решения будет иметь вид табл. 25.5.

 

 

В таблице u_i и v_j — потенциалы строк и столбцов. Для занятых клеток они определяются из условия

 

 

Полагая u₁ = 0, v₁ + и₁ = 5 + 2λ, получаем v₁= 5 + 2λ,

v₂ + и₁ = 4 — λ, откуда v₂ = 4 — λ;

v₁ + u₂ = 4 или 5 + 2λ + u₂ = 4, откуда и₂ = -1 - 2λ;

v₃ + u₂ = 4 + 2λ или -1 – 2λ + v₃ = 4 + 2λ, v₃ = 5 + 4λ.

Аналогично находим, что u₃ = -1 + λ, v₄ = 2 + 2λ.

Оценки свободных клеток находим по формуле

 

 

Имеем

 

 

Аналогично находим, что  Δ₂₄ = -6 + λ, Δ₃₁ = -1 + 3λ, Δ₃₃ = -2 + 5λ.

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

 

 

Имеем

 

 

Так как по условию задачи λ ≥ 0, то оптимальное решение  сохраняется при 0 ≤ λ ≤ 1/3. При  этом минимальная стоимость транспортных расходов составляет

 

 

Таким образом, при λ  [0; 1/3] L(X₁)_min = 1430 + 440λ и

 

 

Чтобы получить оптимальное  решение при λ ≥ 1/3, перераспределим поставки товаров в клетку (3, 1), где λ₂ = 1/3. Вновь полученное распределение представлено в табл. 25.6.