4. Задача о составлении производственной программы и ее экономическая модель.

Общая задача линейного программирования:

f (х₁, х₂…х_n) =

≤b_i , I =

_≥b_i ; i=

x_j ≥ 0, j=1,e

x_{j –} произв. знака.

j=e+1,n

Любой набор значений переменных называется планом в задаче линейного программирования.

План, удовлетворяющий всем ограничениям, называется допустимым планом.

Множество допустимых планов обуславливается Ώ омега

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

Х*=(Х1*,Х2*…Хn*)

Значение целевой функции на оптимальном плане называется оптимальным планом.

f*=f(х*)

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

5

Задачи о составлении смеси

Исторически задача о составлении смеси (диеты, рациона) является одной

из первых ЗЛП. Ниже рассмотрено построение экономико-математических мо-

делей для нескольких задач, относящихся к данному классу [9, 16]. Цены, зара-

ботная плата и некоторые другие количественные величины, представленные в

задачах, которые приведены ниже, выбраны достаточно условно и не отражают

их нынешнего фактического состояния.

Задача № 1. Металлургическому комбинату требуется уголь с содер-

жанием фосфора не более 0,03 % и с долей зольных примесей не более 3,25 %.

Комбинат закупает три сорта угля, условно обозначенных A, B и С, с извест-

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

A, B и C, чтобы полученная смесь удовлетворяла ограничениям на содержание

примесей и имела минимальную цену?

Содержание примесей и цена каждого сорта угля приведены в табл. 2.

Таблица 2

Содержание, %

Сорт угля Фосфора Золы

Цена

1 т, р.

A 0,06 2,0 30

B 0,04 4,0 30

C 0,02 3,0 45

Решение. Построим экономико-математическую модель задачи. Обозна-

чим x1 - количество угля сорта A в тонне смеси, x2 - количество угля сорта B в

тонне смеси, x3 - количество угля сорта С в тонне смеси.

Стоимость 1 т смеси (целевая функция) с учетом введенных обозначений

и данных графы «Цена 1 т, р.» запишется в следующем виде:

1 2 3 Z = 30x + 30x + 45x .

Ограничение на содержание фосфора в смеси запишется в виде

0,06 0,04 0,02 0,03 x

1 + x

2 + x

3 £ (%).

Ограничение на содержание зольных примесей в смеси запишется в виде

6

5.3 Задача о раскрое материалов.

Сущность задачи об оптимальном раскрое состоит в разработке таких

техно­логически допустимых планов раскроя, при которых полу­чается

необходимый комплект заготовок, а отходы (по длине, площади, объему, массе

или стоимости) сводятся к минимуму. Рассмотрим простейшую модель раскроя по

одному измерению. Более сложные постановки ведут к задачам целочисленного

программирования.