Векторное пространство Решение задач линейного программирования графическим способом (стр. 3 из 5)

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

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

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

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

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

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

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

Пусть дана задача

Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (2.2), (2.3) задает на плоскости

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

Выпуклое множество – множество, которое вместе с любыми своими точками

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

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

(рисунок 1 [2, с. 29, рисунок 1.3] ).

Выберем произвольное значение целевой функции

. Получим . Это уравнение прямой линии. В точках NM целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве (2.1) Z параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня функции (линиями постоянного значения).

Рисунок 1

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

и :

Частная производная (2.4) (2.5) функции показывает скорость ее возрастания вдоль данной оси. Следовательно,

и скорости возрастания Z соответственно градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

Вектор –с указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.

Вектор

перпендикулярен к прямым Z = const семейства .

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

1. С учетом системы ограничений строим область допустимых решений.

2. Строим вектор

наискорейшего возрастания целевой функции – вектор градиентного направления.

3. При решении задачи на максимум перемещаем линию уровня

перемещают в антиградиентном направлении (на рисунке 1 – до точки ).

4. Определяем оптимальный план

и экстремальное значение целевой функции .

Сделаем некоторые примечания:

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

2) Если область допустимых решений неограничена по направлению вектора

, то сама целевая функция неограничена сверху в этой области, и тогда maxZ = . Если область допустимых решений неограничена в направлении, противоположном c, то получаем minZ= .

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

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

В частном случае, когда в систему ограничений входят только две переменные x1 и x2, это множество можно изобразить на плоскости. Так как речь идет о допустимых решениях (x1, x2 ≥ 0), то соответствующее множество будет располагаться в первой четверти декартовой системы координат. Это множество может быть замкнутым (многоугольник), незамкнутым (неограниченная многогранная область), состоять из единственной точки и, наконец, система ограничений-неравенств может быть противоречивой.

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

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

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

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