Реферат: Прикладная математика

§6. Задача о "расшивке узких мест производства"

При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, т.е. образуют ²узкие места производства². Будем их заказывать дополнительно. Пусть T(t1,t2,t3)- вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие

H + Q-1T  0.

Задача состоит в том, чтобы найти вектор

T (t1, 0, t3),

максимизирующий суммарный прирост прибыли

                                                         W = 6t1 + 4t3                                                                                 (1)

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

(2)

                                             

предполагая,     что      можно       надеяться       получить      дополнительно не более 1/3 первоначального объема ресурса каждого вида                                                

                    (3)

причем по смыслу задачи

                           t1  0,   t3   0.     (4)                                                                             

Переписав неравенства (2) и (3) в виде:

(6)

(5)

         

приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).

Эту задачу легко решить графически: см. рис. 1. Программа ²расшивки² имеет вид

t1=, t2=0, t3=

18

и прирост прибыли составит 519.

Сводка результатов приведена в таблице

 Таблица 1

§7. Транспортная задача линейного программирования

Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в m пунктах производства (хранения) в количествах   а1, а2,..., аm единиц, необходимо распределить между n пунктами потребления, которым необходимо соответственно   b1, b2,..., bn единиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна сij  и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы  по доставке продуктов были минимальными.

Обозначим через хij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю. При наличии баланса производства и потребления

                                                                          (1)

математическая модель транспортной задачи будет выглядеть так:

найти план перевозок       

                                        Х = (хij),      i = 1,m;        j =  1,n       

минимизирующий общую стоимость всех перевозок

                                                                                                      (2)

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

                                                               (3)

и любому потребителю доставляется необходимое количество груза

                                                                (4)         

причем по смыслу задачи

х11 > 0 ,. . . .,  xmn > 0.                                                             (5)

19

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

А(а1, а2, а3) = (54; 60; 63);    В(b1, b2, b3, b4) = (41; 50; 44; 30);    С =      

Общий объем производства åаi = 55+60+63 = 178 больше, требуется всем потребителям åbi = 42+50+44+30 = 166, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 178-166 = 12 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

Первое базисное допустимое решение легко построить по правилу ²северо-западного угла².

Следует иметь в виду, что по любой транспортной таблице можно восстановить соответствующий предпочитаемый эквивалент системы уравнений (3), (4), а в таблице записаны лишь правые части уравнений, причем номер клетки показывает, какая неизвестная в соответствующем уравнении является базисной. Так как в системе (3), (4) ровно m + n - 1 линейно независимых уравнений, то в любой транспортной таблице должно быть m + n - 1 занятых клеток.

Обозначим через

m)

вектор симплексных множителей или потенциалов. Тогда

                               Dij = mAij - сij                i = 1,m;             j = 1,n

откуда следует

Dij = pi + qj - cij           i = 1,m;        j = 1,n                                     (6)

Один из потенциалов можно выбрать произвольно, так как в системе (3), (4) одно уравнение линейно зависит от остальных. Положим, что р1 = 0. Остальные потенциалы находим из условия, что для базисных клеток . В данном случае получаем

                   D11 = 0,            p1 + q1 - c11 = 0,           0+q1 -1 = 0,     q1 = 1

                   D12 = 0,            p1 + q2 - c12 = 0,           0+q2 -4 = 0,     q2 = 4

D22 = 0,            p2 + q2 - c22 = 0,           р2 +4-6 = 0,     р2 = 2

и т.д., получим: q3=0, p3=6, q4= 1, q5= -6.

Затем по формуле (6) вычисляем оценки всех свободных клеток:

                   D21 =    p2 + q5 - c21 = 2+1-3 = 0

                   D31 =    p3 + q1 - c31 = 6+1-2 = 5

                   D32 = 5;  D13 = -3;  D14 = -1;  D24 = -2;  D15 = -6;  D25 = -4.

20

Находим наибольшую положительную оценку

max () = 5 =

Для найденной свободной клетки 31 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 31-11-12-22-23-33. Производим перераспределение поставок вдоль цикла пересчета

= 21

Получаем второе базисное допустимое решение:

Находим новые потенциалы, новые оценки. Наибольшую положительную оценку будет иметь свободная клетка 14. Для нее строим цикл пересчета 14-11-31-34 производим перераспределение

rmax = 20

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

                   Dij £ 0                   i = 1,m;           j = 1,n

Читателю не составит труда проверить, что будет оптимальным базисное допустимое решение

§8. Динамическое программирование.

21

Распределение капитальных вложений

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

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

Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через fi(xi) прирост мощности или прибыли на j-м предприятии, если оно получит xi рублей капитальных вложений. Требуется найти такое распределение (x1,x2, ... , xn) капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли

            z = f1(x1) + f2(х2) + ... + fn(xn)

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

                                    x1 + x2 + ... + xn = b

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

xj = 0, или 1, или 2, или 3, ...

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

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

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

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

0 £ xk £ x

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

F1(x) = f1(x)

Рассмотрим конкретный пример. Пусть производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций fj(xj) приведены в таблице 1, где, например, число 88 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 88 тыс. руб.

22

Таблица I

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

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

Zmax = 155 тыс. руб.,

причем четвертому предприятию должно быть выделено

 х*4  = 4 (700) = 300 тыс. руб.

На долю остальных трех предприятий остается 400 тыс. руб. Из табл. 5 видно, что третьему предприятию должно быть выделено

x*3 = 3 (700-x*4) = 3 (400) = 200 тыс. руб.

Страницы: 1, 2, 3, 4, 5, 6, 7