Построение математической модели.
Тема 1. Целочисленные задачи линейного программирования
К задачам целочисленного программирования относятся экстремальные задачи, переменные которых по смыслу задачи могут принимать только целочисленные значения.
Рассмотрим конкретную задачу целочисленного программирования.
1 Задача о оборудовании.
В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено S кв.м площади. На приобретение оборудования предприятие может израсходовать A руб. при этом оно может купить оборудование n видов. Единица оборудования i-го вида стоит ai руб. Приобретение оборудования i-го вида позволяет увеличить выпуск продукции в смену на bi ед. Для установки одного оборудования i-го вида требуется ci кв.м. площади. Определить сколько единиц оборудования каждого вида необходимо закупить, чтобы максимально увеличить выпуск продукции.
Построение математической модели. Предположим, что предприятие закупит оборудование i-го вида в количестве x i шт.
Целевая функция задачи описывает увеличение объема выпуска продукции, которое должно быть максимальным, т.е.
F = b1 x 1 + b2 x 2 + … + bn x n → max.
Запишем теперь ограничения задачи.
Первое ограничение относится к стоимости оборудования и выделенной для этой цели денежных средств:
a1 x1 + a2 x2 + … + an x n ≤ A.
Второе ограничение относится к размеру площади, которое может быть выделено под оборудование:
|
|
|
c1 x1 + c2 x2 + … + cn x n ≤ S .
По смыслу задачи, количество оборудования может быть только целым и неотрицательным числом:
x i ≥ 0 и x i – целые
Задачи сводящиеся к транспортной модели
Довольно обширный класс экономических задач, не имеющих ничего общего с транспортной задачей, тем не менее сводится к транспортной модели, и для решения таких задач может быть использован алгоритмы и методы решения транспортных задач (Методическое пособие Лабораторная работа №2. Транспортные задачи и их решение средствами Excel).
В этом случае величины транспортных тарифов имеют различный смысл в зависимости от конкретной экономической задачи, как и величины поставляемых грузов от поставщиков и потребности в них у потребителей.
Рассмотрим конкретную задачу.
Задача. Имеется n участков земли, на которых могут быть засеяны m видов культур. Площадь каждого участка соответственно равна si. Каждой i-ой культурой следует засеять площадь vi . Урожайность каждой из культур для каждого из участков различна и задается матрицей C= {cij}.
Определить, сколько гектаров каждой культуры на каждом из участков следует засеять так, чтобы общий сбор зерна был максимальным.
Построение математической модели
|
|
|
Обозначим искомые величины – площадь культуры j засеянной на участке i , как x ij , i = 1, …, n, j =1, …, m.
Целевая функция представляет собой суммарную урожайность всех культур со всех участков. Так как урожайность культуры j с единицы площади участка i равна с ij , то урожайность этой культуры с площади x ij составит с ij x ij . Суммарная урожайность – целевая функция, которая должна принимать максимальное значение
.
Ограничения задачи. Поскольку на каждом из трех участков засеиваются все четыре культуры, то сумма площадей занимаемой каждой культурой на каждом участке, должна быть равна имеющейся площади этого участка:
, i = 1, …, n
С другой стороны, суммарная площадь отводимая под каждую культуру, которая засеивается на каждом участке, также должна быть равна заданной площади
, j =1, …, m
Площади культур не могут выражаться отрицательными величинами и потому необходимо выполнение условий:
x ij ≥ 0, i = 1, …, n, j =1, …, m
Эта модель по ограничениям полностью совпадает с математической моделью транспортной задачи. Модель является сбалансированной.
В данной задаче необходимо максимизировать целевую функцию. Для перехода к стандартной транспортной модели надо заменить функцию F на противоположную функцию F' = – F, которую необходимо минимизировать, т.е.
|
|
|
Далее задача решается известными методами.
Задача о ранце
К этому классу задач относятся задачи, в которых необходимо при ограниченных объемах перевозчика и ограничениях по весу, перевезти как можно больше груза или, как можно больше значимого груза. Причем загружаться могут несколько грузов каждого вида.
Рассмотрим конкретную задачу.
Задача.
Морское судно грузоподъемностью M тыс. т. и вместимостью V тыс куб.м. может быть использовано для перевозки n видов неделимых грузов, имеющих массу mi, объем vi и стоимость ci.
Определить, сколько единиц груза каждого вида следует загрузить на судно, чтобы суммарная стоимость груза была максимальной и выполнялись ограничения по вместимости и грузоподъемности судна.
Построение математической модели.
Обозначим через x i количество единиц i-го груза загружаемого на судно. Целевая функция, выражающая суммарную стоимость груза на судне, будет равна:
.
Ограничения задачи диктуются ограничением на грузоподъемность судна
и ограничением на вместимость судна
Количество единиц грузов не может быть отрицательным и дробным, т.к. все грузы неделимы, поэтому
|
|
|
x i ≥ 0, целые, i = 1, …, n
Дата добавления: 2022-12-03; просмотров: 39; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!