3.2 Модель оптимального использования мтп

В этой модели для выполнения необходимых объемов механизированных работ с минимальными прямыми (эксплуатационными) затратами надо использовать уже имеющийся машинно-транспортный парк.

Например, для выполнения работ по боронованию и культивации почвы из предыдущей модели, имеется следующий парк машин: ДТ-75М – 2шт., МТЗ-80 – 2шт., Т-40М – 2шт., БЗСС-1,0 – 45шт., КПС-4 – 4шт.

Определить оптимальный план использования МТП для выполнения всех объемов работ с минимальными прямыми затратами.

1)Для составления плана выполнения работ достаточно ввести переменные по количеству рабочих агрегатов:

Х₁ – количество агрегатов ДТ-75М+21БЗСС-1,0

Х₂ – количество агрегатов МТЗ-80+18БЗСС-1,0

Х₃ – количество агрегатов Т-40М+15БЗСС-1,0

Х₄ – количество агрегатов ДТ-75М+2КПС-4

Х₅ – количество агрегатов МТЗ-80+КПС-4

Х₆ – количество агрегатов Т-40М+КПС-4

2)Систему ограничений составляют уравнения, обеспечивающие выполнение заданных объемов работ :

200Х₁+142,8Х₂+114,8Х₃=360 (боронование),

88Х₄+54Х₅+50Х₆=158 (культивация).

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

Х₁+ Х₄ ≤ 2 (По количеству ДТ-75М)

Х₂ + Х₅ ≤ 2 (По количеству МТЗ-80)

Х₃ + Х₆ ≤ 2 (по количеству Т-40М)

21Х₁ + 18Х₂ + 15Х₃≤ 45 (по количеству борон БЗСС-1,0)

2Х₄ + Х₅ + Х₆ ≤4(по количеству культиваторов КПС-4)

3) Целевая функция в этой модели –функция только прямых затрат. Для нашей задачи Z=93,6 Х₁ +80 Х₂ +69,8 Х₃ +82,6 Х₄ +55 Х₅ +50,4 Х₆ .

Решение на ЭВМ симплексным методом дает следующие значения: Х₁ =1,8, Х₄ =0,2, Х₅=0,8, Х₆ =2, Z=326,95.

Задание к лабораторной работе №3 (часть 2).

Для выполнения тех же механизированных работ, что и в части 3.1 необходимо использовать МТП, количество машин в нем представлено в Таблице 3.

Таблица 3

Марка машины	Количество в МТП	Марка машины.	Количество в МТП
Т-150К	5	ПРТ-10	2
ДТ-75М	10	РПН-4	2
МТЗ-80	10	РОУ-5	3
ЛДГ-15	2	НЛН-6-35	3
ЛДГ-10	2	ПЛН-4-35	9
ПФП-1,2	3	БЗСС-1,0	80
ПЭ-0,8Б	5	ЗККШ-6	8
КПС-4	9	СЗУ-3,6	21

3.3 Модель оптимального доукомплектования мтп.

В данной задаче уже имеется определенный состав МТП для выполнения заданных объемов работ (смотри часть 3.2). Но этого состава недостаточно для выполнения всех работ в заданный агротехнический период. Задача состоит в том, чтобы доукомплектовать имеющийся МТП для выполнения работ с минимальными (как правило) приведенными затратами.

Например, для выполнения работ, указанных в модели 1 имеется следующий состав МТП: ДТ-75М – 2шт., МТЗ-80 – 2шт., Т-40М – 1шт., БЗСС-1,0 – 30шт., КПС-4 – 3шт. Сколько и каких машин надо докупить, чтобы выполнить все объемы работ с минимальными приведенными затратами?

Для решения задачи:

1)Вводим переменные: а) Х₁ – Х₆ по количеству работающих агрегатов как в задачах 3.1 и 3.2., б) по количеству докупаемых СХМ:

Х₇ – по количеству докупаемых тракторов ДТ-75М

Х₈ – по количеству докупаемых тракторов МТЗ-80

Х₉ – по количеству докупаемых тракторов Т-40М

Х₁₀ – по количеству докупаемых борон БЗСС-1,0

Х₁₁ – по количеству докупаемых культиваторов КПС-4

