Глава 1. Линейное программирование 3
Глава 2. Транспортная задача линейного программирования (тз) 68
2.1. Математическая модель транспортной задачи 68
2.2. Решение транспортной задачи 72
Глава 3. Динамическое программирование 98
3.1. Задача оптимального распределения ресурсов 99
3.2. Задача об оптимальной стратегии замены оборудования 105
Список использованной литературы 118
Глава 1. Линейное программирование
1.1. Математическая модель задачи линейного программирования
Математическое программирование – область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, то есть задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.
Математической моделью экономической задачи называется совокупность математических соотношений, описывающих рассматриваемый экономический процесс.
Для составления математической модели необходимо:
выбрать переменные задачи;
составить систему ограничений;
задать целевую функцию.
Переменными задачи называются величины , которые полностью характеризуют экономический процесс. Их обычно записывают в виде вектора .
Системой ограничений задачи называется совокупность уравнений и неравенств, которым удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других экономических условий. В общем случае система ограничений имеет вид
Целевой функцией (показателем эффективности, критерием оптимальности) называют функцию переменных задачи, которая характеризует качество выполнения задачи, и экстремальное значение которой требуется найти.
Экстремальным значением называют максимальное или минимальное значение.
Общая задача математического программирования формулируется следующим образом: найти значения переменных задачи , которые обеспечивают экстремум целевой функции
и удовлетворяют системе ограничений
Линейное программирование – это раздел математического программирования, изучающий задачи, математические модели которых включают только линейные функции относительно входящих в модель задачи переменных .
Допустимым решением (планом) ЗЛП называется вектор , удовлетворяющий системе ограничений задачи.
Множество допустимых решений задачи образует область допустимых решений (ОДР).
Допустимое решение (план), доставляющий целевой функции экстремальное значение, называется оптимальным решением (оптимальным планом). Его будем обозначать .
Экстремальное значение целевой функции .
Оптимальное решение не обязательно единственно. Возможны случаи, когда оно не существует, когда имеется конечное или бесконечное множество оптимальных решений.
Составим математические модели некоторых задач линейного программирования (примеры 1.1 – 1.3).
Имеются стержни, длиной 5 м. Их необходимо разрезать на заготовки 2-х видов: заготовки А – длиной 1,5 м и заготовки В – длиной 0,8 м для производства 20 изделий. На каждое изделие требуется две длинных заготовки (А) и три коротких (В). Определить число стержней, которое необходимо разрезать каждым из возможных способов, чтобы изготовить нужное число изделий и минимизировать отходы.
Прежде всего, перебрав все возможные способы, построим карту раскроя одного стержня:
Количество заготовок А (по 1,5 м)
Количество заготовок В (по 0,8 м)
Для изготовления 20 изделий потребуется заготовок А: 202 = 40 шт. и заготовок В: 203 = 60 шт.
1) Введем переменные. Обозначим за – количество стержней, которые будут разрезаныI способом, – II способом, – III способом, –IV способом.
Целевая функция Z – отходы. Ее будем минимизировать. Найдем отходы, полученные при разрезании стержней:
–отходы, полученные при разрезании стержнейI способом,
так как 5 – 3·1,5 = 0,5;
–отходы, полученные при разрезании стержней II способом,
так как 5 – 2·1,5 – 2·0,8 = 0,4;
–отходы, полученные при разрезании стержней III способом,
так как 5 – 1·1,5 – 4·0,8 = 0,3;
–отходы, полученные при разрезании стержней IV способом,
так как 5 – 6·0,8 = 0,2.
Составим систему ограничений задачи.
а) Ограничение на заготовки А.
При разрезании стержнейI способом получим заготовок А,
стержней II способом – заготовок А, стержней III способом – заготовок А, при разрезании стержней IV способом заготовок А не образуется. Таким образом, всего получим заготовок А, что по условию задачи должно быть не менее 40, то есть .
б) Аналогично получим ограничение на заготовки В:
в) Составим ограничения на экономический смысл переменных. Так как количество стержней может быть только неотрицательным числом, то и – целые.
Итак, математическая модель данной задачи имеет вид:
Предприятие за 10 часов должно произвести 31 единицу продукции вида П1 и 36 единиц продукции вида П2. Для производства продукции каждого вида может быть использовано оборудование А1 или А2.
Производительность оборудования этих групп различна и определяется величиной ед./ч, а стоимость 1 часа работы оборудования составляет усл. ден. ед./ч , гдеi – индекс, отличающий вид оборудования, а j – вид продукции. Требуется определить оптимальный план работы групп оборудования на протяжении 10 часов, при котором будет выполнен план выпуска продукции с минимальной себестоимостью.
Для наглядности составим таблицу:
Запас времени, ч
План производства, ед.
1) Обозначим за – время работы оборудования Аi по выпуску продукции Пj, .
2) Целевая функция будет представлять собой затраты на выпуск продукции, которые необходимо минимизировать. Так как затраты по выпуску продукции Пj на оборудование Аi составляют , то целевая функция будет иметь вид:
Составим систему ограничений.
а) Ограничение на выпуск продукции П1.
На оборудовании А1 будет произведено единиц продукции П1.
На оборудовании А2 будет произведено единиц продукции П1.
Таким образом всего продукции П1 будет произведено , что по условию должно быть равно 31, то есть получим ограничение
б) Аналогично получим ограничение по выпуску продукции П2:
в) Ограничение на время работы оборудования А1.
Время работы оборудования А1 по выпуску обоих видов продукции не превышает плановый период 10 ч, следовательно, ограничение будет иметь вид: .
г) Аналогично получим ограничение на время работы оборудования А2: .
д) Введем ограничения на экономический смысл переменных, так как время не может быть отрицательным, то .
Таким образом, математическая модель данной задачи будет иметь вид:
Предприятие может выпускать продукцию двух видов: П1 и П2. При этом используется три вида ресурсов: время работы оборудования, сырье и электроэнергия. Нормы расхода, запасы ресурсов и прибыль от реализации единицы продукции представлены в таблице:
Нормы расхода на единицу продукции
Время работы оборудования, ч
Прибыль от единицы продукции, руб.
Найти оптимальный план выпуска продукции.
, – объем выпускаемой продукции П1 и П2 соответственно, единиц.
Z – прибыль от реализации всей выпущенной продукции.
Математическая модель данной задачи будет иметь вид:
Методы решения задач линейного программирования будут рассмотрены ниже.
Необходимо за 24 часа изготовить максимальное количество изделий, общая себестоимость которых не должна превышать 2000 руб., используя при этом два станка. Производительность первого станка составляет 5 изделий в час, второго – 6 изделий в час. Себестоимость одного изделия, изготовленного на первом станке, составляет 9 руб., на втором станке – 10 руб. Составить математическую модель выпуска продукции на указанных станках.
Цех может выпускать 2 вида продукции, производство которых характеризуется следующими данными:
Время на производство изделия, ч
Количество металла на изделие, кг
Прибыль от реализации изделия, руб.
В планируемом месяце имеется 100 часов рабочего времени и 60 кг металла. Продукции I вида должно бать выпущено не менее 25 изделий. Составить математическую модель задачи выпуска продукции с максимальной прибылью от реализации.
Завод должен переслать 1000 деталей в ящиках двух типов. Ящик I типа вмещает 70 деталей, ящик II типа – 40 деталей. Стоимость пересылки одного ящика I типа составляет 30 руб., II типа – 20 руб. Для пересылки можно использовать не более 12 ящиков I типа. Составить математическую модель задачи пересылки всех деталей с наименьшими затратами
Имеются путевки в дома отдыха 3-х видов: на 7, 12 и 20 дней. Стоимость их 100 руб., 150 руб. и 250 руб. соответственно. Организация планирует закупить 21 путевку и потратить не более 3000 руб. Составить математическую модель задачи определения нужного числа путевок каждого вида, чтобы общее число дней отдыха по всем путевкам оказалось наибольшим.
Для рекламирования своей продукции фирма может использовать радио, телевиденье и общественный транспорт. Стоимость одной минуты рекламы на радио составляет 3 усл. ден. ед., а на телевиденье – 50 усл. ден. ед., в общественном транспорте – 2 усл. ден. ед. Объемы продаж увеличиваются от рекламы на радио, телевиденье и в общественном транспорте в соотношении 2:30:1. Фирма может использовать в месяц не более 10 минут эфирного времени на телевиденье и не более 100 минут на радио. На всю рекламу фирма запланировала потратить в месяц не более 900 усл. ден. ед. Составить математическую модель задачи эффективного вложения в рекламу денежных средств.
Нужно перевести по железной дороге 20 больших и 150 малых контейнеров, используя при этом минимальное количество вагонов. Вес малого контейнера составляет 2 тонны, а большого – 5 тонн. Грузоподъемность вагона – 60 тонн, недогрузка вагонов не допускается. Составить математическую модель задачи перевозки всех контейнеров.
Из пункта S в пункт T необходимо перевести 250 ед. оборудования типа I, 120 – типа II, 340 – типа III на автомобилях вида А, В, С и D. Количество оборудования одновременно вмещаемого на определенный автомобиль и затраты на одну поездку каждого автомобиля приведены в таблице: