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

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

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

Несколько слов о самом термине линейное программирование. Он требует правильного понимания. В данном случае программирование - это, конечно, не составление программ для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий.

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

Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:

• задача об оптимальном использовании ресурсов при производственном планировании;

• задача о смесях (планирование состава продукции);

• задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

• транспортные задачи (анализ размещения предприятия, перемещение грузов).

Линейное программирование – наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

• математические модели большого числа экономических задач линейны относительно искомых переменных;

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

• многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.

В общем виде модель записывается следующим образом:

• целевая функция: ; (1)

• ограничения: (2)

• требование неотрицательности: , . (3)

При этом коэффициенты , , , , – заданные постоянные величины.

Задача состоит в нахождении оптимального значения целевой функции (1) при соблюдении ограничений (2) и (3).

Систему ограничений (2) называют функциональными ограничениями задачи, а ограничения (3) – прямыми.

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

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

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

Общий смысл задач этого класса сводится к следующему.

Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, , , …, условных единиц.

Известны также технологические коэффициенты , которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида ( , ).

Прибыль, получаемая предприятием при реализации изделия j-го вида, равна .

В планируемом периоде значения величин , , остаются постоянными.

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

Далее приведем простой пример задачи такого класса.

Пример 1. Предприятие производит продукцию двух видов (A и Б), используя при изготовлении этой продукции ресурсы трех видов (первого, второго и третьего). Чтобы произвести одну единицу продукции A, нужно затратить по 1 единице первого и второго ресурсов и 2 единицы третьего ресурса. Для производства единицы продукции Б требуется 2 единицы первого ресурса и 1 единица второго ресурса. Запасы ресурсов у предприятия ограничены: на складах есть 90 единиц первого ресурса, 50 единиц второго и 80 единиц третьего ресурса. Рыночная цена продукции A составляет 800 руб., а цена продукции Б равна 1000 руб. Сколько продукции следует произвести, чтобы получить наибольшую выручку?

Условия задач указанного класса часто представляют в табличной форме (таблица 1).

Таблица 1 - Исходные данные задачи об использовании производственных ресурсов

Производственные ресурсы	Вид изделия		Запасы ресурсов
	Изделие А	Изделие Б
I тип	1	3		90
II тип	1	1		50
III тип	-	2		80
Рыночная цена 1 единицы продукции, ден.ед.	800	1000

По данному условию сформулируем задачу линейного программирования.

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

Относительно величин и можно сказать следующее. Во-первых, они должны быть неотрицательными — отрицательный план производства продукции не имеет экономического смысла. Во-вторых, общие расходы ресурсов при производстве единиц продукции A и единиц продукции Б не должны превысить запасы этих ресурсов.

Вычислим суммарный расход первого ресурса. На производство единицы продукции A тратится 1 единица первого ресурса, а всего продукции A производится единиц, значит, на производство всей продукции A будет затрачено единиц первого ресурса. Аналогично, на производство единицы продукции Б тратится 3 единицы первого ресурса, а всего продукции Б производится единиц, значит, на производство всей продукции Б будет затрачено единиц первого ресурса. Суммарный расход первого ресурса на производство всей продукции (и A, и Б) составит единиц. А в запасе есть всего 90 единиц этого ресурса. Значит, должно выполняться ограничение: . Добавляя аналогичные ограничения по второму и третьему ресурсам, приходим окончательно к следующей задаче.

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

при ограничениях по ресурсам

и ограничениях неотрицательности

, .

2. Задача о смесях (планирование состава продукции).

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

Пример 2. На птицеферме употребляются два вида кормов - I и II. В единице массы корма I содержатся единица вещества A, единица вещества В и единица вещества С. В единице массы корма II содержатся четыре единицы вещества А, две единицы вещества В и не содержится вещество C. В дневной рацион каждой птицы надо включить не менее единицы вещества А, не менее четырех единиц вещества В и не менее единицы вещества С. Цена единицы массы корма I составляет 3 рубля, корма II - 2 рубля.

Необходимо составить ежедневный рацион кормления птицы так, чтобы обеспечить наиболее дешевый рацион.

Представим условие задачи в таблице 2.

Таблица 2 - Исходные данные задачи о смесях

питательные вещества	содержание веществ в единице массы корма, ед.		требуемое количество в смеси, ед.
	корм I	корм II
А	1	4	1
В	1	2	4
С	1	-	1
цена единицы массы корма, р	2	4

Cформулируем задачу линейного программирования.

Обозначим количество корма I в дневном рационе птицы,  количество корма II в дневном рационе птицы.

Задача линейного программирования примет вид:

при ограничениях

и ограничениях неотрицательности , .

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

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

Пример 3. Три поставщика одного и того же продукта располагают в планируемый период следующими его запасами: первый – 120 условных единиц, второй – 100 условных единиц, третий – 80 условных единиц. Этот продукт должен быть перевезен к трем потребителям, потребности которых равны 90, 90 и 120 условных единиц, соответственно.

Обычно начальные условия транспортной задачи записывают в так называемую транспортную таблицу (таблица 3). В ячейках таблицы в левом верхнем углу записывают показатели затрат (расходы по доставке единицы продукта между соответствующими пунктами), под диагональю каждой ячейки размещается величина поставки  (т.е. – количество единиц груза, которое будет перевезено от i-го поставщика j-му потребителю).

Таблица 3 - Исходные данные транспортной задачи

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

Сформулируем ЗЛП:

при ограничениях:

, , .