2)Ограничения по выполнению объемов работ вводятся с учетом имеющегося МТП:

200Х₁+142,8Х₂+114,8Х₃=360 (боронование),

88Х₄+54Х₅+50Х₆=158 (культивация),

2+ Х₇ ≥ Х₁ + Х₄ или Х₁ + Х₄ – Х₇ ≤ 2 (ДТ-75М)

2+ Х₈ ≥ Х₂ + Х₅ или Х₂ + Х₅ – Х₈ ≤ 2 (МТЗ-80)

1+ Х₉ ≥ Х₃ + Х₆ или Х₃ + Х₆ - Х₉ ≤ 1 (Т-40М)

30+ Х₁₀ ≥21 Х₁ +18 Х₂ +15 Х₃ или 21 Х₁ +18 Х₂ +15 Х₃ - Х₁₀ ≤30 (БЗСС-1,0)

3+ Х₁₁ ≥2 Х₄ + Х₅ + Х₆ или 2 Х₄ + Х₅ + Х₆ - Х₁₁ ≤3 (КПС-4)

Замечание. Во всех ограничениях их объем должен быть неотрицательным.

3) Целевая функция приведенных затрат вводится также, как в задаче 1.

Z=93,6 Х₁ +80 Х₂ +69,8 Х₃ +82,6 Х₄ +55 Х₅ +50,4 Х₆ +652,8 Х₇ +797,4 Х₈ +

+443,2 Х₉ +1,5 Х₁₀ +67 Х₁₁.

Решение на ЭВМ: Х₁ =1.8; Х₅ =2; Х₆ =1; Х₁₀ =7,8; Z=340,58

Таким образом, по оптимальному плану доукомплектования МТП надо докупить 8 борон БЗСС-1,0, при этом минимальные приведенные затраты составят 340,58 (у.е.).

Задание к лабораторной работе №3 (часть 3).

Для выполнения тех же механизированных работ, что и в части 3.1, 3.2 необходимо использовать МТП, количество машин в котором, представлено в Таблице 3. Определить, достаточно ли имеющихся в МТП сельско- хозяйственных машин для выполнения заданных полевых работ? Если недостаточно, то какой техникой необходимо доукомплектовать данный МТП?

Лабораторная работа № 4

Транспортная задача (ТЗ) с закрытой моделью

Простейшая формулировка ТЗ

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

1. груз от каждого поставщика должен быть вывезен;

2. спрос каждого потребителя полностью удовлетворен;

3. затраты на перевозку должны быть минимальными.

Необходимое и достаточное условие решения поставленной задачи состоит в том, чтобы суммарный запас груза был бы равен суммарному спросу на него, то есть . Если это условие выполнено, то соответствующая ТЗ носит название задачи с закрытой моделью.

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

Поставщик	Потребители				Запас груза
		……………
		……………
……………	……………	……………	……………	……………
		……………
Потребность в грузе		……………

В клетках этой же распределительной таблицы можно составить план перевозок груза из пунктав пункт. При этом расходы на перевозку груза составят:

(1)

Таким образом, математическая формулировка ТЗ следующая: Найти , если переменныеудовлетворяют условиям:

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

При составлении опорного плана решения задачи в распределительной таблице 1 будут заполнены не более клеток, остальные клетки будут свободными (пустыми), так как соответствующий им груз равен нулю.

Таким образом, план решения ТЗ может быть определен следующими этапами:

1. Построение опорного плана решения ТЗ (в распределительной таблице заполняются не более клеток).

2. Проверка опорного плана на оптимальность.

3. Улучшение опорного плана, если он не оптимальный.

4. Проверка улучшенного плана на оптимальность. Процесс заканчивается оптимальным планом.

Рассмотрим каждый этап решения ТЗ.

1. Построение опорного плана решения ТЗ.

Рассмотрим два метода построения опорного плана.

а) Метод «Северо-западного угла»

