Примеры задач линейного программирования

1. Задача об использовании ресурсов (планирование производ­ства). Для изготовления двух видов продукции P ₁ и P ₂ исполь­зуют четыре вида ресурсов S ₁, S ₂, S ₃ и S₄ Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление еди­ницы продукции, даны в табл. 1.1 (цифры условные):

Таблица 1.1

Вид продукции   Вид ресурса	P 1	P 2	Запасы ресурсов
S 1 S 1 S 3 S 4

Прибыль, получаемая от единицы продукции P ₁ и Р ₂, соот­ветственно 2 и 3 руб.

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

Составим экономико-математическую модель задачи.

Обозначим x ₁, x ₂ — число единиц продукции соответственно P ₁ и Р ₂ запланированных к производству. Для их изготовле­ния потребуется (см. табл. 1.1) единиц ресурса S ₁, единиц ресурса S ₃ единиц ресурса S ₃ и 3 x ₁ единиц ресурса S _4. Так как потребление ресурсов S ₁, S ₂, S ₃ и S ₄ не должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запа­сами выразится системой неравенств:

(1.1)

По смыслу задачи переменные (1.2)

Суммарная прибыль F составит 2 х ₁ руб. от реализации про­дукции P ₁ и 3 x ₂ руб. от реализации продукции Р ₂, т.е. . (1.3)

Итак, экономико-математическая модель задачи примет вид: найти такой план выпуска продукции X = (х ₁, x ₂), удовлетво­ряющий системе (1.1) и условию (1.2), при котором функция (1.3) принимает максимальное значение.

Задачу легко обобщить на случай выпуска n видов продук­ции с использованием m видов ресурсов.

Обозначим x _j (j = 1, 2,..., n) — число единиц продукции P _j, запланированной к производству; b ₁ (i = 1, 2,..., m) -- запас ресурса S _i; a_ij — число единиц ресурса S ₁, затрачиваемого на изготовление единицы продукции P_j (числа a_ij часто называют технологическими коэффициентами); c_j — прибыль от реализа­ции единицы продукции P_j.

Тогда экономико-математическая модель задачи об исполь­зовании ресурсов в общей постановке примет вид: найти такой план выпуска продукции, удовлетворяющий системе

(1.4)

и условию , (1.5)

при котором функция (1.6) принимает максимальное значение.

2. Задача составления рациона (задача о диете, задача о сме­сях). Имеется два вида корма I и II, содержащие питательные вещества (витамины) S ₁, S ₂ и S ₃. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходи­мый минимум питательных веществ приведены в табл. 1.2 (цифры условные). Стоимость 1 кг корма I и II соответственно 4 и 6 руб.

Таблица 1.2

Питательное вещество (витамин)	Необходимый минимум питательных веществ	Число единиц питательных веществ в 1 кг корма
I	II
S 1 S 1 S 3

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

Составим экономико-математическую модель задачи.

Обозначим х ₁, х ₂ — количество кормов I и II, входящих в дневной рацион. Тогда этот рацион будет включать (см. табл. 1.2) единиц питательного вещества S ₁, единиц вещества S ₂ и единиц питательного веще­ства S₃.Так как содержание питательных веществ S ₁ S ₂ и S ₃ в рационе должно быть не менее соответственно 9, 8 и 12 еди­ниц, то получим систему неравенств:

(1.7)

Кроме того переменные (1.8)

Общая стоимость рациона составит (в руб.) . (1.9)

Итак, экономико-математическая модель задачи: составить дневной рацион X = (х ₁, х ₂), удовлетворяющий системе (1.7) и условию (1.8), при котором функция (1.9) принимает мини­мальное значение.

Для формулировки задачи в общей постановке обозначим: x_j (j = 1, 2,..., n) - число единиц корма n -го вида; , - необходимый минимум содержания в рационе питательного вещества S_ij, a_ij — число единиц питательного вещества S ₁ в единице корма j -го вида; С_j — стоимость едини­цы корма j -го вида. Тогда экономико-математическая модель задачи примет вид:

