МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ ТЕМА 5

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Математическое программирование рассматривает задачи оптимального использования и распределения ресурсов при наличии ограничений на их использование Разделы математи- ческого програм- мирования Разделы математи- ческого програм- мирования Целочисленное Динамическое Линейное Нелинейное Этап постановки задачи и формализации содержит: Идентификацию переменных модели, оптимальные значения которых должны быть получены; Задание выражения для целевой функции, предполагающее либо максимизацию, либо минимизацию результативного показателя, либо его стремление к определённой величине; Задание системы ограничений, которая позволила бы определить область допустимых значений целевой функции

КЛАССИЧЕСКИЕ ЗАДАЧИ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ Транспортная задача Транспортная задача Задача оптимального производственного планирования Задача оптимального производственного планирования Задача о снижении себестоимости Задача целочисленного программирования (задача о рюкзаке) Задача целочисленного программирования (задача о рюкзаке) Задача о замене оборудования Линейное программирование Нелинейное программирование Динамическое программирование Целочисленное программирование

ПОСТАНОВКА ТРАНСПОРТНОЙ ЗАДАЧИ УСЛОВИЕ: В m пунктах производится однородный продукт, причём a i (i = 1,…,m) – количество продукта, произведённого в i-м пункте. В n пунктах имеется потребность в этом продукте, причём b j (j=1,…,n) – потребность j –го пункта. Известна стоимость перевозки единицы продукции из каждого пункта А в каждый пункт В: C ij – стоимость перевозки единицы продукции из i–го пункта производства в j–й пункт потребления. C 11 C 12 …C 1n C 21 C 22 …C 2n ………… C m1 C m2 …C mn C 11 C 12 …C 1n C 21 C 22 …C 2n ………… C m1 C m2 …C mn Предполагается, что объем производства и потребности пунктов потребления совпадают. Необходимо определить маршрут перевозок (сколько единиц продукции перевозить из каждого пункта производства в каждый пункт потребления), минимизирующий общие затраты на перевозки. Общие затраты могут быть представлены матрицей: Пункты производства Пункты потребления

ПОСТАНОВКА ТРАНСПОРТНОЙ ЗАДАЧИ А1А1 А1А1 А2А2 А2А2 АmАm АmАm B1B1 B1B1 B2B2 B2B2 BnBn BnBn X 11 X 12 X 1n X 21 X 22 X 2n 1) Переменные: x ij – количество продукта, перевозимого из i–го пункта производства в j–й пункт потребления 2) Целевая функция: запрет встречных перевозок x ij 0 X m1 X m2 X mn Схема перевозок …… 3) Система ограничений: по производству по потреблению

ЗАДАЧА ОПТИМАЛЬНОГО ПРОИЗВОДСТВЕННОГО ПЛАНИРОВАНИЯ (ОПТИМАЛЬНОГО ИСПОЛЬЗОВАНИЯ РЕСУРСОВ) Компания по производству холодильного оборудования на одной линии производит две марки А470 и А370. Обе модели приносят прибыль: 70 и 60 у.е. соответственно. Имеются ограничения по количеству, в котором они могут быть произведены: на производство А470 – 3 чел/час. и на А370 – 2 чел/час. Общее количество человеко-часов в неделю не должно превышать Стоимость сырья расходуемого на единицу продукции: на А470 – 50 у.е. и на А370 – 60 у.е. Недельная смета на сырьё у.е. Необходимо определить оптимальный план производства холодильников на неделю, обеспечивающий максимальную прибыль x – количество единиц произведённых холодильников марки А470 в неделю; y – количество единиц марки А370. 1) Переменные: 2) Целевая функция: 3) Система ограничений: по производству:по бюджету: по положительности переменных:

1) Рассчитаем данные, необходимые для построения на графике прямых, определяющих ограничения (от неравенств перейдём к уравнениям): 3)Возможные решения могут быть получены в точках А, В, С и D. Координаты точек: А [0; 0], В [0; 1250], D [1000; 0] 4) Подставим координаты точек В, С и D в целевую функцию: А:70 * * 0 = 0 В:70 * * 1250 = С:70 * * 937 = D:70 * * 0 = План производства: 375 единиц холодильников марки А470 и 937 единиц холодильников марки А370. Прибыль – у.е. План производства: 375 единиц холодильников марки А470 и 937 единиц холодильников марки А370. Прибыль – у.е. РЕШЕНИЕ ГРАФИЧЕСКИМ МЕТОДОМ x = 0 y = 0 y = 1250 x = 1500 x = 0 y = 0 y = 1250 x = x + 2у = 3000 x=0 y=0 y=1500 x=1000 x=0 y=0 y=1500 x= x + 60y = ) Строим график, определяя область возможных решений Х Y Координаты точки С необходимо рассчитать решив систему уравнений, описывающих прямые на графике, пересечение которых определяется точкой С: 50 * x + 60 * y = * x + 2 * y = 3000 Отсюдаx = 375y = 937 область допустимых решений

