Методы оптимизации в экономике, страница 2

План будем называть оптимальным, если он среди всех допустимых планов приводит к минимальной суммарной стоимости перевозок. Мы видим, что перед нами задача линейного программирования с ограничениями типа равенств. Коэффициенты в ограничениях (2,1) — (2.2) равны единице, что позволяет решать задачу более простыми способами. Процесс отыскания оптимального плана итерационный. Его начинают с построения опорного плана, затем проверяют на оптимальность и, если полученный опорный план не оптимален, улучшают его. Существуют несколько простых схем построения первоначальногс опорного плана транспортной задачи.

Рассмо~р~м один из ннх: м~т~д северо-западного угла. Пусть условия транспортной задачи заданы в табл. 2.2. Не учитывая стоимости перевозки единицы груза, начинаем удов- летворение потребностей первого потребителя В~ за счет запаса по- ставщика А1. Для этого сравниваем а 10 с Ь1 15,а ~ < Ь1, меньший из объемов, т.е. 10 единиц, записываем в левый нижний угол клетки А1 В ~. Запасы первого поставщика полностью израсходова- ны, поэтому остальные клетки первой строки оставляе незаполнен- ными. Потребности потребителя В ~ остались неудовлетворенными на 15 — 10 = 5 ед. Сравниваем этот остаток с запасами поставщика А „: так как 5 < 20, то 5 единиц записываем в клетку А, В ~, чем полно- стью удовлетворяем потребности потребителя В ~, а оставшиеся клет- ки в первом столбце оставляем незаполненными. У поставщика А ~ осталось 15 единиц груза.

Удовлетворяем по- требителя В ~ за счет оставшегося у поставщика А, груза. Для этого сравниваем этот остаток с потребностями потребителя В з . 15 > 10, записываем 10 в клетку А ~ Вз, тем самым удовлетворяя потребности потребителя В ~. Оставшиеся клетки второго столбца оставляем неза- полненными. У поставщика А ~ осталось еще 20 — 5 — 10 = 5 ед.

груза. Сравним оставшиеся запасы поставщика А~ с потребностями потреби- теля Вз, т.к. 5 < 15, записываем 5 единиц в клетку Аз Вз и пытаем- ся удовлетворить потребителя В з за счет поставщика А з. Потреби- телю В з требуется 10 единиц, которые он может получить от постав- щика А з. Таким образом, все потребители удовлетворены за счет по- ставщиков. Первоначальный опорный план построен, 8 табл. 2.

3 в левых верхних углах стоят числа, определяющие сто- имость перевозки единицы груза, а в левых нижних углах — числа, определяющие план перевозок. Их сумма по строкам равна запасам соответствующего поставщика, а сумма по столбцам — потребностям соответствующего потребителя. Полученный план невырожденный, так как содержит точно т+л-1=3+3-1=5 занятых клеток. При составлении первоначального опорного плана методом севе- ро-западного угла стоимость перевозки единицы груза не учитывалась, поэтому построенный опорный план далек от оптимального. Общая У = 4х 10 + 2х 5 + 2х 10 + 1 х 5 + 5х 10 =. 12 ~ (ед. стоимости) Таблица 23 15 10 '16 и„ Если при сОставлении ОпОрноГО плана учитывать стоимость пере~оз~~ единицы ~руза то план буде~ зна~ительно ближе к Оп~~~ал~~ому. В этом случае можно воспользоваться для построения опорного плана методом минимальной стоимости 11,2,31.

Построенный Опорный план транспоотной задачи Мо~но довес~и до ОптимальноГО, например, с пОИОщью метода потенциалов. 2.3. Метод потенциалов 1. Построение системы потенциалов. Для построения системы потенциалов используем условие где С;; — стоимость перевозки единицы груза занятой клетки в 1-й строке и ~ -м столбце, а числа и; и ~ называют потенциалами, соответственно, поставщиков и потребителей.

Систему потенциалов можно построить только для невырожденного опорно~о ~ла~~, Содержащ~го ш+и-1 занятых клеенок. Поэзо~у для удобства следует вырожденный план свести к невырожденному путем введения в опорный план клеток с нулевым планом перевозки. Уравнений на одно меньше, чем неизвестных, поэтому система являет- ся неопределенной и одному неизвестному (обычно и 1) придают нулевое значение. После этого остальные потенциалы определяются однозначно. Запиш~м их в столбцы табл.2.3. 2. Проверка выполнения условия-оптимальности для незанятых клеток.

Просматриваем строки, для каждой незанятой клетки вычисляем разность С~ — (и; + м ) и записываем ее в верхний правый угол клетки. Если для всех незанятых клеток все разности положительны, то план является оптимальным, в противном случае— неоптимальным. Значения разностей для исходного примера записаны в табл.2.3. Отрицательные разности записаны в клетках А1 Вз', А| Вз, Аз В1, Аз Вз. Таким образом, имеются четыре клетки, в которых нарушено условие оптимальности. Разности соответственно равны: - 1, -1, -5, -2. 3.

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

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

Циклом называется набор занятых клеток, в котором две и только две соседние клетки расположены в одном столбце или одной строке таблицы„причем последняя клетка находится в той же строке или столбце, что и первая. Отыскиваем цикл и, начиная движение от клетки, отмеченной знаком «+», поочередно проставляем знаки «-» и «+».

