Моделювання задач лінійного програмування та розв’язання їх розподільчим методом

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

Прилади й обладнання: калькулятор.

Короткі теоретичні відомості

Економічний зміст задач лінійного програмування, які розв’язують розподільчим методом, може стосуватися різноманітних проблем, таких, як: оптимізація перевезення вантажів (транспортна задача), розміщення виробництв, складів, визначення оптимального призначення тощо.

За умовами класичної транспортної задачі деякий однорідний продукт, що знаходиться у m постачальників А_і в обсягах  одиниць відповідно необхідно перевезти n споживачам В _j в обсягах  одиниць. У збалансованій (закритій) транспортній задачі виконується умова, за якою загальний наявний обсяг продукції у постачальників дорівнює загальному попиту всіх споживачів. Відомі  вартості перевезень одиниці продукції від кожного А_і постачальника до кожного В _j споживача (або відстані між постачальниками і споживачами), що подані як елементи матриці виду:

 

 

Необхідно визначити план перевезень, за якого вся продукція була б вивезена від постачальників, повністю задоволені потреби споживачів і загальна вартість усіх перевезень була б мінімальною (або обсяг вантажу на 1 км). У такому разі ефективність плану перевезень визначається його вартістю або обсягом вантажоперевезень.

Оптимальним планом транспортної задачі називають матрицю, яка задовольняє умови й обмеження задачі та для якої цільова функція набуває найменшого значення.

Порядок виконання роботи

Під час складання проекту організації території сільськогосподарського підприємства велика рогата худоба (ВРХ) була певним чином розташована на трьох фермах (таблиця 4.1).

Таблиця 4.1 – Розміщення ВРХ на фермах

Номер ферми	Вид тварин	Поголів’я, голів	Необхідний обсяг кормів, тонн
1	Корови	840	6570 +  (5600)
2	Корови	830	6480 +  (5480)
3	Молодняк	2870	16540 + ij (13820)
	Усього ВРХ	4540	29590 +  (24900)

Примітка: ij – порядковий номер студента у списку групи, у дужках вказані вихідні дані для прикладу розрахунку.

 

Річний запас грубих і соковитих кормів зберігається на території ферм на кормових ділянках.

З урахуванням такого розміщення тварин на фермах у проекті передбачено організувати таку кількість сівозмін (таблиця 4.2).

Таблиця 4.2 – Система сівозмін, що проектується

Сівозміна	Обсяг перевезень кормів, тонн
I польова	6450 + ij (5414)
II польова	5490 + ij (4614)
III польова	15300 + ij (12789)
I кормова	1110 + ij (971)
II кормова	585 + ij (526)
III кормова	655 + ij (586)
Усього	29590 +  (24900)

Примітка: ij – порядковий номер студента у списку групи, у дужках указані вихідні дані для прикладу розрахунку.

Необхідно обґрунтувати закріплення сівозмін за фермами. Критерієм оптимальності є мінімальний обсяг перевезень кормів. Середні відстані від сівозмін до ферм наведені в таблиці 4.3.

Таблиця 4.3 – Середні відстані від сівозмін до ферм (відстані у кілометрах)

Сівозміна	Ферма 1	Ферма 2	Ферма 3
I польова	4, 0+ i, j (7, 6)	1, 8 + i, j (5, 5)	7, 0 (10, 7)
II польова	2, 5 + i, j (6, 1)	4, 8 + i, j (9, 4)	5, 0 + i, j (8, 6)
III польова	5, 2 + i, j (8, 9)	6, 0 (9, 6)	2, 2 + i, j (5, 8)
I кормова	6, 5 (10, 2)	5, 3 + i, j (8, 9)	1, 8 + i, j (5, 5)
II кормова	1, 4 + i, j (5, 1)	5, 8 (9, 4)	7, 2 (10, 8)
III кормова	4, 2 (8, 0)	1, 5 + i, j (5, 2)	6, 2 + i, j (9, 8)

Примітка: ij – порядковий номер студента у списку групи, у дужках вказані вихідні дані для прикладу розрахунку.

    Алгоритм розв’язання економіко-математичної задачі землеустрою розподільчим методом розглянемо на конкретному прикладі.

1. Уводять умовні позначення.

