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

продукции, используя для этого три вида ресурсов. Известна технологическая

матрица А затрат любого ресурса на единицу каждой продукции, вектор В

объемов ресурсов и вектор С удельной прибыли

[pic] (7)

Требуется составить производственную программу, обеспечивающую

предприятию наибольшую прибыль при имеющихся ограниченных ресурсах

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

найти производственную программу

(x1, x2, x3, x4)

максимизирующую прибыль

z = 36x1+ 14x2 + 25x3 + 50x4

(8)

при ограничениях по ресурсам

[pic] (9)

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

x1 ( 0, x2 ( 0, x3 ( 0, x4 ( 0.

(10)

Получили задачу на условный экстремум. Для ее решения систему неравенств

(9) при помощи дополнительных неотрицательных неизвестных х5, х6, х7

заменим системой линейных алгебраических уравнений

[pic] (11)

где дополнительные переменные имеют смысл остатков соответствующих

ресурсов. Среди всех решений системы уравнений (11), удовлетворяющих

условию неотрицательности

х1(0, х2(0, … , х5(0, … , х7(0. (12)

надо найти то решение, при котором функция (8) примет наибольшее значение.

Воспользуемся тем, что правые части всех уравнений системы (11)

неотрицательны, а сама система имеет предпочитаемый вид – дополнительные

переменные являются базисными. Приравняв к нулю свободные переменные х1,

х2, х3, х4, получаем базисное неотрицательное решение

x1=0, x2=0, x3=0, x4=0, x5=208, x6=107, x7=181

(13)

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

x1=0, x2=0, x3=0, x4=0

(14)

по которой мы пока ничего не производим.

Из выражения (8) видно, что наиболее выгодно начинать производить

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

наибольшая. Чем больше выпуск в этой продукции, тем больше прибыль.

Выясним, до каких пор наши ресурсы позволяют увеличить выпуск этой

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

решение

[pic] (15)

Мы пока сохраняем в общем решении х1=х2=х3=0 и увеличиваем только х4. При

этом значения базисных переменных должны оставаться неотрицательными, что

приводит к системе неравенств

[pic] или [pic] т.е. 0 ( х4 ( [pic]

Дадим х4 наибольшее значение х4 =181/5, которое она может принять при

нулевых значениях других свободных неизвестных, и подставим его в (15).

Получаем для системы уравнений (11) частное неотрицательное решение

х1=0, х2=0, х3=0, х4=[pic]; x5=27; x6=[pic]; x7=0

(16)

Нетрудно убедиться, что это решение является новым базисным

неотрицательным решением системы линейных алгебраических уравнений (11),

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

х4 за разрешающую и перейти к новому предпочитаемому виду этой системы,

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

уравнение мы обязаны принять третье, так как

[pic]

а разрешающим элементом будет а34=5. Применив известные формулы исключения,

получаем для системы уравнений (11) новый предпочитаемый эквивалент

x1 + 2x2 + 2x3 + x5

- x7 = 27

[pic]x1 + [pic]x2 - [pic]x3 + x6 -

[pic]x7 = [pic] (17)

[pic]x1 + [pic] x2 + [pic]x3 + x4

+ [pic]x7 = [pic]

Приравняв к нулю свободные переменные х1, х2, х3, х7, получаем базисное

неотрицательное решение, совпадающее с (16), причем первые четыре

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

х1=0, х2=0, х3=0, х4=[pic].

(18)

Исследуем, является ли эта программа наилучшей, т.е. обеспечивает ли она

наибольшую прибыль. Для этого выразим функцию прибыли (8) через новые

свободные переменные х1, х2, х3, х7.

Из последнего уравнения системы (17) выражаем базисную переменную х4

через свободные и подставляем в (8). Получаем

[pic]

[pic] (19)

Видим, что программа (18) не является наилучшей, так как прибыль будет

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

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

принимаем х1 в системе (17) за разрешающую неизвестную, находим разрешающее

уравнение по

[pic] (20)

и исключаем х1 из всех уравнений системы (17), кроме первого уравнения.

Получим следующий предпочитаемый эквивалент системы условий, который

определит для системы (11) новое базисное неотрицательное решение и уже

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

выразить функцию (19) через новые свободные переменные, удалив оттуда

переменную х1, ставшую базисной. Мы видели выше, как это делается (удаляли

х4 из (8)).

Важно обратить внимание на то, что эти удаления можно выполнить очень

просто. Представим соотношение (8) в виде уравнения

-36х1 - 14х2 - 25х3 - 50х4 = 0 – z

(21)

и припишем его к системе (11). Получается вспомогательная система уравнений

[pic] (22)

Напомним, что разрешающую неизвестную в системе (11) мы выбрали х4. Этой

переменной в последнем уравнении системы (22) отвечает наименьший

отрицательный коэффициент (4=-50. Затем мы нашли разрешающий элемент а34=5

и исключили неизвестную х4 из всех уравнений системы (11), кроме третьего.

Далее нам пришлось х4 исключать и из функции (8). Теперь это можно сделать

очень просто, если посмотреть на систему уравнений (22). Очевидно,

достаточно умножить третье уравнение системы (22) на 10 и прибавить к

четвертому; получим

-6х1 - 4х2 - 5х3 - 10х4 = 1810 – z

(23)

Таким образом, мы преобразовывали вспомогательную систему уравнений (22)

к виду

x1 + 2x2 + 2x3 + x5 - x7

= 27

[pic]x1 + [pic]x2 - [pic]x3 + x6 - [pic]x7

= [pic] (24)

[pic]x1 + [pic] x2 + [pic]x3 + x4 +

[pic]x7 = [pic]

-6x1 - 4x2 - 5x3 +10x7 =

1810 - z

Первые три уравнения этой системы представляют некоторый предпочитаемый

эквивалент (17) системы уравнений (11) и определяют базисное

неотрицательное решение (16) и производственную программу (18), а из

последнего уравнения системы (24) получается выражение (19) функции цели

через свободные переменные. Очевидно, если имеется хотя бы один

отрицательный коэффициент (j при какой-нибудь переменной xj в последнем

уравнении системы (24), то производственная программа не является наилучшей

и можно далее продолжать процесс ее улучшения. С помощью (19) мы выяснили,

что следует начинать производить продукцию первого вида, т.е. фактически мы

нашли в последнем уравнении системы (24) наименьший отрицательный

коэффициент

min((j0, x4>0. Поэтому

4y1 + 2y2 + 3y3 - 36 = 0

5y1 + 2y2 + 5y3 - 50 = 0

Если же учесть, что второй ресурс был избыточным и, согласно той же теореме

двойственности, ее двойственная оценка равна нулю

у2=0,

то приходим к системе уравнений

4y1 + 3y3 - 36 = 0

5y1 + 5y3 - 50 = 0

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

у1=6, у3=4.

Таким образом, получили двойственные оценки ресурсов

у1=6; у2=0; у3=4,

(4)

причем общая оценка всех ресурсов равна 1972.

Заметим, что решение (4) содержалось в последней строке последней

симплексной таблицы исходной задачи. Важен экономический смысл двойственных

оценок. Например, двойственная оценка третьего ресурса у3=4 показывает, что

добавление одной единицы третьего ресурса обеспечит прирост прибыли в 4

единицы.

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

При выполнении оптимальной производственной программы первый и третий

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

Будем их заказывать дополнительно. Пусть T(t1,t2,t3)- вектор дополнительных

объемов ресурсов. Так как мы будем использовать найденные двойственные

оценки ресурсов, то должно выполняться условие

H + Q-1T [pic] 0.

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

T (t1, 0, t3),

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

W = 6t1 + 4t3

(1)

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

структуры производственной программы)

[pic]

предполагая, что можно надеяться получить

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

[pic] [pic] [pic] (3)

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

t1 [pic] 0, t3

[pic] 0. (4)

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

[pic]

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

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

имеет вид

t1=[pic], t2=0, t3=[pic]

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

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

Таблица 1

|сj |36 |14 |25 |50 |b |x4+i |yi |ti |

| |4 |3 |4 |5 |208 |0 |6 |46 5/12|

|aij|2 |5 |0 |2 |107 |13 |0 |0 |

| |3 |1 |2 |5 |181 |0 |4 |60 1/3 |

|xj |27 |0 |0 |20 |1972 | | |519 2/3|

|(j |0 |8 |7 |0 | | | | |

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

Транспортная задача формулируется следующим образом. Однородный продукт,

сосредоточенный в m пунктах производства (хранения) в количествах а1,

а2,..., аm единиц, необходимо распределить между n пунктами потребления,

которым необходимо соответственно b1, b2,..., bn единиц. Стоимость

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

назначения равна сij и известна для всех маршрутов. Необходимо составить

план перевозок, при котором запросы всех пунктов потребления были бы

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

транспортные расходы по доставке продуктов были минимальными.

Обозначим через хij количество груза, планируемого к перевозке от i-го

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

[pic] (1)

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

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

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

= 1,n

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

[pic] (2)

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

[pic] (3)

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

[pic] (4)

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

х11 > 0 ,. . . ., xmn > 0.

(5)

Для решения транспортной задачи чаще всего применяется метод потенциалов.

Пусть исходные данные задачи имеют вид

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

С = [pic] [pic] [pic][pic][pic]

Общий объем производства (аi = 55+60+63 = 178 больше, требуется всем

потребителям (bi = 42+50+44+30 = 166, т.е. имеем открытую модель

транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт

потребления с объемом потребления 178-166 = 12 единиц, причем тарифы на

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

переменные, добавляемые к левым частям неравенств для превращения их в

уравнения, входят в функцию цели с нулевыми коэффициентами.

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

западного угла(.

| |b1 =41 |b2 |b3 =44|b4 |b5 | |

|Потребление | |=50 | |=30 |=12 | |

|Производство | | | | | | |

| а1 =54 | 41 |13 | | | |p1 =0 |

| a2 =60 | |37 |23 | | | p2 =|

| a3 =63 | * | |21 |30 |12 | p3 =|

| |q1 = |q2 = |q3 = |q4 = |q5 = | |

Следует иметь в виду, что по любой транспортной таблице можно

восстановить соответствующий предпочитаемый эквивалент системы уравнений

(3), (4), а в таблице записаны лишь правые части уравнений, причем номер

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

базисной. Так как в системе (3), (4) ровно m + n - 1 линейно независимых

уравнений, то в любой транспортной таблице должно быть m + n - 1 занятых

клеток.

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

([pic])

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

(ij = (Aij - сij i = 1,m; j = 1,n

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

(ij = pi + qj - cij i = 1,m; j = 1,n

(6)

Один из потенциалов можно выбрать произвольно, так как в системе (3), (4)

одно уравнение линейно зависит от остальных. Положим, что р1 = 0. Остальные

потенциалы находим из условия, что для базисных клеток [pic]. В данном

случае получаем

(11 = 0, p1 + q1 - c11 = 0, 0+q1 -1 = 0, q1 = 1

(12 = 0, p1 + q2 - c12 = 0, 0+q2 -4 = 0, q2 = 4

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

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

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

(21 = p2 + q5 - c21 = 2+1-3 = 0

(31 = p3 + q1 - c31 = 6+1-2 = 5

(32 = 5; (13 = -3; (14 = -1; (24 = -2; (15 = -6; (25 = -4.

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

max ([pic]) = 5 = [pic]

Для найденной свободной клетки 31 строим цикл пересчета - замкнутую

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

параллельны строкам и столбцам таблицы, одна из вершин находится в данной

свободной клетке, а все остальные - в занятых клетках. Это будет 31-11-12-

22-23-33. Производим перераспределение поставок вдоль цикла пересчета

|41 |13 | | |41-( |13+( | | |20 |34 | |

| |37 |23 | | |37-( |23+( | | |16 |44 |

| | |21 | |( | |21-( | |21 | | |

[pic]= 21

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

| |b1 =41 | b2 |b3 =44|b4 | | |

|bj | |=50 | |=30 |b5=12 | |

| ai | | | | | | |

| а1 =54 | 20 |34 | | * | |p1 =0 |

| a2 =60 | |16 |44 | | | |

| | | | | | |p2 =2 |

| a3 =63 | 21 | | |30 |12 | p3 =1|

| |q1 =1 |q2 = 4|q3 = 0 |q4 = 6|q5= -1| |

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

будет иметь свободная клетка 14. Для нее строим цикл пересчета 14-11-31-34

производим перераспределение

|20 | | |20-(|( | | |20 |

|21 |30 | |21+(|30-( | |42 |10 |

(max = 20

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

пор, пока не придем к таблице, для которой все

(ij ( 0 i = 1,m; j = 1,n

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

допустимое решение

[pic] [pic] [pic] [pic]

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

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

Динамическое программирование - это вычислительный метод для решения

задач управления определенной структуры. Данная задача с 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) мы считаем заданными, заметив, что их определение -

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

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

задачи.

Введем параметр состояния и определим функцию состояния. За параметр

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

функцию состояния Fk(() определим как максимальную прибыль на первых k

предприятиях, если они вместе получают ( рублей. Параметр ( может

изменяться от 0 до b. Если из ( рублей k-е предприятие получит xk

рублей, то каково бы ни было это значение, остальные ( - xk рублей

естественно распределить между предприятиями от первого до (К-1)-го

так, чтобы была получена максимальная прибыль Fk-1(( - xk). Тогда прибыль k

предприятий будет равна fk(xk) + Fk-1(( - xk). Надо выбрать такое значение

xk между 0 и (, чтобы эта сумма была максимальной, и мы приходим к

рекуррентному соотношению

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

0 ( xk ( (

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

F1(() = f1(()

Рассмотрим конкретный пример. Пусть производственное объединение состоит

из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700

тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей.

Значения функций fj(xj) приведены в таблице 1, где, например, число 88

означает, что если третье предприятие получит 600 тыс. руб. капитальных

вложений, то прирост прибыли на этом предприятии составит 88 тыс. руб.

Таблица I

[pic]

Прежде всего заполняем табл. 2. Значения f2(x2) складываем со значениями

F1(( - x2) = f1((- x2) и на каждой северо-восточной диагонали находим

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

значение [pic]. Заполняем таблицу 3.

Продолжая процесс, табулируем функции F3((), [pic](() и т.д. В табл.

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