0

Линейное программирование

Курс лекций М.М. Цвиль

и образец решения типового расчёта

Ростов-на-Дону

1. Общая задача линейного программирования

1.1. Задачи математического и линейного программирования

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

1) выбор переменных задачи;

2) составление системы ограничений;

3) выбор целевой функции.

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

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

Целевой функцией называют функцию переменных задачи, экстремум которой требуется найти.

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

(1.1.1)

при системе ограничений на переменные

(1.1.2)

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

Математическое программирование включает в себя такие разделы как линейное, нелинейное и динамическое программирование. Если целевая функция (1.1.1) и система ограничений (1.1.2) линейны, то задача математического программирования называется задачей линейного программирования (ЛП).

Математическое программирование возникло в 30-е годы XX века. Линейное программирование началось с работы (1938 г.) ленинградского математика Л. В. Канторовича, в которой содержались постановка и метод решения задачи о выборе наилучшей производственной программы. Независимо линейное программирование начало развиваться и в США. В 1947 году американский учёный Дж. Данциг описал один из основных методов решения задач ЛП, получивший название «симплексный».

В общем случае задача ЛП может быть записана в виде:

, (1.1.3)

(1.1.4)

, , (1.1.5)

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

1.2. Математические модели простейших экономических задач

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

Для изготовления нескольких видов продукции , ,…, используют видов ресурсов , ,…, (например, различные материалы, электроэнергию и т.д.). Объём каждого вида ресурсов ограничен и известен: . Известно также количество каждого -го вида ресурса, расходуемого на производство единицы -го вида продукции. Кроме того, известна прибыль, получаемая от реализации единицы каждого вида продукции . Условие задачи можно представить в виде табл. 1.1.

Таблица 1.1

Вид ресурсов	Объём ресурсов
					. . . . . . . . .
. . .	. . .	. . .	. . .	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		. . .
Прибыль				. . . . . . . . .

Пусть количество каждого вида продукции, которое необходимо произвести. Для первого ресурса имеет место неравенство-ограничение

.

Аналогичные неравенства будут и для остальных видов ресурсов. Следует учитывать, что все значения , .

Общая прибыль, получаемая от реализации всей продукции может быть представлена как функция , для которой нужно найти максимальное значение. Таким образом, математическая модель задачи использования ресурсов запишется в виде:

,

(1.2.1)

, .

Пример 1.1. Фирма производит две модели А и В сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3 досок, а для изделия модели В – 4 . Фирма может получить от своих поставщиков до 1700 досок в неделю. Для каждого изделия модели А требуется 12 мин. машинного времени, а для изделия модели В – 30 мин. В неделю можно использовать 160 ч машинного времени. Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В – 4 дол. прибыли?

Составим математическую модель. Пусть количество выпущенных за неделю полок модели А, а количество выпущенных за неделю полок модели В. Еженедельная прибыль выражается целевой функцией . Ограничение, наложенное на объём используемого сырья, выражается неравенством , а на количество машинного времени – . Задача состоит в том, чтобы найти наилучшие значения и . Очевидно, наилучшими для данной задачи являются такие значения, которые максимизируют еженедельную прибыль.

Итак, нужно максимизировать функцию при следующей системе ограничений:

Задача о составлении рациона питания

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

Пусть имеются различных кормов , ,…, и перечень питательных веществ , ,…, . Обозначим через содержание -го питательного вещества в единице -го корма, а через минимальную суточную потребность животного в -м питательном веществе. Условие задачи можно представить в виде табл. 1.2.

Таблица 1.2

Питат. Вещество					Суточная потребность
			. . . . . . . . .
. . .	. . .	. . .	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . .	. . .
Стоимость 1 кг корма			. . . . . . . . .

Составим математическую модель. Через обозначим количество каждого вида корма в ежедневном рационе, . Очевидно, что . Для первого вида питательного вещества неравенство-ограничение примет вид

.

Аналогично запишутся неравенства для остальных питательных веществ. Общие затраты на весь рацион питания

.

Эту функцию надо минимизировать.

Итак, математическая модель задачи составления рациона питания имеет вид:

(1.2.2)

, .

Пример 1.2. При откорме каждое животное ежедневно должно получать не менее 9 ед. питательного вещества I вида, не менее 8 ед. вещества II вида и не менее 12 ед. вещества III вида. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 кг каждого корма соответственно равно 3,1,1 и 1,2,6. Стоимость 1 кг корма I вида – 4 руб., II вида – 6 руб. Необходимо составить дневной рацион нужной питательности, причём затраты на него должны быть минимальными. Составить математическую модель этой задачи самостоятельно.

Задача оптимизации выпуска дорожной продукции

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

Таблица 1.3

Компоненты смеси	Запасы сырья	Содержание компонентов /в 100т/
		А	В
Щебень	1000	58	21
Песок	900	35	60
М.П.	245	7	19
Битум	110	5,5	5,2
Прибыль		29 ден. ед.	31 ден. ед.

Заметим, что при определении долевого содержания 100т каждой cмеси битум берётся сверх 100%.

В задаче требуется составить план производства, обеспечивающий наибольшую прибыль при реализации продукции. То есть надо указать такие числа и сотен тонн продукции и соответственно , чтобы суммарная прибыль /ден. ед./ принимала бы наибольшее

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

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

неравенств-ограничений:

(1.2.3)

.

Значения и , удовлетворяющие (1.2.3), будем называть допустимым планом (решением).

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

максимизируют линейную функцию .