Обсяги кормів, які перевозяться з відповідних сівозмін на ферми:

x ₁₁, x ₁₂, x ₁₃

x ₂₁, x ₂₂, x ₂₃

x ₃₁, x ₃₂, x ₃₃

………….

x ₆₁, x ₆₂, x ₆₃

Обсяги виробництва кормів на відповідних сівозмінах: .

Потреби ферм у кормах: b ₁, b ₂, b ₁.

Коефіцієнти цільової функції (середні відстані в км від сівозмін до ферм):

с₁₁, с₁₂, с₁₃

с₂₁, с₂₂, с₂₃

с₃₁, с₃₂, с₃₃

………….

с₆₁, с₆₂, с₆₃

2. Складають економіко-математичну модель транспортної задачі.

Необхідно знайти:

за умов:

а) за постачальниками:

 

                                          

        

 

б) за споживачами:

 

,                                                                   

в) умова закритості моделі:

;              

г) умова невід’ємності змінних:

                                                                 

 

 

3. Складають перший опорний план за правилом північно-західного кута (табл. 4.4).

 

 

Таблиця 4.4 – Перший опорний план

№ пор.	Сівозміна	Ферма № 1	Ферма № 2	Ферма № 3	Обсяг виробництва кормів, тон
1	I польова	7, 6 5414	5, 5	10, 7	5414
2	II польова	6, 1 186	9, 4 4428	8, 6	4614
3	III польова	8, 9	9, 6 - 1052	5, 8 +11737	12789
4	I кормова	10, 2	8, 9	5, 5 971	971
5	II кормова	5, 1	9, 4	10, 8 526	526
6	III кормова	8, 0	5, 2 +	9, 8 - 586	586
Потреба в кормах		5600	5480	13820	24900

 

Кількість закритих комірок в опорному плані визначають за формулою:

,

де m – кількість сівозмін; n – кількість ферм.

.

Значення цільової функції для першого плану:

        

        

Для визначення оптимальності плану для кожної вільної його комірки будують замкнений контур (позначається пунктирною лінією), за допомогою якого визначають пробіг на тонну вантажу. Для прикладу в таблиці 4.4 побудований замкнений контур для комірки К₆₂. Початковій вершині замкненого контуру надається знак «+», далі знаки чергуються.

К₁₂ = +5, 5 – 9, 4 + 6, 1 – 7, 6 = –5, 4; К₁₃ = +10, 7 – 5, 8 + 9, 6 – 9, 4 + 6, 1 – 7, 6 = +3, 6; К₂₃ = +8, 6 – 5, 8 + 9, 6 – 9, 4 = +3, 0; К₃₁ = +8, 9 – 6, 1 + 9, 4 – 9, 6 = +2, 6; К₄₁ = +10, 2 – 6, 1 + 9, 4 – 9, 6 +5, 8 – 5, 5 = +4, 2; К₄₂ = +8, 9 – 9, 6 + 5, 8 – 5, 5 = –0, 4; К₅₁ = +5, 1 – 6, 1 + 9, 4 – 9, 6 + 5, 8 – 10, 8 = –6, 2; К₅₂ = +9, 4 – 9, 6 +5, 8 -10, 8 = –5, 2; К₆₁ = +8, 0 – 6, 1 + 9, 4 – 9, 6 + 5, 8 – 9, 8 = –2, 3; К₆₂ = +5, 2 – 9, 6 +5, 8 – 9, 8 = –8, 4.

Для комірок К₁₂, К₄₂, К₅₁, К₅₂, К₆₁, К₆₂ характеристики одержані зі
знаком «–», що вказує на неоптимальність першого опорного плану.

Поліпшення плану починають з тієї комірки, для якої негативна характеристика за абсолютною величиною найбільша. Отже, у план необхідно ввести вільну комірку К₆₂. У від’ємному напівланцюговому контурі для цієї комірки вибирають найменший обсяг вантажу, за яким проводять перерозподіл вантажів (586 тонн), отримуючи другий план вантажоперевезень (таблиця 4.5).

Таблиця 4.5 – Другий план вантажоперевезень

