Лекция: Математические модели типовых задач линейного программирования.

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

1. Задача о загрузке оборудования. Предприятие располагает N1 станками типа 1 и N2 станками типа 2. Станки могут производить четыре вида изделий: T1, T2, T3, T4.

Каждый тип станка может производить любой из видов изделий, но в неодинаковом количестве. Станок типа 1 производит в смену a11 изделий Т1, а12 изделий Т2, а13 изделий Т3, а14 изделий Т4. Соответствующие данные для станка типа 2 будут а21, а22, а23, а24. Производительности станков при производстве каждого вида изделий заданы табл. 2.1. Предприятию предписан план, согласно которому он обязан произвести за месяц: не менее b1 изделий Т1, не менее b2 изделий Т2, не менее b3 изделий Т3 и не менее b4 изделий Т4, т.е. плановое задание выражается числами b1, b2, b3, b4 (см. табл. 2.1).

 

Таблица 2.1

Тип станка Вид изделия
T1 T2 T3 T4
a11 a12 a13 a14
а21 а22 а23 а24
задание b1 b2 b3 b4

 

Каждое изделие Т1 приносит предприятию доход с1, Т2 – доход с2, Т3 – доход с3, Т4 – доход с4.

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

Запишем условия задачи математически. Обозначим х11 – число станков типа 1, занятых производством изделий Т1, х12 – число станков типа 1, занятых производством изделий Т2, и вообще хij – число станков типа i, занятых производством Tj. Первый индекс соответствует типу станка, второй – виду изделия (i = 1, 2, j = 1, 2, 3, 4).

Таким образом возникают восемь переменных – элементов решения:

 

х11, х12, х13, х14;

х21, х22, х23, х24, (2.3)

 

которые мы должны выбрать так, чтобы прибыль была максимальна. Запишем формулу для вычисления этой прибыли. Каждое изделие Т1 приносит прибыль с1; х11 изделий Т1 принесут прибыль с1х11; всего Т1 принесет прибыли с1(х11+х21) и т.д. Общая прибыль будет равна:

Z = с1(х11+х21)+с2(х12+х22)+с3(х13+х23)+с4(х14+х24). (2.4)

 

Требуется выбрать такие неотрицательные значения переменных (2.3), чтобы целевая функция от них (2.4) обращалась в максимум. При этом должны выполняться следующие ограничительные условия:

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

х11+х12+х13+х14 ≤ N1;

х21+х22+х23+х24 ≤ N2. (2.5)

 

2) Задания по ассортименту должны быть выполнены (или перевыполнены). С учетом табл. 2.1 эти условия запишутся в виде неравенств:


а11х11+а21х21 ≥ b1,

a12x12+a22x22 ≥ b2,

a13x13+a23x23 ≥ b3, (2.6)

a14x14+a24x24 ≥ b4.

 

Таким образом, сформулирована задача:

Выбрать такие неотрицательные значения переменных х11, х12,…, х24, удовлетворяющие линейным неравенствам (2.5) и (2.6), при которых линейная функция этих переменных (2.4) обращалась бы в максимум.

2. Задача о распределении ресурсов. Имеются какие-то ресурсы (сырье, рабочая сила, оборудование): R1, R2, …, Rm в количествах соответственно b1, b2, …, bm единиц. С помощью этих ресурсов могут производиться товары: Т1, Т2,…, Тn. Для производства одной единицы товара Tj необходимо aij единиц ресурса Ri (i = 1, 2,…, m; j = 1, 2,…, n). Каждая единица ресурса Ri стоит di рублей (i = 1, 2,…, m). Каждая единица товара Tj может быть реализована по цене cj (j = 1, 2,…, n).

По каждому виду товара количество произведенных единиц ограничивается спросом: известно, что рынок не может заказать более, чем kj единиц товара Tj (j = 1, 2,…, n).

Определить: какое количество единиц какого товара надо произвести для того, чтобы получить максимальную прибыль?

Составим математическую модель задачи. Обозначим через х1, х2, …, хn количества товаров Т1, Т2, …, Тn, которые будут запланированы к производству. Условия спроса налагают на эти величины ограничения:

x1 ≤ k1; x2≤ k2; …, xn ≤ kn. (2.7)

Ресурсов должно хватить, отсюда возникают ограничения:

a11x1+a12x2+…+a1nxn ≤ b1;

a21x1+a22x2+…+a2nxn ≤ b2;

……………………………… (2.8)

am1x1+am2x2+…+amnxn ≤ bm.

 

Выразим прибыль Z в зависимости от элементов решения х1, х2,…, хn. Себестоимость sj единицы товара Tj равна:

sj = a1jd1 + a2jd2 +…+ amjdm.

Вычислив по этой формуле себестоимость единицы каждого товара, получим ряд значений s1, s2,…,sn.

Чистая прибыль qj, получаемая от реализации одной единицы товара Tj, равна разнице между ее продажной ценой cj и себестоимостью sj:

qj = cj – sj (j = 1, 2,…, n).

По этой формуле получаем чистые прибыли на единицу всех товаров q1, q2,…,qn. Общая чистая прибыль от реализации всех товаров составит

Z = q1x1 + q2x2 + … + qnxn (2.9)

Задача сводится к следующему:

Выбрать такие неотрицательные значения переменных х1, х2,…, хn, которые удовлетворяют линейным неравенствам (2.7), (2.8 ) и обращают в максимум линейную функцию этих переменных (2.9).

3. Задача о составлении смеси. Еще одним распространенным типом задач линейного программирования являются задачи составления смеси, например, задача составления смесей химических или нефтепродуктов, которые удовлетворяют определенным требованиям. Для простоты ее рассмотрения зададимся числовыми значениями исходных данных.

