Бщая постановка задач линейного программирования.

инейное программирование.

одели математического программирования.

бщая постановка задач линейного программирования.

Оптимизационная задача – это экономико-математическая задача, которая состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений.

Для того, чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение.

Если целевая функция в задаче является функцией n - переменной, то методы решения называются методами математического программирования.

Линейное программирование – это раздел математики ориентируемый на нахождении экстремума в задачах, которые описываются линейными уравнениями.

Задачей линейного программирования называется задачей исследования операций, математическая модель которой имеет вид:

F(x) = бщая постановка задач линейного программирования. - student2.ru cjxj=c1x1+c2x2+…+cnxn → min (max)

Линейная функция (целевая функция) стремится либо к min, либо к max.

бщая постановка задач линейного программирования. - student2.ru aijxj ≤ bj (или ≥b), i = бщая постановка задач линейного программирования. - student2.ru = 1,2…m

бщая постановка задач линейного программирования. - student2.ru

Все переменные должны быть xj ≥ 0, j = бщая постановка задач линейного программирования. - student2.ru

Название системы: система организации задачи линейного программирования (ЗЛП).

Если математическая модель ЗЛП имеет вид

бщая постановка задач линейного программирования. - student2.ru

xj ≥ 0, bi ≥ 0, то ЗЛП представлена в канонической форме.

ПРАВИЛО приведения ЗЛП к канонической форме:

1. Если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

2. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на минус единицу;

3. Если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства.

Пример: Привести ЗЛП к канонической форме.

Fmax = 3x1 + x2 + 5x3

бщая постановка задач линейного программирования. - student2.ru

F = -3x1 - x2 - 5x3→ min

бщая постановка задач линейного программирования. - student2.ru

Всякое не отрицательное решение системы ограничений называется допустимым.

Допустимое решение, дающее минимум функции F называется оптимальным.

Оптимальное решение не всегда будет единственным.

Рассмотрим процесс математических моделей ЗЛП на примерах:

1. Задача о диете.

Из имеющихся в распоряжении видов пищи нужно составить такую диету, которая с одной стороны обеспечивала бы минимум потребностей организма в питательных веществах (белках, жирах, витаминов и т.д.) и вместе с тем требовала бы наименьших затрат.

Рассмотрим простую математическую модель этой задачи.

Пусть имеются два вида продуктов Р1 и Р2 содержащих питательные вещества А, В, С. S1 и S2 стоимость 1 кг продукта Р1 и Р2 соответственно. В таблице указано сколько питательного вещества содержащихся в 1 кг продукта Р1 и Р2 . Требуется рассчитать количество продуктов P1 и P2, так чтобы обеспечить необходимое количество питательных веществ при минимальных затратах на продуктах.

Продукт А В С
P1 А1 В1 С1
P2 А2 В2 С2
Ежесут. требн. А В С

x1 – количество продукта P1

x2 – количество продукта P2

x1 ≥ 0, x2 ≥ 0

F(x) = s1x1 + s2x2 → min

бщая постановка задач линейного программирования. - student2.ru

2. Задача о распространении ресурсов.

Предприятие имеет в своем распоряжении определенное количество ресурсов (сырье, оборудование и т.д.), из этих ресурсов выполняется определенное количество товаров.

Известно количество единиц каждого из ресурсов, используемых при производстве единицы каждого вида товара. Известен также доход, полученный предприятием от выпуска одной единицы товара. При этих условиях требуется выполнить такое количество товаров, чтобы доход их был максимальным.

Ресурсы Товары   Кол-во
  T1 T2 ресурсов
R1 A11 A12 B1
R2 A21 A22 B2
R3 A31 A32 B3

S1, S2 - стоимость T1 , T2

x1 – количество продукта T1

x2 – количество продукта T2

x1 ≥ 0, x2 ≥ 0

F(x) = s1x1 + s2x2 → max

бщая постановка задач линейного программирования. - student2.ru

Наши рекомендации