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

Введение

Пусть R есть множество действительных чисел. Обозначим: Rn - множество всех n-мерных векторов (Евклидово пространство).
Имеется два вида оптимизационных задач.
В классической задаче поиска экстремума (минимума или максимума) функции f(x1,x2,…,xn) подразумевается, что x1,x2,…,xn∈Rn, где вектор решений X=(x1,x2,…,xn) определен на всем множестве действительных чисел Rn, т.е. нет никаких специальных ограничений на переменные функции. Такая задача называется задачей безусловной оптимизации.
Если вектор решений X определен не на всем множестве Rn, т.е. имеется требование, чтобы переменные функции удовлетворяли некоторым условиям, то такая задача называется задачей условной оптимизации.
Задачи условной оптимизации возникли как составная часть научной дисциплины под названием исследование операций.
Полагают, что термин ``исследование операций'' впервые ввел английский ученый А. Раув, который в 1938г. руководил научной группой, разрабатывающей эффективные средства противовоздушной обороны Англии. Становление исследования операций как научной дисциплины относят к 1952 году и связывают с работами П. Блекетта, Ф. Морза и Д. Кимбелла. Последние два автора опубликовали в этом году книгу ``Методы исследования операций''.
К числу первых работ, связанных с разработкой методов решения задач исследования операций, относят также работу профессора Ленинградского университета Л.В. Канторовича, который в 1939 году выполнял хоздоговорную тематику по оптимальному раскрою фанерных листов. Он предложил так называемый метод разрешающих множителей для решения поставленной задачи.
В последующем, некоторые разделы исследования операций получили большее развитие, другие - меньшее. Наиболее впечатляющий результат получен в работе Л. Хачияна, который, работая научным сотрудником Вычислительного Центра АН СССР, доказал в 1980 году, что для задач линейного программирования - одного из разделов исследования операций - существует теоретически эффективный (полиномиально-временной) алгоритм для их решения. На основе этой работы американский математик Н. Кармаркар разработал такой алгоритм. (Karmarkar N. A New Polynomial-time algorithm for linear programming. Combinatorica. 1984. N 4, p. 373--395.)
Характерной особенностью задач условной оптимизации является их большой объем и поэтому реальные задачи недоступны для ручных вычислений. Поэтому для их решения разрабатываются компьютерные программы.
Для задач условной оптимизации все условия, накладываемые на неизвестные задачи, записываются в виде системы ограничений (уравнений и неравенств). Критерий оптимальности записывается в виде функции, которую называют целевой. Решение задачи условной оптимизации состоит в отыскании на множестве решений системы ограничений наибольшего или наименьшего значения целевой функции.
Процесс решения задачи состоит из следующих этапов:
Выбор или разработка метода решения задачи.
Если это возможно, то используется известный метод для решения сформулированной задачи. Если метода решения сформулированной задачи нет, то такой метод разрабатывается.
Выбор или написание программы решения задачи на компьютере.
Для решения задачи на компьютере необходимо выбрать существующую программу решения соответствующего класса задач, или написать программу при ее отсутствии.
Решение задачи на компьютере.
Вся необходимая информация для решения задачи на компьютере вводится в память машины вместе с программой ее решения.
Анализ полученного решения.
Производят формальный и содержательный анализ полученного решения (анализ на чувствительность).
Выполнение перечисленных этапов может повторяться, т.е. в процессе построения математической модели может оказаться необходимым уточнить содержательное описание задачи, или в процессе выбора или создания метода решения задачи необходимо вернуться к построению математической модели и т.п.
К сожалению, не существует единого алгоритма решения задач условной оптимизации ввиду их сложности. Поэтому далее рассмотрим особый класс задач условной оптимизации - задачи линейного программирования, для решения которых разработан практически эффективный алгоритм.


Общая форма задачи линейного программирования.
В общем виде задача линейного программирования формулируется следующим образом: найти значения неизвестных x1,x2,…,xn∈Rn, доставляющих экстремум (минимум или максимум) функции
fx1,x2,…,xn=j=1ncjxj→min⁡(max), (1)
и удовлетворяющие ограничениям
i=1mj=1naijxj≤=≥bi, (2)
а также условиям неотрицательности
xj≥0, j=1,2,…,n. (3)
Здесь задачу (1) - (3) называют задачей линейного программирования, функцию цели (1) называют также линейной формой. Систему ограничений (2) называют также многоугольником (при n=2) или многогранником (при n>2) решений или планов.
Коэффициенты cj в функции цели называют иногда коэффициентами затрат, а коэффициенты aij (i=1,…,m; j=1,…,n) называют также нормой затрат i-го ресурса на производство j-го продукта.
Совокупность значений переменных x1,x2,…,xn∈Rn, удовлетворяющих ограничениям (2), называют допустимым решением задачи (1) - (3). Допустимое решение, доставляющее экстремум функции (1) называют оптимальным решением задачи (1) - (3).


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