Затем находим О о ш1пх,~, где х;. — перевозки, стоящие в вершинах цикла, отмеченных знаком «минус». Величина Оо определяет, сколько единиц груза можно перераспределить по найденному циклу. Клетку, содержащую Оо, из опорного плана исключим. Значение О о записываем в незанятую клетку, отмеченную знаком «+», двигаясь по циклу, вычтем О о из объемов перевозок, расположенных в клетках, которые отмечены знаком «-», и прибавим к объемам перевозок, находящихся в клетках, отмеченных знаком «+». Т а б л я ц а 2.4 В рассматриваемом прнмере клетку А з.в 1 отмечаем знаком 16 10 15 «+» и находим цикл, приведенный в табл.2.3. Имеем О ~ =5, т.е. пере- 3 О К 6 10 «вЂ” 0 возку в 5 единиц необходимо пере- 20 2 2 местнгь в клетку ~ъ ЗЮ| и прове0 10 10 -~ сти перемещение 5 единиц в клетки со знаком «+» и вычесть из клеток 10 1 -2 5 со знаком «-» (табл.2.3).

5 -3 5. В результате перераспределения Оо получен новый опорный невырожденный план (табл.2.4), который снова подлежит проверке на оптимальность. Для этого можно вновь построить систему потенциалов и проверить выполнение условия оптимальности для каждой незанятой клетки. Если полученный план вновь окажется неоптимальным, то следует выполнить вычисления, приведенные в п.4. Таблица 25 Таблица 26 15 10 15 и„. 10 10 Для рассматриваемого примера последовательность выполнения действий приведена в табл.2.4 — 2.6.

Причем для табл. 2,4 У = 100 ед, для табл. 2.5 У = 7О ед., для табл.2.6 У =65 ед. Опорный план, приведенный в табл.2.6, является оптимальным. 2.4, Варианты заданий 1. Для строительства четырех объектов используется кирпич, изготовляемый на трех заводах.

Ежедневно каждый из заводов может изго- товлять 100, 150 и 50 усл. единиц кирпича. Ежедневные потребности в кирпиче на каждом из стр~ящих~я объек~~х с~о~~~~с~в~нн~ ра~ны 75, 80, 60 и 85 усл.единиц. Известны также тарифы перевозок 1 уел. ед. ки-нича с каждого из заводов к каждому из строящихся объек- ТОВ: 5 6 2 1 б) 1 2 7 3 61152 6 7 3 5 1 2 5 6 8 10 20 1 Составить такой план перевозки кирпича к строящимся обьектам, при кОтором общая стоимость перевозок является минимальной.

2. На трех хлебокомбинатах ежедневно производится 110, 190 и 90 т муки. Эта мука потребляется четырьмя хлебозаводами, ежедневные потребности которых равны соответственно 80, 60, 170 и 80 т. 1"арифы перевозок 1 т муки с хлебокомбинатов к каждому из хлебозаводов задаются матрицей 8 1 9 7 4 6 212 3 5 8 9 б) 9 7 5 3 1 2 4 6 8 10 12 1 а) Составить такой план перевозок бензина, при котором общая стоимость перевозок является минимальной. 4.

На предприятии имеется четыре группы станков, каждый из которых может выполнять пять видов элементарных операций по обработке детали, причем операции могут производиться в любом порядке. Максимальное время работы каждой из групп станков соответственно равно 320, 400, 240 и 400 ч., каждая операция должна выполняться со- Составить такой план доставки муки, при котором общая стоимость перевозок является минимальной. 3.

В трех хранилищах горючего ежедневно хранится 175, 125 и 140 т бензина. Этот бензин ежедневно получают четыре заправочные станции в количествах, равных соответственно 180, 60, 140, 60 т. Стоимости перевозок 1 т бензина с хранилищ к заправочным станциям задаются магрицей лен е~ ли Й~~ОйюОфий ( 1~ьн~л ~ь ааа~.~о~ о а и~и ~ ~ ~ **,~а — « ° ~ ~ ~~ «ю~» ю ттмгплы ияРРгтий н "~ййа- 3 на матрицей 4 3 6 2 1 3 4 3 5 2 2 5 4 2 3 3 6 5 4 6 4 3 3 6 2 3 6 г 2 5 7 2 5 а) 7 11 5 4 6 8 5 4 3 6 13-7 8 4 Составить такой план прикрепления потребителей к поставщикам, при котором общие затраты являются минимальными.

6. Для строительства четырех дорог используется гравий из трех карьеров. Запасы гравия в каждом из карьеров соответственно равны 120, 250, 190 усл.ед. Потребности в гравии для строительства каждой из дорог соответственно равны 150, 230, 30 и 40 усл. единиц. Известны также тарифы перевозок 1 усл. ед. гравия из каждого карьера к каждой из строящихся дорог, которые задаются матрицей 2 7 12 8 5 2 6 7 1 7 3 2 1 8 10 4 4 1 5 9 3 9 2 1 а) Составить такой план перевозок гравия, при котором потребности в нем каждой из строящихся дорог были бы удовлетворены при наименьшей общей стоимости перевозок. 7. Имеется три участка земли, на которых могут быть засеяны кукуруза, ячмень, пшеница и просо.