№ пор.	Сівозміни	Ферма № 1	Ферма № 2	Ферма № 3	Обсяг виробництва кормів, тонн
1	I польова	7, 6 5414	5, 5	10, 7	5414
2	II польова	6, 1 186	9, 4 4428	8, 6	4614
3	III польова	8, 9	9, 6 446	5, 8 12323	12789
4	I кормова	10, 2	8, 9	5, 5 971	971
5	II кормова	5, 1	9, 4	10, 8 526	526
6	III кормова	8, 0	5, 2 586	9, 8	586
Потреба в кормах		5600	5480	13820	24900

 

Значення цільової функції для другого плану обчислюють за формулою:

 

де F_{min 1} – значення цільової функції для першого опорного плану; D F – добуток найбільшого від’ємного значення величини пробігу у попередньому плані на обсяг вантажу, що розподіляється по контуру.

Перевірка другого плану на оптимальність:

К₁₂ = +5, 5 – 9, 4 + 6, 1 – 7, 6 = –5, 4; К₁₃ = +10, 7 – 5, 8 + 9, 6 – 9, 4 + 6, 1 – 7, 6 = +3, 6; К₂₃ = +8, 6 – 5, 8 + 9, 6 – 9, 4 = +3, 0; К₃₁ = +8, 9 – 6, 1 + 9, 4 – 9, 6 = +2, 6; К₄₁ = +10, 2 – 6, 1 + 9, 4 – 9, 6 +5, 8 – 5, 5 = +4, 2; К₄₂ = +8, 9 – 9, 6 + 5, 8 – 5, 5 = –0, 4; К₅₁ = +5, 1 – 6, 1 + 9, 4 – 9, 6 + 5, 8 – 10, 8 = –6, 2; К₅₂ = +9, 4 – 9, 6 + 5, 8 – 10, 8 = –5, 2; К₆₁ = +8, 0 – 6, 1 + 9, 4 – 5, 2 = +6, 1; К₆₃ = +9, 8 – 5, 2 +9, 6 – 5, 8 = +8, 4.

Наявність від’ємних значень К свідчить про неоптимальність і цього плану.

4. Подальший порядок обчислень аналогічний наведеному вище – послідовне складання й аналіз планів вантажоперевезень для знаходження оптимального плану. У цьому прикладі оптимальним планом є шостий план (таблиця 4.6).

Таблиця 1.9 – Шостий план вантажоперевезень

№ пор.	Сівозміни	Ферма № 1	Ферма № 2	Ферма № 3	Обсяг виробництва кормів, тонн
1	I польова	7, 6 520	5, 5 4894	10, 7	5414
2	II польова	6, 1 4554	9, 4	8, 6 60	4614
3	III польова	8, 9	9, 6	5, 8 12789	12789
4	I кормова	10, 2	8, 9	5, 5 971	971
5	II кормова	5, 1 526	9, 4	10, 8	526
6	III кормова	8, 0	5, 2 586	9, 8	586
Потреба в кормах		5600	5480	13820	24900

Перевірка шостого плану на оптимальність:

К₁₃ = +10, 7 – 7, 6 + 6, 1 – 8, 6 = +0, 6; К₂₁ = +6, 1 – 7, 6 + 5, 5 – 9, 4 = -5, 4; К₃₁ = +8, 9 – 7, 6 + 5, 5 – 9, 4 +8, 6 – 5, 8 = +0, 2; К₃₂ = +9, 6 – 9, 4 +8, 6 – 5, 8 = +3, 0; К₄₁ = +10, 2 – 7, 6 + 5, 5 – 9, 4 + 8, 6 – 5, 5 = +10, 4; К₄₂ = +8, 9 – 9, 4 + 8, 6 – 5, 5 = +2, 6; К₅₂ = +9, 4 – 5, 1 + 7, 6 – 5, 5 = +6, 4; К₅₃ = +10, 8 – 5, 1 + 7, 6 – 5, 5 + 9, 4 – 8, 6 = +8, 6; К₆₁ = +8, 0 – 7, 6 + 5, 5 – 5, 2 = +0, 7; К₆₃ = +9, 8 – 5, 2 + 9, 4 – 8, 6 = +5, 4.

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

    Отже, за фермою № 1 закріплені: І польова сівозміна – 520 т кормів; ІІ польова сівозміна – 4554 т кормів; ІІ кормова сівозміна – 526 т кормів. За фермою № 2 закріплені: І польова сівозміна – 4894 т кормів; ІІІ кормова сівозміна – 586 т кормів. За фермою № 3 закріплені: ІІ польова сівозміна – 60 т кормів; ІІІ польова сівозміна – 12789 т кормів; І кормова сівозміна – 971 т кормів.