ПОСТАНОВКА ЗАДАЧИ ПРОИЗВОДСТВЕННОГО ПЛАНИРОВАНИЯ УСЛОВИЕ: Из технологических соображений известен перечень продукции, которую предприятие может производить без дополнительных капитальных вложений. Также известны вид и количество ресурсов, отпущенных для производства. При формировании производственного плана необходимо учитывать ограниченность такого рода ресурсов. Известна структура материальных затрат и доходов. Материальные затраты задаются в виде коэффициентов удельных затрат, а доходы – в виде показателя прибыли на единицу продукции. Цель процесса планирования: выбор объёма производства для каждого вида продукции, обеспечивающего максимизацию общей прибыли. ВВЕДЕМ ОБОЗНАЧЕНИЯ: n – количество видов продукции (j = 1, 2… n), которую производит предприятие; x j – количество производимого j-го продукта; m – количество видов ресурсов (i = 1, 2 … m), которыми располагает предприятие; b i – общее количество ресурсов i-го вида, отпущенного для производственного потребления; a ij – количество i-го ресурса, расходуемое на производство единицы j-го продукта; C j – прибыль при производстве j-го продукта.

ПОСТАНОВКА ЗАДАЧИ ПРОИЗВОДСТВЕННОГО ПЛАНИРОВАНИЯ x 1, x 2, … x n – производственная программа, оптимальное значение элементов которой необходимо найти Систематизируем постановку задачи в табличном виде Ресурсы Продукты Лимиты … … n n 1 1 a 11 a 12 … … a 1n b1b1 b1b1 2 2 a 21 a 22 … … a 2n b2b2 b2b2 … … … … … … … … … … … … m m a m1 a m2 … … a mn bmbm bmbm Прибыль C1C1 C1C1 C2C2 C2C2 … … CnCn CnCn 1) Переменные: 2) Целевая функция: 3) Система ограничений:

ПОСТАНОВКА ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ (ЗАДАЧА О РЮКЗАКЕ) УСЛОВИЕ: Имеется n предметов П 1, П 2, …, П n, которые турист собирается взять в поход. Каждый из этих предметов занимает определённый объём v 1, v 2, …, v n и имеет определённый вес p 1, p 2, …, p n. Ограничение на общий объём рюкзака - V и на вес - Р. Количественно измерена полезность каждого предмета c 1, c 2, …, c n. Необходимо выбрать те предметы, которые обладая в сумме максимальной полезностью, не превышали бы ограничение по объёму и весу. Ограничение по весу Числа могут принимать значения только 0 или 1: x 1, x 2, …, x n = [0;1] – целые Ограничение по объёму 1) Переменные: 2) Целевая функция: 3) Система ограничений: Ограничение по целостности предметов

ПОСТАНОВКА ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЗАДАЧА СНИЖЕНИЯ СЕБЕСТОИМОСТИ) УСЛОВИЕ: Продукцию П можно производить на двух видах оборудования О 1 и О 2. Стоимость единицы продукции равна С 1 – при выпуске на оборудовании О 1 и С 2 – при выпуске на О 2. Для изготовления одной единицы продукции на первом оборудовании требуется время а 11, а на втором – а 12 (всего не более b 1 часов). Для изготовления одной единицы продукции на первом оборудовании требуется а 21 кВт*часов, а на втором – а 22 кВт*часов (всего не более b 2 кВт*часов). Необходимо найти количество единиц продукции, производимой на оборудовании каждого вида, которое бы обеспечивало минимизацию затрат на производство при выполнении имеющихся ограничений на рабочее время и потребление электроэнергии. x 1 – количество единиц продукции, производимой на оборудовании О 1 x 2 – количество единиц продукции, производимой на оборудовании О 2 По ресурсам рабочего времени: Исходя из условия задачи очевидно, что переменные могут быть только положительными: X 1 >= 0 и X 2 >= 0 1) Переменные: 2) Целевая функция: 3) Система ограничений: По потреблению электроэнергии:

