Линейная производственная задача

Имеем:

Cij-тарифная стоимость перевозки 1 единицы груза;

Ĉij-фактическая стоимость перевозки 1 единицы груза;

ij-условие оптимальности;

рi-платежи за единицу груза в пункте отправления;

pj- платежи за единицу груза в пункте назначения

pi + qj = Cij

Для заполненных (базисных)клеток : Ĉij=Cij

Для пустых: Xij=0

Lопорная=24*1+6*2+14*1+31*3+40*1=183(общая сумма затрат)

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

Т.к. не все ij  0, то мы еще не нашли оптимальное решение.

Далее выбираем пустую клетку таблицы с максимальной переплатой ij0.

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

Итак, выполняется условие оптимальности: ij  0, и мы получили оптимальный план затрат.

Lоптим.= 24*1+6*2+20*1+25*3+40*1=171

L=183-171=12

МЕТОД ВЕТВЕЙ И ГРАНИЦ.

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

P(x) = x1 + 3x2max

   14x1 + 9x2  51

   -6x1 + 3x2   1

   x1  0, x2 0

решение:

x1 = 1.56, x2 = 3.45, P(x)max = 11.5

См. график на рисунке

         P(x) = x1 + 3x2max                                P(x) = x1 + 3x2max

    G1        =   14x1 + 9x2  51                            G2 =                14x1 + 9x2  51

                               -6x1 + 3x2   1                                                        -6x1 + 3x2   1        

                             x1  1                                                                                 x1  2

Решение: x1 = 1; x2 =7/3                               Решение: x1 = 2; x2 =23/9

P1(x)max = 8                                                   P2(x)max = 9,6

Т.к. P1(x)max >P2(x)max

То эта задача не подходит

         P(x) = x1 + 3x2max                                P(x) = x1 + 3x2max

    G3        =   14x1 + 9x2  51                            G4 =                14x1 + 9x2  51

                               -6x1 + 3x2   1                                                        -6x1 + 3x2   1        

                             x1  2; x2  2                                                      x1  2; x2  3

                                                               Решение не принадлежит ОДЗ

         P(x) = x1 + 3x2max                                P(x) = x1 + 3x2max

    G5        =   14x1 + 9x2  51                            G6 =                14x1 + 9x2  51

                               -6x1 + 3x2   1                                                        -6x1 + 3x2   1        

                             x1 =3;              x2 =1                                                                   x1 =2;              x2 =2

P5(x)max =6                                                   P6(x)max = 8

Ответ: P(x)max = 8; x1 =2;x2 =2

РЕШЕНИЕ  ЗАДАЧИ  РАСПРЕДЕЛЕНИЯ  КАПВЛОЖЕНИЙ  МЕТОДОМ  ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

Динамическое программирование - это вычислительный метод для решения задач управления определённой структуры. Данная задача с n переменными представляется как много шаговый процесс принятия решений. На каждом шаге определяется экстремум функции только от одной переменной.

Рассмотрим нелинейную задачу распределения ресурсов между предприятиями отрасли. Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через fj(xj) прирост мощности  или прибыли на  j-том предприятии, если оно получит  xj рублей капвложений. Требуется найти такое распределение (х1, х2, ..., хn) капвложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли

Z=f1(x1)+f2(x2)+...+fn(xn)

при ограничении по общей сумме капвложений

х1 + х2 +...+хn = b

причём будем считать, что все переменные xj принимают только целые значения xj =1,2,...

Функции fj(xj) мы считаем заданными, заметив, что их определение -довольно трудоёмкая экономическая задача.

Воспользуемся методом динамического программирования для решения этой задачи.

Введём параметр состояния и определим функцию состояния. За параметр состояния   примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk() определим как максимальную прибыль на первых  k  предприятиях, если они вместе получат  рублей. Параметр  может меняться от 0 до b. Если из  рублей k-ое предприятие  получит Хк  рублей, то каково бы ни было это значение, остальные -Хк  рублей естественно распределить между предприятиями от 10-го до (к-1)-го предприятия, чтобы была получен максимальная прибыль Fk-1(-xk). Тогда прибыль k предприятий будет равна fk(xk) + Fk-1(-xk). Надо выбрать такое значение xk между 0 и , чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению:

Fk() = max {fk(xk) + Fk-1(-xk)}

         0  X  

для k=2,3,....,n .Если же k=1 ,то

F1()=f1().

Рассмотрим конкретный пример. Пусть производственное объединение состоит из 4-х предприятий (k=4).Общая сумма капвложений равна 700 тыс. рублей (b=700) , выделяемые предприятиям суммы кратны 100 тыс. рублей.

Значения функций fj(xj) приведены в табл. 1.

Прежде всего заполняем табл.3. Значения f2(x2) складываем со значениями F1(-x2)=f1(-x2) и на каждой побочной диагонали находим наибольшее число, которое помечаем звёздочкой. Заполняем табл .3.

Продолжая процесс табулируем функции F3(), x3() и т.д. В табл.6 заполняем только одну диагональ для значения =700.

Таблица 1.