Содержание1. Сформулировать линейную производственную задачу и составить ее математическую модель, взяв исходные данные из приложения 1.
Технологическая матрица A затрат ресурсов на единицу продукции каждого вида, вектор B объемов ресурсов и вектор C удельной прибыли:
Предположим, что предприятие или цех выпускает n видов изделий, имея m групп оборудования. Известны нормы времени на обработку каждого изделия на каждой группе оборудования, например, в минутах или часах и фонд времени работы каждой группы оборудования. Пусть, кроме того, известно, что из всех n видов изделий наибольшим спросом пользуются k видов. Требуется составить план производства, при котором выпуск дефицитных изделий будет наибольшим возможным.
Компоненты производственной программы должны удовлетворять условию, что суммарное время обработки всех изделий на данной группе оборудования не должно превышать фонда времени работы этой группы оборудования. На обработку x1 единиц первого изделия на i-й группе оборудования будет затрачено ai1x1 единиц времени, на обработку x2 единиц второго изделия на той же группе оборудования будет затрачено ai2x2 единиц времени и т.д. Необходимое время на обработку всех x1, x2, x3, x4 изделий на i-й группе оборудования будет равно сумме
Эта сумма не может превышать фонд времени работы i-й группы оборудования, т.е. должна быть bi. Выписывая такие условия для всех 3-x групп оборудования, получаем:
(1)
Так как компоненты плана суть количество изделий и, следовательно, не могут быть выражены отрицательными числами, то естественным образом добавляются условия:
x1 0, x2 0 x3 0, x4 0. (2)
Обозначим через сj прибыль на единицу j-го изделия. При плане производства (х1, х2, х3, x4) прибыль предприятия будет равна:
z = c1x1 + c2x2 + c3x3 + c4x4 = 27x1 + 39x2 + 18x3 + 20x4. (3)
Мы хотим составить производственную программу (х1, х2, …, хn) так, чтобы функция (3) приняла наибольшее значение при выполнении всех других условий.
Система линейных неравенств (1), (2) и линейная форма (3) образуют математическую модель задачи о рациональном использовании производственных мощностей. Среди всех решений системы линейных неравенств (1), удовлетворяющих условию неотрицательности (2), необходимо найти такое решение, при котором линейная форма (3) принимает наибольшее возможное значение. Это – задача линейного программирования.
Последовательное улучшение производственной программы
Получили задачу на условный экстремум. Для ее решения систему неравенств (2) при помощи дополнительных неотрицательных неизвестных х5, х6, х7 заменим системой линейных алгебраических уравнений
(4)
где дополнительные переменные имеют смысл остатков соответствующих ресурсов. Среди всех решений системы уравнений (4), удовлетворяющих условию неотрицательности
х10, х20, … , х50, … , х70. (5)
надо найти то решение, при котором функция (3) примет наибольшее значение.
Воспользуемся тем, что правые части всех уравнений системы (4) неотрицательны, а сама система имеет предпочитаемый вид – дополнительные переменные являются базисными. Приравняв к нулю свободные переменные х1, х2, х3, х4, получаем базисное неотрицательное решение
x1=0, x2=0, x3=0, x4=0, x5 =140, x6=90, x7=198 (6)
первые четыре компоненты которого определяют производственную программу
x1=0, x2=0, x3=0, x4=0 (7)
по которой мы пока ничего не производим.
Составим начальную симплекс-таблицу:
Таблица 1.
Базис 27 39 18 20 0 0 0 Пояснения
Н x1 x2 x3 x4 x5 x6 x7
0 х5 140 2 1
6 5 1 0 0
0 х6 90
0 3 0 4 0 1 0
0 х7 198 3 2 4 0 0 0 1
0 – z -27 -39 -18 -20 0 0 0
Перейдем к новому базису. Определим переменную, которая войдет в базис. Выбираем ту переменную, которая дает наиболее быструю прибыль. Из выражения (3) видим, что это x2. Она становится базисной.
Определим переменную, покидающую базис. Вычислим симплексные отношения, расположенные в последнем столбце симплекс-таблицы. Здесь числителем является свободный член ограничения (столбца Н), знаменателем – положительные коэффициенты ведущего столбца, т.е. столбца x2. Строка, в которой находится минимальное симплексное отношение (90/3 = 30), является ведущей строкой, в этой же строке находится переменная x6, покидающая базис. На пересечении ведущего столбца и ведущей строки находится ведущий элемент (a22 = 3). Пересчитаем таблицу:
Таблица 2.
0 х5 110
2 0 6 11/3 1 -1/3 0
39 х2 30 0 1 0 4/3 0 1/3 0
0 х7 138 3 0 4 -8/3 0 -2/3 1
1170-z -27 0 -18 32 0 13 0
Приравняв к нулю свободные переменные х1, х3, х4, х6, получаем базисное неотрицательное решение, причем первые четыре компоненты его определяют новую производственную программу
х1=0, х2=30, х3=0, х4=0. (8)
Исследуем, является ли эта программа наилучшей, т.е. обеспечивает ли она наибольшую прибыль. Для этого выразим функцию прибыли (3) через новые свободные переменные х1, х3, х4, х6.
(9)
Видим, что программа (9) не является наилучшей, так как прибыль будет расти, если мы начнем производить или первую, или третью продукцию, но наиболее быстро функция z растет при возрастании х1. Поэтому принимаем х1 за разрешающую неизвестную, находим разрешающее уравнение по
= 46.
Пересчитываем таблицу.
Таблица 3.
0 х5 18 0 0 10/3 49/9 1 1/9 -2/3 все j 0
39 х2 30 0 1 0 4/3 0 1/3 0
27 х1 46 1 0 4/3 -8/9 0 -2/9 1/3
2412-z 0 0 18 8 0 7 9
Определяем базисное неотрицательное решение рассматриваемой задачи:
x1=46, x2=30, x3=0, x4=0, x5=18, x6=0, x7=0 (10)
производственную программу:
x1=46, x2=30, x3=0, x4=0 (11)
и остатки ресурсов:
первого вида х5=18
второго вида х6=0 (12)
третьего вида х7=0
Выразим функцию цели z через свободные переменные
z = 2412 - 18х3 - 8х4 - 7х6 (13)
тогда в силу того, что все xj 0, прибыль будет наибольшей тогда, когда
x3=0, x4=0, x6=0 (14)
Это означает, что производственная программа (11) является наилучшей и обеспечивает предприятию наибольшую прибыль
zmax = 2412 . (15)
Итак, организовав направленный перебор базисных неотрицательных решений системы условий задачи, мы пришли к оптимальной производственной программе и указали остатки ресурсов, а также максимальную прибыль.
Рассмотрим узкие места производства.
Остатки ресурсов второго и третьего видов равны нулю, это означает, что второй и третий виды сырья используются полностью при выполнении оптимальной производственной задачи. Это и есть узкие места производства.
Из последней симплексной таблицы запишем обращенный базис Q-1, соответствующий оптимальному набору базисных неизвестных (x5, x6, x7):
(16)
Проверим выполнение соотношения:
H = Q–1B.
Имеем
Умножим Q–1 на B:
Т.к. по оптимальной производственной программе два вида продукции (x3 и x4) не должны выпускаться, то составим математическую модель задачи оптимизации производственной программы с двумя оставшимися переменными (x1 и x2), сохранив прежнюю нумерацию переменных и решим ее графически. Получим исходные данные:
Математическая модель:
(17)
x1 0, x2 0. (18)
z = 27x1 + 39x2. (19)
Полученную задачу линейного программирования с двумя переменными можно решить графически. Система линейных неравенств (17), (18) определяет выпуклый многоугольник OPQR допустимых решений. Линии уровня функции Z перпендикулярны вектору-градиенту grad Z = (27, 39) и образуют семейство параллельных прямых (градиент указывает направление возрастания функции).ВведениеТранспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в 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)
Исходные данные задачи имеют вид:
А(а1, а2, а3) = (70; 40; 60); В(b1, b2, b3, b4) = (37; 39; 48; 40);
С = .
Общий объем производства аi = 70+40+60 = 170 больше, чем требуется всем потребителям bi = 37+39+48+40 = 164, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 170-164 = 6 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.
Первое базисное допустимое решение легко построить по правилу северо-западного угла.
Таблица 1.
ПН
ПО b1 b2 b3 b4 b5 Запасы аi
а1 2
37 1
33 6
– 5
– 0
– 70
а2 5
– 3
6 7
34 6
– 0
– 40
а3 3
– 2
– 4
14 2
40 0
6 60
Потребности bj 37 39 48 40 6
В этом опорном плане 7 занятых клеток. План невырожденный, т.к. число клеток равно m + n – 1 = 3 + 5 – 1 = 7. Общая стоимость перевозок тогда равна:
F(X1) = 3*37+1*33+3*6+7*34+4*14+2*40+0*6 = 536.
Найдем потенциалы поставщиков и заказчиков. Пользуясь теоремой о потенциалах, можем записать 7 уравнений для определения pi и qj:
p1 + q1 = c11 = 2, p1 + q2 = c12 = 1, p2 + q2 = c22 = 3, p2 + q3 = c23 = 7,
p3 + q3 = c33 = 4, p3 + q4 = c34 = 2, p3 + q5 = c35 = 0.
Приравнивая p1 = 0, находим значения остальных потенциалов. Значения записываем в клетки таблицы.
Таблица 2.
ПН
ПО b1
q1 = 2 b2
q2 = 1 b3
q3 = 5 b4
q4 = 3 b5
q5 = 5 Запасы аi
а1
p1 = 0 2
37 1
33 6
– 5
– 0
– 70
а2
p2 = 2 5
– 3
6 7
34 6
– 0
– 40
а3
p3 = – 1 3
– 2
– 4
14 2
40 0
6 60
Потребности bj 37 39 48 40 6
Проверим оптимальность опорного плана. Подсчитаем оценки для свободных клеток:
13 = – 1, 14 = – 2, 15 = 1 0, 21 = – 1, 24 = – 1, 25 = 3 0,
31 = – 2, 32 = – 2.
Среди оценок есть положительные, следовательно, план нуждается в изменении. Модификацию плана проводим с помощью пересчета по циклу. Начинаем цикл с клетки с самой большой оценкой 25 = 3. Получим цикл: 25-35-33-23-25.
Таблица 3.
ПН
ПО b1
q1 = 2 b2
q2 = 1 b3
q3 = 5 b4
q4 = 3 b5
q5 = 5 Запасы аi
а1
p1 = 0 2
37 1
33 6
– 5
– 0
– 70
а2
p2 = 2 5
– 3
6 7
34
6
– 0
– 40
а3
p3 = – 1 3
– 2
– 4
14 2
40 0
6 60
Потребности bj 37 39 48 40 6
Производим перераспределение поставок вдоль цикла пересчета:
= 6. Получаем второе базисное допустимое решение:
Таблица 4.
ПН
ПО b1
q1 = 2 b2
q2 = 1 b3
q3 = 5 b4
q4 = 3 b5
q5 = 5 Запасы аi
а1
p1 = 0 2
37 1
33 6
– 5
– 0
– 70
а2
p2 = 2 5
– 3
6 7
28 6
– 0
6 40
а3
p3 = – 1 3
– 2
– 4
20 2
40 0
– 60
Потребности bj 37 39 48 40 6
Стоимость перевозок по полученному плану равна:
F(X2) =2*37+1*33+3*6+7*28+0*6+4*20+2*40 = 481.
Найдем потенциалы поставщиков и потребителей, занося данные в новую таблицу.
Таблица 5.
ПН
ПО b1
q1 = 2 b2
q2 = 1 b3
q3 = 5 b4
q4 = 3 b5
q5 = – 2 Запасы аi
а1
p1 = 0 2
37 1
33 6
– 5
– 0
– 70
а2
p2 = 2 5
– 3
6 7
28 6
– 0
6 40
а3
p3 = – 1 3
– 2
– 4
20 2
40 0
– 60
Потребности bj 37 39 48 40 6
Проверим оптимальность опорного плана. Подсчитаем оценки для свободных клеток:
13 = – 1, 14 = – 2, 15 = – 2, 21 = – 1, 24 = – 1, 31 = – 2, 32 = – 2, 35 = – 3.
Среди оценок нет положительных, следовательно, получили оптимальное решение:
, причем на второй базе останется запас продукта в 6 единиц.
4. Методом динамического программирования решить задачу распределения капитальных вложений между четырьмя предприятиями производственного объединения, располагающего суммой в 700 тыс. руб.
Таблица 1.
хj 0 100 200 300 400 500 600 700
f1 (xj) 0 15 26 38 45 52 58 63
f2 (xj) 0 10 17 23 29 34 38 41
f3 (xj) 0 11 19 26 30 33 35 36
f4 (xj) 0 25 34 41 46 50 53 56
Требуется найти такое распределение (x1, x2, x3, x4) капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли
z = f1(x1) + f2(х2) + f3(x3) + f4(x4)
при ограничении по общей сумме капитальных вложений
x1 + x2 + x3 + x4 = 700,
причем будем считать, что все переменные xj принимают только целые неотрицательные значения, кратные 100
xj = 0, или 100, или 200, или 300, ...
Введем параметр состояния и определим функцию состояния. За параметр состояния примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk() определим как максимальную прибыль на первых k предприятиях, если они вместе получают рублей. Параметр может изменяться от 0 до 700. Если из рублей k-е предприятие получит xk рублей, то каково бы ни было это значение, остальные – xk рублей естественно распределить между предприятиями от первого до (k – 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. Если же k = 1, то
F1() = f1().
Прежде всего заполняем табл. 2. Значения f2(x2) складываем со значениями F1( – x2) = f1( – x2) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение . Заполняем таблицу 3.Литературанет
|
|
