Линейное программирование как метод оптимизации

Рефераты / Экономико-математическое моделирование / Линейное программирование как метод оптимизации

Обозначим количество единиц k-го вида изделий, выпускаемых предприятием, через xk, $k = \overline{1, K}$ . Тогда математическая модель этой задачи будет иметь такой вид:

$\text{максимизировать} \; \sum_k c_k x_k$ (3.1)

при ограничени

ях

$\begin{align*}\sum_k a_{ik} x_k \leq b_i , \quad i = 1, 2, . , m.\end{align*}$ (3.2)

Кроме ограничений на ресурсы (3.2) в эту модель можно ввести дополнительные ограничения на планируемый уровень выпуска продукции $x_j \geq x_{j0}$ , xi: xj: xk = bi: bj: bk для всех i, j, k и т.д.

Оптимальное распределение взаимозаменяемых ресурсов. Имеются m видов взаимозаменяемых ресурсов а1, а2,., аm, используемых при выполнении n различных работ (задач). Объемы работ, которые должны быть выполнены, составляют b1, b2,., bi, bn единиц. Заданы числа $\lambda_{ij}$ , указывающие, сколько единиц j-й работы можно получить из единицы і-го ресурса, а также Cij - затраты на производство j-й работы из единицы i-го ресурса. Требуется распределить ресурсы по работам таким образом, чтобы суммарная эффективность выполненных работ была максимальной (или суммарные затраты - минимальными).

Данная задача называется общей распределительной задачей. Количество единиц i-го ресурса, которое выделено на выполнение работ j-го вида, обозначим через xij.

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

$\text{минимизировать} \; \sum_{j=1}^n \sum_{i=1}^m c_{ij} x_{ij}$ (3.3)

при ограничениях

$\sum_{i=1}^m \lambda_{ij} x_{ij} \geq b_j, \quad j = 1, 2, ., n ,$ (3.4)

$\sum_{j=1}^n x_{ij} = a_i, \quad i=1,2,.,m.$ (3.5)

Ограничение (3.4) означает, что план всех работ должен быть выполнен полностью, а (3.5) означает, что ресурсы должны быть израсходованы целиком.

Примером этой задачи может быть задача о распределении самолетов по авиалиниям.

Задача о смесях. Имеется р компонентов, при сочетании которых в разных пропорциях получают разные смеси. Каждый компонент, а следовательно и смесь, содержит q веществ. Количество k-го вещества k = 1, 2,., q, входящее в состав единицы і-го компонента и в состав единицы смеси, обозначим через аik и аk соответственно.

Предположим, что аk зависит от аik линейно, то есть если смесь состоит из x1 единиц первого компонента, x2 - единицу второго компонента и т.д., то

$a_k = \sum_i a_{ik} x_i .$

Задано р величин Ci, характеризующих стоимость, массу или калорийность единицы i-го компонента, и q величин bk, указывающих минимально необходимое процентное содержание k-го вещества в смеси. Обозначим через x1, x2,.,xр значение компонента р-го вида, входящего в состав смеси.

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

$\text{минимизировать} \; \sum_{i=1}^p c_i x_i$ (3.6)

при ограничении

$\sum_{i=1}^p a_{ik} x_i \geq b_k , \quad k=1,2,.,q ,$ (3.7)

$\sum_{i=1}^p x_i =1$

Ограничение (3.7) означает, что процентное содержание k-го вещества в единице смеси должно быть не меньше bk.

К этой же модели принадлежит также задача определения оптимального рациона кормления скота.

4. Геометрический метод решение задач ЛП

Задача 1. При откорме каждое животное должно получить не менее 14 ед.питательного вещества S1, не менее 15 ед. вещества S2 и не менее 10 вещества S3. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 килограмме каждого вида корма и стоимость одного килограмма корма дана в таблице 1.

Таблица 1

Питательные вещества	Количество единиц питательных веществ в 1 кг. корма
Питательные вещества	корм 1	корм 2
S1	1	2
S2	1	3
S3	2	1
Стоимость 1 кг. корма	3	7

Составить рацион минимальной стоимости.

Решение:

X1 + 2X2 ≥ 14

X1 + 3X2 ≥ 15

2X1 + X2 ≥ 10

X1, X2 ≥ 0

3X1 + 7 X2 → min

X1 + 2X2 = 14

X1 + 3X2 =15

2X1 + X2 = 10

5. Симплексный метод решения задач ЛП

Задача 2. Для изготовления 4-ёх видов продукции P1, P2, P3, P4 используют два вида сырья: S1 и S2. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2.

Таблица 2.

Вид сырья	Запас сырья	Количество единиц сырья, идущих на изготовление единицы продукции
Вид сырья	Запас сырья	P1	P2	P3	P4
S1	3	1	1	1	2
S2	7	1	2	3	1
Прибыль от единицы продукции		9	14	15	10

Скачать реферат

Страница: 1 2 3 4 5 6 7

Линейное программирование как метод оптимизации

Другие рефераты на тему «Экономико-математическое моделирование»:

Поиск рефератов

Последние рефераты раздела

document.write('<p class="otherfont" style="float:right; color:#222222; text-align:center;">Страница <br /><big style="font-size:18px;"><b>3</b></big></p>'); Линейное программирование как метод оптимизации

Другие рефераты на тему «Экономико-математическое моделирование»:

Поиск рефератов

Последние рефераты раздела

Линейное программирование как метод оптимизации