Требуется составить смесь, содержащую три химических вещества А, В, С. Известно, что составленная смесь должна содержать вещества А не менее 6 единиц, вещества В не менее 8 единиц, вещества С не менее 12 единиц. Вещества А, В, С содержатся в трех видах продуктов –I, II, III в концентрации, указанной в таблице 2.2:

 

Таблица 2.2

  Химические вещества
продукты А В С
I
II
III 1,5

 

Стоимость единицы продуктов I, II,III различна: единица продукта I стоит 2 рубля, единица II – 3 рубля, единица III – 2,5 рубля. Смесь надо составить так, чтобы стоимость используемых продуктов была наименьшей.

Построим математическую модель задачи составления смеси. Число единиц продукта I, входящего в смесь, обозначим через х1, продукта II – через х2, продукта III — через х3.

Составляемая смесь должна содержать вещество А, которое содержится во всех трех продуктах. На каждую единицу продукта I приходится 2 части концентрации вещества А. Следовательно, если использовано х1 единиц продукта I, то в составляемой смеси будет 2х1 частей вещества А. Если использовано х2 единиц продукта II, то в смеси будет 1х2 частей вещества А. Наконец, если использовано х3 единиц продукта III, то в смеси будет 3х3 частей вещества А. Так как общее количество вещества А в смеси должно быть не меньше 6, то

2х1 + х2 + 3х3 ≥ 6.

Рассуждая аналогично относительно концентрации веществ В и С, получаем неравенства:

х1 + 2х2 + 1,5х3 ≥ 8,

3х1 + 4х2 + 2х3 ≥ 12.

Стоимость смеси слагается из 2х1 руб. (стоимость использованного продукта I), 3х2 руб. (стоимость продукта II), 2,5х3 руб. (стоимость продукта III). Следовательно, общая стоимость смеси будет равна

2х1 + 3х2 + 2,5х3.

Из условия задачи следует, что число единиц используемых продуктов неотрицательно: х1≥0, х2≥0, х3≥0.

Таким образом, математическая модель задачи представлена системой линейных неравенств:

2х1 + х2 + 3х3 ≥ 6

х1 + х2 + 1,5х3 ≥ 8 (2.10)

3х1 + 4х2 + 2х3 ≥ 12

xi ≥ 0, i = 1,2,3,

на множестве решений которой надо найти наименьшее значение целевой функции

Z = 2х1 + 3х2 + 2,5х3. (2.11)

Заметим, что: 1) все ограничения системы (2.10) имеют вид неравенств вида ≥, 2) требуется минимизировать целевую функцию Z.

4. Задача о перевозках.Имеются m складов: С1, С2,.., Сm и n пунктов потребления: П1, П2,…, Пn. На складах имеются запасы товаров в количествах а1, а2,…, аm единиц. Пункты потребления подали заявки соответственно на b1, b2,…, bn единиц товара. Заявки выполнимы, т.е. сумма всех заявок не превосходит суммы всех имеющихся запасов:

Склады С1,…, Сm связаны с пунктами потребления П1,…, Пn какой-то сетью дорог с определенными тарифами на перевозки. Стоимость перевозки одной единицы товара со склада Ci в пункт Пj равна сij (i = 1,2,…,m; j = 1,2,…,n).

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

Обозначим через хij – количество единиц товара, направляемое со склада Сi в пункт Пi (если с этого склада в этот пункт товары не направляются, хij = 0).

Решение (план перевозок) состоит из mn чисел:

х11, х12,…, х1n;

х21, х22,…, х2n;

…………………

хm1, xm2,…, xmn,

образующих прямоугольную таблицу (матрицу). Требуется выбрать такие неотрицательные значения переменных хij (i = 1,2,…,m; j = 1,2,…,n), чтобы были выполнены следующие условия:

1. Емкость складов не должна быть превышена, т.е. общее количество товара, взятое с каждого склада, не должно превышать имеющихся на нем запасов:

х11+ х12+…+ х1n ≤ а1;

х21+ х22+…+ х2n ≤ а2; (2.12)

……………………….

хm1+ xm2+…+ xmn ≤ аm,

2. Заявки, поданные пунктами потребления, должны быть выполнены:

х11+ х21+…+ хm1 = b1;

х12+ х22+…+ хm2 = b2; (2.13)

……………………….

х1n+ x2n+…+ xmn = bn,

Общая стоимость перевозок Z будет равна

Z = c11x11+c12x12+…+c1nx1n+ (2.14)

+c21x21+c22x22+…+c2nx2n+

+…+cm1xm1+cm2xm2+…+cmnxmn,

Требуется так составить план перевозок, чтобы стоимость Z этих перевозок обратить в минимум.

Снова возникает задача, аналогичная рассмотренным ранее: выбрать неотрицательные значения переменных хij так, чтобы при выполнении условий (2.12), (2.13) целевая функция этих переменных (2.14) достигла минимума.

Особенность этой задачи, по сравнению с ранее рассмотренными, стоит в том, что не все ограничения, наложенные на переменные, являются линейными неравенствами; а именно, условия (2.13) записаны в виде линейных равенств.

Второе, более существенное, отличие рассматриваемой математической модели от предыдущих заключается в том, что здесь в системе ограничений коэффициенты при всех переменных равны единице. Задачи линейного программирования, математические описания которых представлены моделями данного вида, называются транспортными задачами линейного программирования. Для решения транспортной задачи линейного программирования разработан ряд методов, существенно более простых по сравнению с методами решения задач, математические модели которых были рассмотрены выше. К транспортным задачам линейного программирования относят многие не связанные с перевозками задачи, исходя из вида математических моделей.

 

еще рефераты
Еще работы по информатике