Суть этого метода состоит в том, что заполнение распределительной таблицы ТЗ начинается с левого верхнего угла (клетка 1;1). В ней записывается максимально возможный груз: . Например, если, тои весь груз из пунктавывезен в пункт, но внадо завозить ещеединицу груза. Этот недостающий груз завозим из пункта, записывая в клетку (2;1) максимально возможный груз. Заполнив клетку (2;1), заполняем следующую, либо в той же строке 2 (если), либо в строке 3 (если). Последней заполняется клетка. При этом число заполненных клеток будет не более.Пример построения опорного плана методом «Северо-западного угла» приведен для следующей задачи .

Задача №1.

Фирма, выпускающая газированные напитки, складируемые в трех разных местах, должна поставить продукцию в четыре супермаркета. Каждая упаковка содержит 20 бутылок по 1,5 литра, тарифы на доставку товара, объемы запасов и заказы на продукцию приведены в Таблице 2.

Таблица 2

Поставщики	Потребители					Запасы груза
	6 75	7 25	3	5	100
	1	2 55	5 60	6 35	150
	2	10	20	2 50	50
Потребность в грузе	75	80	60	85	300

Затраты на перевозку 300 ед. груза по этому плану составляют:

(у.е.)

б) Метод «Минимального элемента»

Опорный план, построенный по методу «Северо-западного угла» обычно оказывается далеким от оптимального, так как при его составлении игнорируются величины затрат . Поэтому существуют другие методы составления начального опорного плана. Простейший из них - метод «Минимального элемента». В отличие от метода «Северо-западного угла», здесь заполнение распределительной таблицы начинается из клетки, у которой наименьший тариф. В эту клетку заносится максимально возможный груз. При этом либо строка, либо столбец окажутся заполненными. Далее заполняется следующая клетка (строки или столбцы), имеющая наименьший тариф.

Пример построения опорного плана методом «Минимального элемента» приведен в Таблице 3.

Таблица 3

Поставщики	Потребители					Запасы груза
	6	7 5	3 60	5 35	100
	1 75	2 75	5	6	150
	2	10	20	2 50	50
Потребность в грузе	75	80	60	85	300

Здесь порядок заполнения клеток следующий:

.

Затраты по этому маршруту перевозок составят: (у.е.). Мы видим, что по этому плану затраты на перевозку груза значительно меньше. И в таблице 2 и в таблице 3 заполненных клеток оказалось 3+4-1=6.

2. Проверка опорного плана на оптимальность.

Будем проверять опорный план на оптимальность методом потенциалов. Суть его состоит в том, что каждой строке и столбцу распределительной таблицы приписываются некоторые числа называемые потенциалами. Таким образом, числа- потенциалы строк,- потенциалы столбцов. Эти числа рассчитываются по формуле: длякаждой заполненной клетки распределительной таблицы сумма потенциалов строки и столбца равна тарифу соответствующей заполненной клетки, то есть

. (3)

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

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

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

3. Алгоритм улучшения неоптимального плана.

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

1) Маршрут начинается и заканчивается в клетке с отрицательной характеристикой;

2) Линии контура строго вертикальны или горизонтальны (нельзя двигаться по диагонали);

3) Повороты (на 90⁰) можно осуществлять только в заполненных клетках.

После построения замкнутого маршрута (самый простой вариант – прямоугольник), происходит перераспределение груза (улучшение опорного плана) по следующей схеме:

4) Каждой угловой клетке маршрута (где осуществлялись повороты на 90⁰) присваивается знак «+» или «-», причем клетке, из которой начинается маршрут, приписывают знак «+», далее знаки чередуются;

5) Среди клеток со знаком «-» выбирают клетку с наименьшим грузом;

6) Наименьший груз прибавляют ко всем клеткам со знаком «+» и вычитают из всех клеток со знаком «-». При этом пустая клетка, из которой начиналось движение и которая имела отрицательную характеристику, становится заполненной, а заполненная клетка, имевшая груз, который подлежал перераспределению, стала пустой.

Далее, улучшенный план вновь проверяют на оптимальность и улучшают до тех пор, пока характеристики всех пустых клеток не окажутся положительными. Это означает, что пустыми оказались клетки с большими тарифами, а заполнены клетки с малыми тарифами и поэтому затраты на перевозку груза оказались минимальными.

Проверим, например, оптимальность плана, построенного методом «Минимального элемента» в Таблице 3 (он лучше плана построенного методом «Северо-западного угла» в Таблице 2). Для этого рассчитаем потенциалы строк и столбцовпо заполненным клеткам Таблицы 3.