Контрольні питання

1. Алгоритм розподільчого методу.

2. Які задачі лінійного програмування можна розв’язувати розподільчим методом?

3. Умови економіко-математичної моделі транспортної задачі.

4. За яким правилом складають перший опорний план вантажоперевезень?

5. Що є критерієм оптимальності транспортної задачі?

6. Яким чином визначаються значення пробігу для вільних комірок у плані вантажоперевезень?

7. Як обчислюється значення цільової функції у транспортній задачі?

8. Який із усіх можливих планів вантажоперевезень буде оптимальним?

КРИТЕРІЇ ОЦІНЮВАННЯ ЗНАНЬ СТУДЕНТІВ

    До заліку виносяться питання, що наведені після кожної практичної роботи – «Контрольні питання».

    Максимальний бал за виконання практичних робіт у семестрі дорівнює 30 за стобальною шкалою. У таблиці 5.1 наведені критерії оцінювання результатів практичних занять.

Таблиця 5.1 – Критерії оцінювання практичних занять

Номер робо-ти	Тема	Критерії оцінювання	Оцін-ки у балах	Макси-мальний бал
1	Прогнозування використання земельних ресурсів	Відвідування заняття Виконання роботи Захист звіту	2   5 3	10
2	Моделювання задач лінійного програмування та розв’язання їх графічним методом	Відвідування заняття Виконання роботи Захист звіту	1   3 1	5
3	Моделювання задач лінійного програмування та розв’язання їх симплексним методом	Відвідування заняття Виконання роботи Захист звіту	2   5 3	10
4	Моделювання задач лінійного програмування та розв’язання їх розподільчим методом	Відвідування заняття Виконання роботи Захист звіту	1   3 1	5
Усього				30

Список літератури

1. Конституція України [Електронний ресурс]. – Режим доступу: http: //zakon3.rada.gov.ua/laws/show/254к/96-вр.

2. ДБН 360-92**. Містобудування. Планування і забудова міських і сільських поселень [Електронний ресурс]. – Режим доступу: http: //dbn.at.ua/load/1-1-0-206.

3. Закон України «Про місцеві державні адміністрації» від 9 квітня 1999 року № 586-XIV, зі змінами станом на 30.10.2010 [Електронний ресурс]. – Режим доступу: http: //zakon.rada.gov.ua/cgi-bin/laws/main.cgi? nreg=586-14.

4. Земельний кодекс України від 25 жовтня 2001 року № 2768-III, зі змінами станом на 05.02.2011 [Електронний ресурс]. – Режим доступу: http: //zakon.rada.gov.ua/cgi-bin/laws/main.cgi? nreg=2768-14.

5. Методичні вказівки щодо практичних занять з навчальної дисципліни «Управління земельними ресурсами» для студентів денної форми навчання зі спеціальності 8.070904 – «Землевпорядкування та кадастр» / укладач
О. Г. Хохлов. – Кременчук, 2006. – 18 с.

6. Кирсанов В. А. Прогнозирование и планирование использования земельных ресурсов: конспект лекций. Ч. 1 / В. А. Кирсанов. – Харьков: ХАГУ, 1996. – 70 с.

7. Кирсанов В. А. Прогнозирование и планирование использования земельных ресурсов: конспект лекций. Ч. 2 / В. А. Кирсанов. – Харьков: ХАГУ, 1997. – 64 с.

8. Стативка И. М. Экономико-математические методы и моделирование в землеустройстве: учебное пособие / И. М. Стативка. – Харьков: ХСХИ, 1985. – 102 с.

9. Третяк А. М. Управління земельними ресурсами / А. М. Третяк,
О. С. Дорош. – Вінниця: Нова книга, 2006. – 360 с.

 

 

⇐ Предыдущая1234

Поделиться: