Задач линейного программирования

1.Задача об использовании ресурсов (планировании производства).

Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

Введем следующие обозначения:

х_j – число единиц продукции P_j , запланированной к производству,

b_i – запас ресурса S_i ,

a_ij – число единиц ресурса S_i , затрачиваемое на единицу продукции P_j (эти числа называют технологическими коэффициентами),

c_j – прибыль от реализации продукции P_j .

Тогда модель задачи будет иметь вид:

Рассмотрим задачу с конкретными данными.

Прибыль от реализации единицы продукции Р₁ составляет 2 рубля, а от единицы продукции Р₂ – 3 рубля. Данные о запасах ресурсов и количестве ресурсов, необходимых для изготовления единицы продукции, сведены в следующую таблицу.

Таблица 1.1

Данные задачи об использовании ресурсов

Экономико-математическая модель данной задачи будет иметь вид:

2.Задача составления рациона (о диете, о смесях), или технологическая задача.

Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела.

Введем обозначения:

x_j – число единиц корма j-го вида;

b_i – необходимый минимум содержания в рационе питательного вещества S_i ;

a_ij – число единиц питательного вещества S_i в единице корма j-го вида;

c_j – стоимость единицы корма j-го вида.

Тогда экономико-математическая модель задачи запишется следующим образом:

Рассмотрим задачу с конкретными данными.

Стоимость 1 кг корма вида I – 4 рубля, а вида II – 6 рублей. Используя данные таблицы, необходимо составить такой рацион питания, чтобы стоимость его была минимальной и содержание каждого вида питательных веществ было не менее установленного предела.

Таблица 1.2

Данные задачи о рационе питания

Модель задачи будет иметь вид:

3.Задача об использовании мощностей (задача о загрузке оборудования).

Предприятию задан план производства продукции по времени и номенклатуре: требуется за время Т выпустить n₁, n₂,……n_k единиц продукции P₁, P₂,……P_к. Продукция производится на станках S₁, S₂, …….S_m. Для каждого станка известны производительность a_ij (то есть число единиц продукции P_j , которое можно произвести на станке S_i в единицу времени) и затраты b_ij на изготовление продукции P_j на станке S_i в единицу времени.

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

Экономико-математическая модель задачи.

Обозначим x_ij – время, в течение которого станок S_i будет занят изготовлением продукции P_j . Так как время работы каждого станка ограничено и не превышает Т, то справедливы следующие неравенства:

4.Технологическая задача (о раскрое материала).

Найти план раскроя, обеспечивающий максимальное число комплектов.

Для изготовления брусьев длиной 1,2 м, 3 м и 5 м в соотношении 2:1:3 на распил поступает 195 бревен длиной 6 м. Определить план распила, обеспечивающий максимальное число комплектов.

Составим модель задачи.

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

Таблица 1.3

Способы распила бревен

Через х_i обозначим число бревен распиливаемых i-м способом, , а через х – число комплектов брусьев.

Тогда экономико-математическая модель задачи будет иметь вид:

Задания для самостоятельной работы.