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

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

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

при наложении на переменные следующих условий:

Функция F называется целевой функцией, система – системой ограничений.

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

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

ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1. Задача использования сырья (задача планирования производства).

Для изготовления двух видов продукции и используют три вида сырья: , и . Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 10.1. Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.

Таблица 10.1

Виды сырья	Запасы сырья	Количество единиц сырья, затрачиваемых на изготовление единицы продукции
Прибыль от единицы продукции (в руб.)

Составим экономико-математическую модель (математическое описание исследуемого экономического процесса) задачи.

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

(10.1)

По смыслу задачи переменные , . (10.2)

Суммарная прибыль F(x) составит руб. от реализации продукции и руб. – от реализации продукции , т.е.

. (10.3)

Итак, экономико-математическая модель задачи: найти такой план выпуска продукции , удовлетворяющий системе (10.1) и условию (10.2), при котором функция (10.3) принимает максимальное значение.

Задачу легко обобщить на случай выпуска n видов продукции с использованием m видов сырья.

2. Задача составления рациона (задача о диете).

Имеется два вида корма I и II, содержащие питательные вещества (витамины) , и . Содержание количества единиц питательного вещества в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице 10.2.

Таблица 10.2

Питательные вещества	Необходимый минимум питательных веществ	Количество единиц питательного вещества в 1 кг корма
Корм I	Корм II
Стоимость 1 кг корма (в руб.)

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

Составим экономико-математическую модель задачи. Обозначим через и соответственно количество кормов I и II, входящих в дневной рацион. Принимая во внимание значения, приведенные в табл. 10.2, и условие, что дневной рацион удовлетворяет требуемой питательности только в случае, если количество единиц питательных веществ не меньше предусмотренного, получим систему ограничений

(10.4)

Кроме того, переменные

, . (10.5)

Общая стоимость рациона (в руб.) составит

. (10.6)

Итак, экономико-математическая модель задачи: составить дневной рацион , удовлетворяющий системе (10.4) и условию (10.5), при котором функция (10.6) принимает минимальное значение.

3. Задача о раскрое материалов.

На раскрой поступает материал одного образца в количестве a единиц. Требуется изготовить из него l разных комплектующих изделий в количествах пропорциональных числам , , …, (условие комплектности). Каждая единица материала может быть раскроена n различными способами, при этом использование i-го способа (i =1, 2, …, n) дает единиц k-го изделия (k = 1, 2, …, l). Требуется составить план раскроя, обеспечивающий максимальное количество комплектов.

Составим экономико-математическая модель задачи. Обозначим через количество единиц материала, раскраиваемых i-м способом, и x – количество изготавливаемых комплектов изделий.

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

(10.7)

Условие комплектности выразится уравнениями

(k = 1, 2, …, l) (10.8)

по смыслу задачи переменные

(i = 1, 2, …, n). (10.9)

Итак, экономико-математическая модель задачи: найти такое решение , удовлетворяющее системе уравнений (10.7) – (10.8) и условию (10.9), при котором функция F = x принимает максимальное значение.

неизвестных и свободных членов системы уравнений задачи.

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

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

План , при котором целевая функция принимает свое максимальное (минимальное) значение, называется оптимальным.

СВОЙСТВА РЕШЕНИЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

(10.15)

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

АХ = В, (10.16)

Х  0, (10.17)

где

, ,

Теорема 10.1. Множество всех планов задачи линейного программирования выпукло (если оно не пусто).

Доказательство.

Пусть и – два допустимых плана задачи (10.15)-(10.17). Тогда , и , .

Рассмотрим выпуклую линейную комбинацию , , и покажем, что Х также является планом задачи. Действительно,

,

т.е. Х удовлетворяет (10.16). Но так как , , , , то и , т.е. удовлетворяет и условию (10.17).

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

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

Доказательство. Предположим, что многогранник решений является ограниченным, имеющим конечное число угловых точек. Обозначим его через К. В К имеет вид многоугольника, изображенного на рисунке. Обозначим угловые точки К через , , …, , а оптимальный план через . Тогда для всех Х из К. Если - угловая точка, то первая часть теоремы доказана.

Рисунок 10.2.

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

Так как F(Х) – линейная функция, получаем

(10.18)

В этом разложении среди значений выберем минимальное. Пусть оно соответствует угловой точке и обозначим его через М, т.е. . Заменим в (10.18) каждое значение этим минимальным значением. Тогда, учитывая, что , , получим

.

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

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

Пусть Х – выпуклая линейная комбинация этих угловых точек, т.е.

, ,

Так как – линейная функция, получим

,

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

Теорема 10.3. Если система векторов в разложении (10.14) линейно независима и такова, что

где все , то точка является угловой точкой многогранника решений.

Теорема 10.4. Если – угловая точка многогранника решений, то векторы , соответствующие положительным в разложении (10.14), линейно независимы.

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

Дата добавления: 2015-04-29