ПОСТАНОВКА ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ (ЗАДАЧА О ЗАМЕНЕ ОБОРУДОВАНИЯ) УСЛОВИЕ: В течение периода времени, состоящего из n–этапов, предприятие должно производить изделия на оборудовании, комплект которого вместе с установкой стоит Z д.е. Со временем оборудование изнашивается и стоимость продукции C(t), которую можно получить на протяжении каждого этапа снижается, если растёт возраст оборудования t, причём параллельно возрастают затраты на ремонт и обслуживание оборудования r(t). Надо определить те моменты времени, в которые следует заменять старый комплект оборудования на новый, чтобы прибыль от производства была максимальной. Под прибылью понимается суммарная стоимость выпущенной продукции за минусом либо стоимости обслуживания и ремонта, либо замены оборудования. 1)Обозначим моменты начала каждого этапа через Т 0, Т 1 …Т n-1, тогда моменты завершения этапов соответственно Т 1, Т 2 …Т n. Состояние процесса на каждом этапе Т k (k = 1; … ; n – 1) характеризуется возрастом оборудования S k i, эксплуатируемого к началу данного этапа. 2) На каждом этапе можем выбрать одно из 2-х управленческих решений: U(1) – сохранить установленное оборудование и продолжить выпускать продукцию U(2) – заменить установленное оборудование

ПОСТАНОВКА ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ (ЗАДАЧА О ЗАМЕНЕ ОБОРУДОВАНИЯ) 3) Прибыль f k, получаемая на k этапе, зависит с одной стороны, от состояния оборудования S k i, с другой стороны – от выбранного варианта решения U k : 4) Составляем целевую функцию: Суммарная прибыль, которую надо максимизировать представляем собой сумму прибылей на всех этапах: 4) Составляем целевую функцию: Суммарная прибыль, которую надо максимизировать представляем собой сумму прибылей на всех этапах: C(t) - r(t), если U k = U(1) f k = f k (S k i, U k ) = C(0) - r(0) + Z, если U k = U(2)

НЕДОПУСТИМЫЕ И НЕОГРАНИЧЕННЫЕ РЕШЕНИЯ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКСНЫМ МЕТОДОМ Вводятся «свободные» переменные в ограничения и неравенства заменяются уравнениями: Свободные переменные S 1 и S 2 вводятся и в целевую функцию Этап 1 Этап 2 Составляется таблица: РядБазисЗначениеxyS1S1 S2S2 1S1S S2S P Указываются переменные, которые могут дать решение задачи. В этом случае x 1 =0, x 2 =0, т.е. производство стоит и ресурсы не используются

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКСНЫМ МЕТОДОМ Таблица преобразуется для поиска решения задачи: а) находится осевая колонка (наибольшее положительное значением в последнем ряду); б) находится осевой ряд: делится каждое число в колонке значений на соответствующее число осевой колонки. Наименьшее значение, полученное при делении, определяет осевой ряд; в) находится осевое значение – на пересечении осевой колонки и осевого ряда; г) делится каждое число в осевом ряду на осевое значение; д) Каждое число осевой колонки приводится к нулю. Для этого отнимается кратное число осевого ряда из других рядов а) находится осевая колонка (наибольшее положительное значением в последнем ряду); б) находится осевой ряд: делится каждое число в колонке значений на соответствующее число осевой колонки. Наименьшее значение, полученное при делении, определяет осевой ряд; в) находится осевое значение – на пересечении осевой колонки и осевого ряда; г) делится каждое число в осевом ряду на осевое значение; д) Каждое число осевой колонки приводится к нулю. Для этого отнимается кратное число осевого ряда из других рядов Этап 3 РядБазисЗначениеxyS1S1 S2S2 Значение/ось 1S1S /3=1000 2S2S /50= P РядБазисЗначениеxyS1S1 S2S2 11x100010,6670,3330 R2-50*R12S2S ,667-16,6671 R3-70*R13-P ,33323,3330 S1 замещено на x в колонке «Базис». Получено более качественное решение. При x=1000 прибыль увеличилась до 70000

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКСНЫМ МЕТОДОМ Уточняется, можно ли улучшить полученное решение. Если все значения в последнем ряду 0, то полученное решение – оптимальное. Если нет – процесс повторяется с третьего этапа: Уточняется, можно ли улучшить полученное решение. Если все значения в последнем ряду 0, то полученное решение – оптимальное. Если нет – процесс повторяется с третьего этапа: Этап 4 РядБазисЗначениеxyS1S1 S2S2 Значение/ ось 1x100010,6670, /0,677 2S2S ,667-16, /26,667 3-P ,33323,3330 РядБазисЗначениеxyS1S1 S2S2 R1-0,667*R21x375100,75-0,025 2y937,501-0,6250,0375 R3-13,333*R23-P ,05 Решение получено, т.к. в последнем ряду все значения меньше или равны 0 а) находится осевая колонка - y; б) находится осевой ряд -2; в) находится осевое значение – 26,667; д) Каждое число осевой колонки приводится к нулю