. За неизвестные необходимо принимать такие величины, которые и предстоит определить как результат решения задачи. Эти величины обычно обозначаются последними буквами латинского алфавита х, у, … и т.д. с одним или несколькими индексами.
Построение функции цели осуществляют, исходя из критерия, по которому будут сравниваться различные варианты и выбираться среди них наилучшее (оптимальное) решение. В качестве такого критерия в различных исследуемых процессах могут быть наибольшая прибыль, наименьшие издержки производства, максимальное использование оборудования, достижение определенного результата за наименьшее время, наименьшие отходы производства, наибольшая товарная продукция и т.д.
Учёт ограничений позволяет наложить определенные условия на пределы изменения неизвестных задачи. Этим учитываются ограниченность ресурсов, которыми и необходимо распорядиться наилучшим образом.
Рассмотрим пример составления математической модели.
Пример 1.
Мебельная фабрика выпускает столы, стулья и книжные шкафы. При изготовлении этих изделий используются два различных типа досок: I и II. Фабрика имеет в наличии 1500 м досок I-го типа и 1000 м досок II-го типа. Кроме того, заданы трудовые ресурсы в количестве 800 чел.-ч.
Нормативы затрат каждого вида ресурсов на изготовление 1 единицы изделия и прибыль на 1 единицу изделия приведены в следующей таблице:
Ресурсы Столы Стулья Книжные шкафы
Доски 1-го типа 5 1 12
Доски II-го типа 2 3 1
Трудовые ресурсы 3 2 10
Прибыль 12 5 10

Определить оптимальный ассортимент выпускаемой продукции, максимизирующий прибыль.
Решение.
Осуществим выбор неизвестных задачи.
Ясно, что в решении мы должны указать количество изделий каждого вида, которое должно выпускаться мебельной фабрикой. Поэтому в качестве неизвестных задачи выбираем:
x1 - количество (шт) столов,
x2 - количество (шт) стульев,
x3 - количество (шт) книжных шкафов, которые будет выпускать фабрика.
Целью производства является прибыль. Прибыль от производства всех столов, которые будут выпущены в количестве x1 штук, помноженное на прибыль фабрики от выпуска единицы этого изделия, т.е. общая прибыль от производства столов будет равна 12x1, прибыль от производства всех стульев равна 5x2. Аналогично определяем прибыль от производства всех книжных шкафов: 10x3.
Нам необходимо получить наибольшую прибыль.
Если рассмотреть полученную функцию цели формально, мы видим, что чем большие значения неизвестных будут взяты, тем большее значение функции будет получено.
К сожалению, мы не можем выбирать произвольно большие значения неизвестных, так как продукция фабрики изготавливается из досок, а на плановый период мы имеем ограниченное количество этих ресурсов. Кроме того, имеется ограничение по использованию труда работников фабрики.
Как учесть ограниченность существующих ресурсов?
Рассмотрим в каком количестве будет использован первый ресурс - доска I-го типа.
На производство одного стола затрачивается 5 м доски I-го типа. Следовательно, на производство всех столов будет затрачено 5x1 м доски рассматриваемого типа. Аналогично определяем, что на производство всех стульев будет затрачено x2 м и, наконец, на производство всех книжных шкафов - 12x3 м доски I-го типа.
Таким образом, общие затраты доски I-го типа составят 5x1+x2+12x3 м. Эта величина не должна превышать 1500 м - существующее количество доски данного типа (меньшее количество, очевидно, может быть использовано). Поэтому получаем окончательно первое ограничение в виде неравенства:
5x1+x2+12x3≤1500.
Аналогично рассуждая, найдем, что ограниченность ресурса второго вида (доски II-го типа) приводит к получению неравенства:
2x1+3x2+x3≤1000.
И, наконец, неравенство
3x1+2x2+10x3≤800
учитывает ограниченность ресурса третьего вида - трудовых ресурсов.
Ясно, что фабрика не может произвести, скажем, -5 стульев - это бессмыслица. Поэтому полагаем, что x1,x2,x3≥0.
Таким образом, математическая модель сформулированной выше задачи, будет иметь следующий вид.
Найти значения переменных x1, x2, x3, доставляющих максимум функции цели
fx1,x2,x3=12x1+5x2+10x3→max
и удовлетворяющих ограничениям:
5x1+x2+12x3≤1500
2x1+3x2+x3≤1000
3x1+2x2+10x3≤800
а также условиям неотрицательности
x1,x2,x3≥0.
Последнее условие (неотрицательность переменных) всегда должно выполняться в задачах линейного программирования.


Графический метод решения задач линейного программирования
Для четкого понимания принципов решения задач линейного программирования аналитическими средствами (симплекс-методом) очень важно хорошо понимать графический метод их решения.
Графическим методом можно решать задачи линейного программирования, содержащие не более трех переменных. Однако практически решают таким способом задачи, имеющие две неизвестные (т.е на плоскости).
Графическое решение задачи линейного программирования целесообразно производить в следующем порядке:
а) построить область определения функции цели;
б) построить направляющий вектор C=(с1;с2);
в) найти точку области допустимых решений, в которой функция цели достигает экстремума;
г) найти экстремальное значение функции цели.
Область определения функции цели задается системой линейных равенств и неравенств. С графической точки зрения такая область представляет собой пересечение полуплоскостей (или прямых), которые определяются выше указанной системой.
Во всех задачах линейного программирования область определения функции цели всегда выпукла, т.е. вместе с любыми двумя точками этой же области принадлежат и точки отрезка, соединяющего эти две точки.
В частном случае область определения может представлять собой неограниченную фигуру