Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

Транспортная задача

В трех месторождениях добывается определенное количество угля. Имеются три пункта потребления угля. Известны расстояния между пунктами добычи и потребления и стоимость перевозок cij (i = 1, 2, 3; j = 1, 2, 3). Необходимо так определить девять чисел xij, означающих количество грузов, перевозимых из пункта добычи в пункт потребления, чтобы суммарная стоимость перевозок была минимальна:

L = ∑cijxij → min

при условиях

x1j + x2j + x3j = bj, j = 1, 2, 3,

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

xi1 + xi2 + xi3 = ai, i = 1, 2, 3,

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

хотя это ограничение непринципиально.

Задача о рациональном питании

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

Предположим, имеется n различных продуктов калорийностью a1j (j = 1, 2,..., n), равной числу калорий в единице массы. В единице массы j-го продукта содержится a2j жиров, a3j белков, a4j углеводов. Обозначим через b1, b2, b3, b4 потребность организма в энергии, жирах, белках и углеводах, соответственно. Тогда при правильном питании должны выполняться следующие соотношения:

a11x1 + a12x2 +... + a1nxn ³ b1;

a21x1 + a22x2 +... + a2nxn ≤ b2;

a31x1 + a32x2 +... + a3nxn ≤ b3;

a41x1 + a42x2 +... + a4nxn ≤ b4,

где xj ³ 0 – количество потребления j-го продукта.

Если ввести требование экономного расходования средств, то это эквивалентно критерию

L = → min.

Если поменять знаки b1, a1j (j = 1, 2,..., n), то первое неравенство запишется в виде

–a11x1 – a12x2 –... – a1nxn ≤ –b1.

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

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

Предприятие имеет определенное количество ресурсов: рабочую силу, сырье, оборудование и т.д. Для простоты будем считать, что число ресурсов равно трем, и каждого ресурса имеется b1, b2, b3, условных единиц. Предприятие выпускает два вида товаров. Для производства единицы каждого товара затрачивается аij ресурсов. Известна стоимость сi единицы каждого товара. Требуется при данных ресурсах выпустить такую комбинацию товаров x1 и x2, чтобы доход предприятия L был максимален. При линейной зависимости стоимости продукции от количества продукции задача записывается в виде

L = c1x1 + c2x2 → max;

ai1x1 + ai2x2 ≤ bi; i = 1, 2, 3; xj ³ 0

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

Задача о загрузке транспорта

Пусть имеется транспортная единица грузоподъемностью b, которую необходимо загрузить различными предметами xj в разных количествах, причем cj – стоимость; wj – вес отдельного предмета j-го типа. Например, загружаются автомобили. Требуется определить оптимальную загрузку так, чтобы стоимость перевозимого груза была минимальной.

Очевидно, что стоимость всего перевозимого груза задается формулой

Необходимо найти такие целые числа xj (j = 1, 2,..., n), при которых эта линейная форма приняла бы максимальное значение при условиях

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





Дата публикования: 2014-11-28; Прочитано: 838 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...