Результаты расчетов запишем в таблицу 4.

Таблица 4

Поставщики	Потребители				Потенциалы строк
	6	«-» 7 5	3 60	«+» 5 35	0
	«-» 1 75	2 75 «+»	5	6	- 5
	2 «+»	10	20	2 50 «-»	- 3
Потенциалы столбцов	6	7	3	5

Теперь по таблице 4 рассчитаем характеристики свободных клеток. Имеем, ;;;;;(-3+3)=20.Таким образом, среди свободных клеток одна клетка (3;1) имеет отрицательную характеристику.

По описанной выше схеме строим маршрут перераспределения груза. Движение начинаем из клетки (3;1) и ей присваиваем знак «+». Далее знаки чередуются. Среди клеток со знаком «-» наименьший груз (равный 5 ед.) в клетке (1;2). Этот груз мы вычитаем из клеток (1;2), (2;1), (3;4) и прибавляем в клетки со знаком «+» (3;1), (1;4), (2;2).

Таблица 5

Поставщики	Потребители				Запасы груза
	6	7	3 60	5 40	100
	1 70	2 80	5	6	150
	2 5	10	20	2 45	50
Потребность в грузе	75	80	60	85	300

Получаем новый опорный план (таблица 5).

Затраты по новому плану составят (у.е.). Проверка этого плана показывает, что он оптимальный.

Замечание. Если в опорном плане оказалось несколько клеток с отрицательной характеристикой, то маршрут перераспределения начинается из клетки с самой большой по абсолютной величине отрицательной характеристикой.

Задание для лабораторной работы № 4

Из четырех совхозов на заготовительные пункты необходимо вывести (ц) свеклы. Причем из первого совхоза ( ) (ц), из второго – () (ц), из третьего – () (ц), из четвертого – () (ц). Свеклу могут принять три заготовительные пункта :первый -() (ц), второй – () (ц), третий –( )(ц), здесь- номер варианта. Стоимость перевозки 1 ц свеклы (у.е.) задаются матрицей:

Вариант 1	Вариант 2	Вариант 3
Вариант 4	Вариант 5	Вариант 6
Вариант7	Вариант 8	Вариант 9
Вариант10	Вариант11	Вариант12

1) Построить распределительную таблицу ТЗ.

2) Построить опорный план решения ТЗ.

а) методом «Северо-западного угла»;

б) методом «Наименьшего элемента»

3) Проверить один из планов на оптимальность и найти неоптимальный план.

4) Построить маршрут перераспределения и улучшить опорный план.

5) Найти оптимальный план.

Лабораторная работа N 5

Транспортная задача (ТЗ) с открытой моделью.

Если общие запасы груза _I не равны суммарному спросу на него _j , то модель такой ТЗ называется открытой. Для решения задачи открытую модель сводят к закрытой с помощью введения фиктивного поставщика или фиктивного потребителя. Если _I ≤ _j , то вводят фиктивного поставщика А_m+1 с запасом груза a_m+1= _j - _I , а тарифы (затраты на перевозку этого груза к потребителям) равны нулю (с _m+1,j =0), так как на самом деле этого груза нет и соответствующие потребители его недополучат. Если _I ≥ _j , то вводят фиктивного потребителя В _n+1 со спросом на груз b_n+1= _I - _j и тарифами на получение с _{I, n+1} =0. Таким образом, открытую транспортную задачу можно решать как ТЗ с закрытой моделью.

Модель ТЗ (закрытая или открытая) может применяться не только для транспортировки грузов, но и в других задачах распределения ресурсов: распределение удобрений по участкам с различным плодородием для получения наибольшего урожая, распределения сельскохозяйственных культур по пашням для получения максимального дохода от реализации, распределение марок тракторов и подвесных орудий по видам механизированных работ для выполнения этих работ с минимальными затратами и т.д. При этом сама формулировка ТЗ может быть усложнена особыми требованиями: минимизация суммарных затрат на производство продукции и ее транспортировку ( в этом случае тариф – сумма затрат на производство и транспортировку), запрет отдельных поставок ( в этом случае соответствующая клетка распределительной таблицы блокируется завышенным тарифом) и др.

