Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Конспекты по методам оптимизации тема 2.doc
Скачиваний:
52
Добавлен:
13.02.2016
Размер:
328.19 Кб
Скачать

  1. 2. Основы линейного программирования

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

      1. 2.1.1. Математическая формулировка задачи линейного программирования

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

Математически задача линейного программирования ставится следующим образом: ищется максимум линейной формы (функции цели)

L

(2.1)

= c1x1 + c2x2 + ... + cnxn =

при условиях

ai1x1 + ai2x2 + ... + ainxn ≤ bi, i = 1, 2, ..., m; j = 1,2, …, n,

или

–ai1x1 – ai2x2 – ... – ainxn + bi  0.

Словесно задачу линейного программирования можно сформулировать так: требуется найти максимум линейной формы от n переменных при m ограничениях в виде неравенств или равенств. Нетрудно убедиться, что всегда можно говорить только о равенствах, так как введением дополнительных переменных xn+υ (υ = 1, ..., p ≤ m) неравенства всегда можно свести к равенствам. Так, ограничение

a

(2.2)

i1x1 + ai2x2 + ... + ainxn ≤ bi

м

(2.3)

ожно свести к равенству, добавив переменную xn+1:

ai1x1 + ai2x2 + ... + ainxn + xn+1 = bi.

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

L = c1x1 + c2x2 + ... + cnxn

при условии выполнения m равенств

ai1x1 + ai2x2 + ... + ainxn = bi, i = 1, 2, ..., m

и n неравенств xj, j = 1,2, …, n.

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

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

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

В трех месторождениях добывается определенное количество угля. Имеются три пункта потребления угля. Известны расстояния между пунктами добычи и потребления и стоимость перевозок 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 целочисленные. Поэтому ее можно отнести к задачам целочисленного линейного программирования, которые решаются различными способами, в том числе и с помощью динамического программирования.