Найти такой рацион X = (х ₁, х ₂,…, x_n), удовлетворяющий системе

(1.10)

и условию , (1.11)

при котором функция (1.12) принимает минимальное значение.

3. Задача об использовании мощностей (о загрузке оборудова­ния). Предприятию задан план производства продукции по времени и номенклатуре: требуется за время Т выпустить п ₁, п ₂,..., n_k единиц продукции P ₁, P ₂,..., P_k Продукция произ­водится на станках S ₁, S ₂,..., Sm. Для каждого станка извест­ны производительность а_ij (т.е. число единиц продукции P_j; которое можно произвести на станке S_i) и затраты b_ij на из­готовление продукции P_j на станке S_i в единицу времени.

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

Составим экономикj-математическую модель задачи.

Обозначим х_ij — время, в течение которого станок S_i будет занят изготовлением продукции Pj (i = 1, 2,..., m;j = 1, 2,..., k).

Так как время работы каждого станка ограничено и не пре­вышает T, то справедливы неравенства:

(1.13)

Для выполнения плана выпуска по номенклатуре необходимо, чтобы выполнялись следующие равенства:

(1.14)

Кроме того, (1.15)

Затраты на производство всей продукции выразятся функцией (1.16)

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

найти такое решение Х = (х ₁₁, х ₁₂, …, x_mk), удовлетворяющее системам (1.13) и (1.14) и условию (1.15), при котором функция (1.16) принимает минимальное значение.

4. Задача о раскрое материалов. На раскрой (распил, обра­ботку) поступает материал одного образца в количестве а еди­ниц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональных числам b ₁, b ₂..., b_l (условие комплектности). Каждая единица материала может быть раскроена п различными способами, причем использова­ние i -го способа (i = 1, 2,..., n) дает а_ik единиц k -го изделия (k = 1, 2,..., l).

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

Составим экономико-математическую модель задачи.

Обозначим х_i — число единиц материала, раскраиваемых i -м способом, и х — число изготовляемых комплектов изделий. Так как общее количество материала равно сумме его еди­ниц, раскраиваемых различными способами, то . (1.17)

Требование комплектности выразится уравнениями . (1.18)

Очевидно, что . (1.19)

Экономико-математическая модель примет вид:

найти такое решение Х = (х ₁, х ₂, …, x_n), удовлетворяющее системе уравне­ний (1.17) — (1.18) и условию (1.19), при котором функция F = х принимает максимальное значение.

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

Решение. Прежде всего определим всевозможные способы распила бревен, указав соответствующее число получаемых при этом брусьев (табл. 1.3):

Таблица 1.3

Способ распила i	Число получаемых брусьев длиной в м:
1,2	3,0	5,0
	- -	- -	- - -

Обозначим: — число бревен, распиленных i -м способом (i =1,2,3,4); х - число комплектов брусьев.

Учитывая, что все бревна должны быть распилены, а числа брусьев каждого размера должны удовлетворять условию комп­лектности, экономико-математическая модель задачи примет вид:

F = х max при ограничениях

(i = 1, 2, 3, 4).

Задачу о раскрое легко обобщить на случай m раскраиваемых материалов.

Пусть каждая единица j -го материала (j = 1, 2,..., m) может быть раскроена п различными способами, причем использова­ние i -го способа (i = 1, 2,..., n) дает а_ijk единиц k -то изделия (k = 1, 2,..., l» а запас j -го материала равен a_j единиц.

Обозначим x_ij — число единиц j -го материала, раскраиваемо­го i -м способом.

Экономико-математическая модель задачи о раскрое в об­щей постановке примет вид: найти такое решение Х = (х ₁₁, х ₁₂, …, x_nm)удовлетворяющее системе

и условию , при котором функция F = х принимает мак­симальное значение. 5.