Распределительные задачи

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

Усл. обозначения:

m-кол-во типов станков

n- кол-во видов изд-й

i- порядковый № типа- станков

j- порядковый № вида изделий

Ai- фонд раб.t станков i вида

Bf- план по пр-ву изд j вида

Pij- кол-во изд j вида,производимых на станках I типа в ед t.

Сij- ден.затр-ты при пр-ве изд-й j вида на станках I типа в ед-цу t.

Математич.модель:

F(t)= С₁₁t₁₁ + C₁₂ t₁₂ + … +C _mn t _mn ----min

Ден.затр-ты при изготоалении изд-й 1 вида на станках 1типа

Общ сумма д.б.min.

t₁₁ + t₁₂ + … + t _1n <=A₁ ограничение по использ-ю

t₂₁ + t₂₂ + … + t _2n <=A₂ фонда раб.естанков

t_m1 + t_m2 + … + t _mn <=A_m каждого типа.

P₁₁ t₁₁ + P₂₁t₂₁ +… + P _m1 t_m1 =B₁ огр-е по выпуску

P₁₂t₁₂ + P₂₂t₂₂ +… + P _m2 t_m2 =B₂изд-й кажд. вида

P_1nt_1n + P_2nt_2n +… + P _mn t_mn =B_n

t₁₁>=0 t₁₂>=0 t_1n>=0

Paccмотренная задача явл-ся задачей линейного программирования, поэтому для решения м.исп-ть симплексный метод.Также м.свести рассмотренную модель к модели трансп.задачи и решить ее при помощи метода потенциалов.

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

Постановка задачи: Пусть имеется m Пунктов произ-ва некот-го однородного продукта, его необх-мо перевести в n пунктов потребления.

Известно:

-запас продукта в каждом пункте отправления

-спрос в каждом пункте потребления

-зат-ты на перевозку ед-цы груза от каждого пункта отправления в каждый пункт потребления.

Требуется составить план перевозок.

Критерий оптимальности: MIN-е общие транспортные затраты

Условные обозначения:

m- количество пунктов отправления

n- количество пунктов потребления

i- порядковый номер пункта отправления

j- порядковый номер пункта потребления

a_i- кол-во единиц груза в итом пункте отправления

b_j- потребность в грузе в житом пункте потребления

Сij-затраты на перевозку ед-цы груза от итого пункта отправления в житый пункт потребления

Хij- объем перевозки груза от итого пункта отправления к житому пункту потребления

Математическая модель:

F(х)=С11Х11+С12Х12+…+СmnХmn-min (1)

Условия по вывозу продукта:

Х11+Х12+…+Х1n меньше или равно a1

Х21+Х22+..+Х2n меньше или равно a2

………………….

Хm1+Хm2+…Хmn меньше или равно am (2)

Условия по ввозу прдукта:

Х11+Х12+..+Хm1=b1

Х12+Х22+..+Хm2=b2

…………………….

Х1n+Х2n+…+Хmn=bn

Хmn больше или равно 0 (3)

Если общая потребность в грузе в пунктах потребления равна общему запасу груза в пунктах отправления, то модель трансп.задачи называется ЗАКРЫТОЙ: сумма ai= сумме bj. Если условие не совпадает, то модель ОТКРЫТАЯ. Для разрешимости трансп.задачи необходимо и достаточно, чтобы общий запас груза у отправителей был равен общей потребности в грузе в пунктах потребления, т.е. модель закрытая.

В случае превышения общего предложения: сумма ai больше суммы bj, вводится фиктивный (n+1)-й пункт потребления с потребностью: bn+1=сумма ai-сумма bj, при этом тарифы на перевозку единицы груза считаются равными нулю: Ci,n+1=0 (i=1,m).

Если же сумма ai меньше суммы bj, то вводится фиктивный (m+1)-й пункт отправления с запасом a_m+1= сумма bj-сумма ai, тарифы на перевозку единицы груза от этого пункта отправления =0: Cm+1,j=0 (j=1,n)

Для решения задачи 1,2,3 можно использовать симплекс-метод, но благодаря особенностям ограничений системы (2): (каждая переменная встречается только 2 раза, коэф-ты перед переменными равны0) для определения оптимального плана трансп.задачи разработаны спец. Методы, например, метод потенциалов.

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

17. Определение опорного плана транспортной задачи по методу северо- западного угла.

Заполнение клеток таблицы условий начинается с левой верхней клетки. Первый опорный план не вырожденный, т.к. количество занятых клеток =(m+n)-1

m- число отправителей

n-число потребителей

При построении 1-ого опорного плана по методу северо-западного угла не обращают внимание на тарифы на перевозку единицы груза, поэтому процесс оптимизации идет долго.