Лекция 4. Транспортная задача ЛП.Экономические задачи, сводящиеся к

преподаватель
кафедры ММиМЭ

начального опорного плана.
3. Метод потенциалов.
4. Оптимизационные задачи, сводящиеся к транспортным

моделям.

потребления.
ai – запасы в пунктах отправления, i=1,2,..m
bj – потребности в

грузах, j=1,2..n
Стоимость транспортировки единицы груза от i-го источника к j-му потребителю равна сij
xij - количество груза, транспортируемого от
от i-го поставщика к j-му потребителю. Определить xij , при которых общие транспортные расходы будут минимальными.

поставщиков (запасы грузов) и спросы потребителей (потребности) , а

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

были реализованы;
2. спросы всех потребителей были удовлетворены;
3. суммарные затраты на

перевозку были бы минимальны.
X11+X12+X13+X14=60
X21+X22+X23+X24= 120
X31+X32+X33+X34= 100 Мощности поставщиков реализованы

+3 X14+ X21 +6 X22 +5 X23 +2 X24 +6

X31 +3 X32 +7 X33+4X34min (суммарные затраты на перевозку)
Трансп. задача закрытого типа, т.к. ai= bj=280

= min (a1 , b1 ), x12 = min (a1

- x11 , b2 ), если x11 = b1 ,
Или x21 = min (b1 - x11 , a2 ), если x11 = a1 и т.д.
2. Метод минимального элемента
сlk = min (cij), где i=1,2,..m, j=1,2,..n
xlk = min (al , bk ),

i=1,2,..m
vj - потенциалы столбцов, j=1,2,..n
Для базисных переменных: vj-ui=cij
для небазисных переменных:

vj -ui ≤ cij

ввести фиктивного поставщика или потребителя.

7=7 – решение невырожденное f(x)=7*70+2*10+2*90+5*30+1*20+4*80+0*30=1180

решение невырожденное f(x)=2*80+1*40+2*20+2*60+1*50+4*50+0*30=610

с промежуточными пунктами.
3.Модель производства с запасами.
4.Оптимальное распределение оборудования.
5.Формирование оптимального штата

фирмы.

являются разнотипные грузы, которые развозятся по пунктам назначения в соответствии

с заявками.
К типов груза, для каждого типа груза заданы тарифы перевозок.
Если перевозки разнотипных грузов независимы, то многопродуктовая задача фактически расщепляется на К независимых транспортных моделей.
Чтобы свести многопродуктовую ТЗ к стандартной транспортной модели , будем рассматривать каждый пункт отправления Ai (i=1,2,..m), как К пунктов отправления Aih , (h=1,2,..К), и каждый пункт назначения Bj (j=1,2,..n) как К пунктов назначения Bjh .

и n*К – пунктов назначения. Если между пунктами Aih и

Bjh
груз не перевозится, то этим перевозкам присваивается очень большая стоимость M.
Пример. Даны m =4 пункта отправления Ai (i=1,..4),
в которых содержится до К=3 типов груза, отправляемых в n=2 пункта назначения Bj (j=1,2)
Запасы: а11=200, а13=150, а21=75, а22=100, а23=50, а31=50, а32=100, а41=40, а42=30, а43=50.
Заявки:b11=250, b12=130, b13=150, b21=115, b22=100, b23=100.

площадки, используемые для перегруппировки или хранения груза.
1) Промежуточные пункты

– только пункты отправления и назначения, т.е. груз можно перевозить через любой другой пункт отправления или назначения, пока груз не будет доставлен по назначению.
2) Промежуточными пунктами являются только дополнительные пункты.
3) Промежуточными пунктами являются как дополнительные пункты, так и пункты отправления и назначения.

назначения

M периодов (месяцев, недель, дней или иных периодов) планируется выпускать

продукцию в объёмах, равных a1, a2,… aM соответственно. Величина спроса для каждого периода составляет b1,b2,.. bM . Объёмы производства ai и спроса bi могут не совпадать между собой.
Спрос на продукцию пр-ва в текущем периоде i может быть удовлетворен:
При реализации продукции, произведённой в текущем периоде i;
При производстве продукции в предыдущие периоды j, jПри производстве продукции в более поздние периоды j, j>i, и реализации её в счёт погашения неудовлетворенного спроса в
период i.

в течение периода i;
Si - затраты на хранение единицы

готовой продукции в течение периода i;
Задержка в поставке единицы продукции в период i приводит к издержкам, равным ri .
Необходимо составить такой план поставок продукции потребителю, чтобы суммарные затраты f, связанные с производством, хранением и издержками, были минимальны. Обозначим:
Xij – кол-во продукции, изготовляемой в период i и поставляемой в период j.

изготовлена и реализуется в период i;
Cij=pi +

,если iCij=pi+ ,если i>j, т.е. если продукция изготовлена и реализуется в период i в счёт долга, образованного недопоставкой в период j.

n рабочими участками. Производительность единицы оборудования i-го вида на j-м

рабочем участке равна pij , i=1,..m;
J=1,..n. Запас оборудования i-го вида равен aI ,
Потребность j-го участка в оборудовании составляет bj . Найти распределение оборудования по рабочим участкам, при котором суммарная производительность максимальна.
Xij – число единиц оборудования i-го вида , выделенное на j-й рабочий участок.

группами различных должностей по bj , j=1,..n, вакантных единиц в

каждой группе. По результатам тестирования кандидатов разделяют на m групп по
aI кандидатов в каждой группе, i=1,..m. Для каждого кандидата из i-ой группы требуются определённые затраты cIj на обучение для занятия j-й должности.
cIj=0, кандидат полностью соответствует должности,
cIj=∞, кандидат не может занять данную должность.
Требуется распределить кандидатов на должности, затратив минимальные средства на их обучение.