Задание к лабораторной работе №5.

Распределение тракторов по видам механизированных работ.

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

1.Т-25А -18шт. 2.ДТ-75М -28шт. 3.Т150К- 16шт. 4.МТЗ80 – 30шт. 5.ДТ-75 20шт. 6.МТЗ82 -20шт.

Одновременно выполняются следующие виды работ:

1.Вспашка зяби -3000га условной пахоты.

2.Лущение стерни 2000га условной пахоты.

3.Сволакивание соломы – 3100га условной пахоты.

4.Дискование – 2000га условной пахоты.

5.Противоэрозионные работы 1400га условной пахоты.

Агротехнический срок выполнения всех работ – 15 дней. Определите оптимальное распределение работ по маркам тракторов, если средняя выработка за смену ( две смены в день) и затраты на выполнение условного га работ приведены в Таблице 6. Прочерки в клетках Таблицы 6 означают, что соответствующие марки тракторов данный вид работ не выполняют, поэтому соответствующие клетки распределительной таблицы блокируются искусственно завышенным тарифом.

Таблица №6

№ п/п	Вид работ	Затраты (у.е.) на выполнение условного га работ
		Т-25А	Т-150К	ДТ-75	ДТ-75М	МТЗ-80	МТЗ-82
1.	Вспашка зяби	4,2	-	4,1	4,0	5,0	-
2.	Лущение стерни	3,8	3,2	3,4	3,4	-	5,0
3.	Сволакивание соломы	-	3,9	4,1	-	4,2	4,4
4.	Дискование	4,0	4,0	-	4,2	4,3	4,8
5.	Противоэро- зийные работы	-	3,8	3,6	3,6	3,9	4,0
	Сред.выработка в га условной пахоты за смену	2	11	6	7	5	6

При вычислении объема работ, которые могут выполнить все трактора данной марки следует сменную выработку одного трактора умножить на их количество и на число смен в агротехническом периоде. Например, для ДТ-75 объем выполняемых работ составит 6*20*30=3600 га условной пахоты; для ДТ-75М – 7*28*30=5880га и т.д. При составлении распределительной таблицы в строках указывается вид работ и его объем, а в столбцах - марка трактора и объем работ, который могут выполнить все трактора данной марки за весь агротехнический период.

План выполнения работы.

1. Составить распределительную таблицу, руководствуясь предложенными вариантами заданий.

2. Проверить, будут ли совпадать имеющиеся ресурсы выработки МТП с требуемым объемом механизированных работ. Если совпадения не будет, то ввести либо фиктивные работы, либо фиктивную марку тракторов.

3. . Решить полученную закрытую ТЗ.

4. Дать анализ полученного решения.

Варианты заданий к лабораторной работе.

Вариант 1. Вариант 2.

Вариант 3.Вариант 4.

Вариант 5. Вариант 6.

Вариант 7. Вариант 8.

Вариант 9.Вариант 10.

Вариант 11.Вариант 12.

Основной список вопросов, выносимых на зачет и входящий в содержание лабораторных работ.

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

2.Математическая формулировка линейной задачи оптимизации для двух переменных.

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

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

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

6.Метод Гомори, как один из распространенных методов отсечения, для нахождения целочисленного решения оптимальных задач: анализ полученного симплексным методом дробного решения с выделением основной переменной Гомори, составление дополнительного ограничения, итерация в симплексной таблице для получения целочисленного решения, наиболее близкого к оптимальному.

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

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

9.Открытая транспортная задача: введение искусственных поставщиков и потребителей для нахождения оптимального решения методом потенциалов.

.

Список рекомендуемой литературы

1) А.В. Кузнецов и др. Сборник задач по математическому программированию. Минск, 1985 г.

2) Г.И. Новиков и др. Сборник задач по вычислительной технике и программированию. М,, 1991 г.

3) В.Т. Сергованцев, В.В. Бледных. Вычислительная техника в инженерных и экономических расчетах. М., 1998 г.

4) Г.П.Фомин. Математические методы и модели. М., 2001г.

5)В.В.Федосеев Экономико – математические методы и прикладные модели. М., 2005г.