Графический метод математического программирования

Размещено на http://www.allbest.ru/

48

Размещено на http://www.allbest.ru/

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

Графический метод математического программирования

Чебоксары 2011



СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА I. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ О ГРАФИЧЕСКОМ СПОСОБЕ РЕШЕНИЯ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ В ДВУМЕРНОМ ПРОСТРАНСТВЕ

§1. Классификация задач математического программирования

§2. Понятие о линейном программировании

§3. Графический метод решения задач линейного программирования

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

§5. Понятие о дробно-линейном программировании и графический метод решения задач дробно-линейного программирования

§6. Понятие о целочисленном программировании и графический метод решения задач целочисленного программирования

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

ГЛАВА II. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ О ГРАФИЧЕСКОМ СПОСОБЕ РЕШЕНИЯ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ В ТРЕХМЕРНОМ ПРОСТРАНСТВЕ

§1. Решения задач линейного программирования графическим методом в трехмерном пространстве

§2. Решения задач нелинейного программирования графическим методом в трехмерном пространстве

ГЛАВА III. РЕШЕНИЕ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ ГРАФИЧЕСКИМ СПОСОБОМ В ДВУМЕРНОМ ПРОСТРАНСТВЕ

§1. Графический способ решения задач линейного программирования

§2. Графический способ решения задач нелинейного программирования

§3. Графический способ решения задач дробно-линейного программирования

§4. Графический способ решения задач целочисленного программирования

§5. Графический способ решения задач параметрического программирования

ГЛАВА IV. РЕШЕНИЕ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ ГРАФИЧЕСКИМ СПОСОБОМ В ТРЕХМЕРНОМ ПРОСТРАНСТВЕ

§1. Примеры задач линейного программирования в трехмерном пространстве, решенные графическим способом

§2. Примеры задач нелинейного программирования в трехмерном пространстве, решенные графическим способом

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК



Введение

Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных вариантов в условиях рыночных отношений приходиться отыскивать наилучшие в некотором смысле при ограничениях, налагаемые на природные, экономические и технические возможности. До недавнего времени большинство таких задач решалось исходя из здравого смысла и опыта лиц, принимающих решения, или просто «на глаз». При таком подходе не было и не могло быть никакой уверенности, что найденный вариант наилучший. При современном масштабе производства даже незначительные ошибки оборачиваются громадными потерями. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы. Такие методы объединяются под общим названием математическое программирование.

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

В общем виде математическая постановка экстремальной задачи состоит в определении наибольшего или наименьшего значения целевой функции f (x₁, x₂, ... , х_п) при условиях g_i (x₁, х₂, ... , х_п) <= b_i (i = 1, m), где f и g_i -- заданные функции, a b_i --некоторые действительные числа.

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

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

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

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

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

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

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

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

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

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

можно представить в виде системы двух неравенств

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

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

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

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений; решением является единственная точка; задача не имеет решений.

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

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

Объекты задачи математического программирования.

Задачи:

1. Исследовать графический метод математического программирования в двумерном пространстве.

2. Исследовать графический метод математического программирования в трехмерном пространстве.

3. Рассмотреть задачи, в решении которых удобно использовать полученные результаты.

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

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

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

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

При написании данной работы использовалась следующая литература: В.И. Копылов, В.Г. Ефремов, Т.И. Рыбакова «Основы математического программирования», Кузнецов А.В., Сакович В.А., Холод Н.И. «Математическое программирование», Карманов В.Г. «Математическое программирование». Некоторые примеры были взяты из книг: Копылов В.И. «Лекции и практические занятия по математическому программированию», Акулич И.Л. «Математическое программирование в примерах и задачах» и из статьи Копылов В.И., Абрамова В.В. «Примеры решения задач нелинейного программирования». Были так же использованы статьи Павловой Е.В., Тяминой А.И. из «Сборника научных статей студентов и преподавателей».



Глава I. Теоретические сведения о графическом способе решения задач математического программирования в двумерном пространстве

§1. Классификация задач математического программирования

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

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

В общем виде математическая постановка экстремальной задачи состоит в определении наибольшего или наименьшего значения целевой функции f (x₁, x₂, ... , х_п) при условиях g_i (x₁, х₂, ... , х_п) <= b_i (i = 1, m), где f и g_i -- заданные функции, a b_i --некоторые действительные числа.

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

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

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

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

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

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

§2. Понятие о линейном программировании

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



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

F = c₁x₁ + c₂x₂ + … + c_nx_n > max (min). (2.2)

В матричной форме задача (2.1) - (2.2) имеет вид:

0, (2.3)

F = ( (2.4)

где = (x₁, x₂, …,x_n), = (c₁, c₂, …, c_n), = (b₁, b₂, …, b_n), A = (a_ij) - матрица коэффициентов. Вектор называют вектором коэффициентов линейной формы, вектор - вектором ограничений.

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

Каноническая задача линейного программирования:

F = c₁x₁ + c₂x₂ + … + c_nx_n > max (min). (2.6)

или в матричной форме:

0, (2.7)

F = ( (2.8)

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

(2.9)

F = c₁x₁ + c₂x₂ + … + c_nx_n > max (min). (2.10)

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

Тот случай, когда в стандартной задаче требуется минимизировать линейную форму, легко сводится к задаче на максимум - F₁ = - c₁x₁ - c₂x₂ - … - c_nx_n > max при тех же ограничениях на переменные, что и в исходной задаче.

В линейном программировании сложилась определенная терминология, которой мы будем поддерживаться. Линейная форма F = c₁x₁ + c₂x₂ + … + c_nx_n, подлежащая максимизации, или минимизации, называется целевой функцией. Вектор = (x₁, x₂, …,x_n), удовлетворяющий всем ограничениям задачи линейного программирования, называется допустимым вектором, или допустимым планом. Задача линейного программирования, для которой существует допустимый вектор, называется допустимой задачей. Допустимый вектор на котором целевая функция принимает наибольшее значение, называется решением задачи, или оптимальным планом. Максимальное значение d = ( целевой функции называется значением задачи.

§3. Графический метод решения задач линейного программирования

Непустое множество планов основной задачи линейного программирования называется многогранником решений, а всякая угловая точка многогранника решений -- вершиной.

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

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

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

F = c₁x₁ + c₂x₂ (3.1)

при условиях:

b_i (i = ) (3.2)

x₁, x₂ (3.3)

Каждое из неравенств (3.2) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми b_i (i = ), x₁=0 и х₂=0. Так как множество точек пересечения данных полуплоскостей -- выпуклое, то областью допустимых решений задачи (3.1) -- (3.3) является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.

Таким образом, исходная задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция F принимает максимальное значение. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим линию уровня c₁x₁ + c₂x₂ = h (где h -- некоторая постоянная), проходящую через многоугольник решений, и будем передвигать ее в направлении вектора = (c₁; c₂) до тех пор, пока она не пройдет через последнюю ее общую точку с многоугольником решений. Координаты указанной точки и определяют оптимальный план данной задачи.

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

Рис. 3.1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 3.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 3.3 изображен случай, когда целевая функция не ограничена сверху на множестве допустимых решений, а на рис. 3.4 -- случай, когда решений нет.



Рис. 3.1-3.2. Возможные области решений задач линейного программирования

Рис. 3.3-3.4. Возможные области решений задач линейного программирования

Отметим, что нахождение минимального значения линейной функции при системе ограничений (3.2) отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня c₁x₁ + c₂x₂ = h передвигается не в направлении вектора = (c₁; c₂), а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минимального значения.

Итак, нахождение решения задачи линейного программирования (3.1) --(3.3) графическим методом включает следующие этапы:

Строят прямые, уравнения, которых получаются в результате замены в ограничениях (3.2) и (3.3) знаков неравенств на знаки точных равенств;

Находят полуплоскости, определяемые каждым из ограничений задачи;

Находят многоугольник решений;

Строят вектор = (c₁; c₂);

Строят прямую c₁x₁ + c₂x₂ = h, проходящую через многоугольник решений;

Передвигают прямую c₁x₁ + c₂x₂ = h в направлении вектора , в результате находят точку (точки), в которой целевая функция принимает максимальное (минимальное) значение, либо устанавливают неогра-ниченность сверху функции на множестве планов;

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

Пример 3.1 (задача об использовании сырья).

Таблица 3.1. Исходные данные задачи

Виды сырья	Запасы сырья	П1	П2
S1	19	2	3
S2	13	2	1
S3	15	0	3
S4	18	3	0
Доход	-	7	5

Для изготовления продукции двух видов П₁ и П₂ требуется 4 вида сырья S₁, S₂, S₃, S₄. Запасы сырья каждого вида ограничены и составляют соответственно 19, 13, 15 и 18 единиц. Количество единиц сырья, необходимо для изготовления единицы каждого вида продукции, известно и задается таблицей 3.1. Составить такой план выпуска продукции видов П₁ и П₂, при котором доход предприятий от реализации всей продукции был бы максимален.



Решение:

Пусть предприятие должно выпускать х₁ единиц продукции П₁ и х₂ единиц продукции П₂, следовательно, х₁ и х₂ положительны. Для этого потребуется сырья:

Доход, получаемый предприятием, составит Z = 7x₁ + 5x₂ max.

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

Решим ее используя представленный выше алгоритм:

Сначала построим прямые, уравнения, которых получаются в результате замены в ограничениях (3.4) знаков неравенств на знаки точных равенств: Затем определим полу-плоскости, определяемые каждым из ограничений задачи. Таким образом, найдем многоугольник решений - ABCDEF (рис. 3.5). Далее строим вектор = (7; 5), определяемый коэффициентами целевой функции. Строим линии уровня 7x₁ + 5x₂ = h, проходящие через многоугольник решений. Передвигая прямую 7x₁ + 5x₂ = h в направлении вектора , находим точку D, в которой целевая функция принимает максимальное значение. Определяем координаты точки максимума функции, решая систему:

D(5;3).

После чего вычисляем значение целевой функции в этой точке:



Zmax = 7.

Ответ: требуется производить 5 изделий П₁ и 3 изделия П₂. Максимальный доход: 50 единиц.

Рис. 3.5. Графическое решение примера 3.1

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

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

(4.1)

при условии, что ее переменные удовлетворяют соотношениям:

(4.2)



где f и g_i -- некоторые известные функции n переменных (хотя бы одна из них не линейна), а b_i -- заданные числа.

Здесь имеется в виду, что в результате решения задачи будет определена точка = (, , …, ), координаты которой удовлетворяют соотношениям (4.2) и такая, что для всякой другой точки x = , удовлетворяющей условиям (4.2), выполняется неравенство:

[]

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

Если определена область допустимых решений, то нахождение решения задачи (4.1), (4.2) сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня:Указанная точка может находиться как на границе области допустимых решений, так и внутри нее.

Процесс нахождения решения задачи нелинейного программирования (4.1), (4.2) графическим методом включает следующие этапы:

Находят область допустимых решений задачи, определяемую соотношениями (4.2) (если она пуста, то задача не имеет решения);

Строят гиперповерхность ;

Определяют гиперповерхность наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из-за неограниченности функции (4.1) сверху (снизу) на множестве допустимых решений;

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

Пример 4.1. Найти максимальное значение функции:

= (4.3)

при условиях:

Решение:

Так как целевая функция (4.3) нелинейная, то задача (4.3) -- (4.4) является задачей нелинейного программирования. Воспользуемся приведенным выше алгоритмом решения задач нелинейного программ-мирования графическим методом. Находим область решений строя прямые, уравнения, которых получаются в результате замены в ограничениях (4.4) знаков неравенств на знаки точных равенств: Затем находим полуплоскости, определяемые каждым из ограничений задачи. Таким образом, областью допустимых решений данной задачи является многоугольник ОАВС (рис. 4.1). Следовательно, для нахождения решения задачи нужно определить такую точку многоугольника ОАВС, в которой функция (4.3) принимает максимальное значение. Построим линию уровня = , где h-- некоторая постоянная, и исследуем ее поведение при различных значениях h. При каждом значении h получаем параболу, которая тем выше отдалена от оси Ох, чем больше значение h (рис. 4.1). Значит, функция F принимает максимальное значение в точке касания одной из парабол с границей многоугольника ОАВС.

В данном случае это точка D, в которой линия уровня = касается стороны АВ многоугольника ОАВС. Координаты точки D можно найти из системы уравнений:

Решая эту систему, получим x₁=3; x₂=4. Итак, F_max=13 при Х* = (3; 4).

Рис. 4.1. Графическое решение задачи 4.1

Ответ: F_max=13 при Х* = (3; 4).

Как видим, в задаче (4.3) -- (4.4) точка максимального значения целевой функции не является вершиной многоугольника решений. Поэтому процедура перебора вершин, которая использовалась при решении задач линейного программирования, неприменима для решения данной задачи.

§5. Понятие о дробно-линейном программировании и графический метод решения задач дробно-линейного программирования

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

при условиях:

) (5.3)

где c_j, d_j, b_i и a_ij - некоторые постоянные числа, ) и в области неотрицательных решений системы линейных уравнений (5.2). При этом будем предполагать, что (такое условие не нарушает общности задачи, поскольку в том случае, когда эта величина отрицательна, знак минус можно отнести к числителю).

Как и в случае основной задачи линейного программирования, свое максимальное значение целевая функция задачи (5.1) принимает в одной из вершин многогранника решений, определяемой системой ограничений (5.2) и (5.3) (естественно, при условии, что эта задача имеет оптимальный план).

Рассмотрим задачу, состоящую в определении максимального (минимального) значения функции:



при условии:

Будем считать, что

Чтобы найти решение задачи (5.4) -- (5.6), сначала находим многоугольник решений, определяемый ограничениями (5.5) и (5.6). Предполагая, что этот многоугольник не пуст, полагаем значение функции равным некоторому числу h, так что прямая

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

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

Теорема 5.1. Если , то с увеличением линия уровня функции вращается по часовой стрелке; если , то линия уровня вращается против часовой стрелки.

Итак, процесс нахождения решения задачи (5.4) -- (5.6) графическим методом включает следующие этапы:

В системе ограничений задачи заменяют знаки неравенств на знаки точных равенств и строят определяемые этими равенствами прямые;

Находят полуплоскости, определяемые каждым из неравенств системы ограничений задачи;

Находят многоугольник решений задачи;

Строят прямую (5.7), уравнение которой получается, если положить значение целевой функции (5.4) равным некоторому постоянному числу;

Определяют точку максимума или устанавливают неразрешимость задачи;

Находят значение целевой функции в точке максимума.

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

Таблица 5.1. Данные задачи 5.1

Тип оборудования	Затраты времени на производство одного изделия	Продолжительность работы (ч)
	А	В
I	2	8
II	1	1
III	12	3
Затраты на производство одного изделия	2	3	-

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

Решение:

Предположим, что предприятие изготовит х₁ изделий вида А и х₂ изделий вида В. Тогда общие затраты на их производство равны 2х₁ + 3x₂ руб., а себестоимость одного изделия в рублях составит

Затраты времени на обработку указанного количества изделий на каждом из типов оборудования соответственно составят 2x₁ +8x₂ часов, часов и часов. Так как оборудование I и III типов может быть занято обработкой изделий вида А и В не более 26 и 39 ч, а оборудование II типа -- не менее 4 ч, то должны выполняться следующие неравенства:

По своему экономическому смыслу переменные х₁ и х₂ могут принимать только лишь неотрицательные значения:

х_1, х₂

Таким образом, математическая постановка задачи состоит в определении неотрицательного решения системы линейных неравенств (5.9), реализующего минимум функции (5.8). Чтобы найти решение задачи, прежде всего, построим многоугольник решений. Как видно из рис. 5.1, им является треугольник BCD. Значит, функция (5.8) принимает минимальное значение в одной из точек: В, С или D. Определим направление вращения прямой целевой функции, по теореме 5.1: , тогда прямая вращается против часовой стрелки. Тогда минимальное значение функция принимает в точке D (3; 1).



Рис. 5.1. Графическое решение задачи 5.1

Таким образом, оптимальным планом производства продукции является план, согласно которому изготовляется три изделия вида А и одно изделие вида В. При таком плане себестоимость одного изделия является мини-мальной и равна F_min = 9/4.

Ответ: F_min = 9/4 при D (3; 1).

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

Многогранник решений ограничен, максимум и минимум достигаются в его угловых точках (рис. 5.2);

Многогранник решений не ограничен, однако существуют угловые точки, в которых целевая функция задачи принимает соответственно максимальное и минимальное значения (рис. 5.3);

3. Многогранник решений не ограничен, и один из экстремумов достигается. Например, минимум достигается в одной из вершин многогранника решений и функция F имеет так называемый асимптотический максимум (рис. 5.4);

4. Многогранник решений не ограничен, как максимум, так и минимум являются асимптотическими (рис. 5.5).

Рис. 5.2-5.3. Возможные случаи задач дробно-линейного программирования



Рис. 5.4-5.5. Возможные случаи задач дробно-линейного программирования

§6. Понятие о целочисленном программировании и графический метод решения задач целочисленном программирования

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

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

Примером целочисленной задачи можно привести задачу о ранце.

Задача 6.1 (задача о ранце).

В поход собирается путешественник, который должен упаковать в ранец различные предметы n наименований, причем могут потребоваться несколько одинаковых предметов. Имеется m ограничений по весу, объему, линейным размерам и т.д. Пусть a_ij i - я характеристика j - го предмета, b_i - ограничение по весу, объему, линейным размерам и т.д. (i = 1, 2, …, m; j = 1, 2, …, n). Считается, что известна полезность c_j одного j - го предмета. Требуется так упаковать ранец, чтобы он имел максимальную полезность при условии выполнения всех ограничений.

Решение:

Составим математическую модель этой задачи. Обозначим через x_j, (j = 1, 2, …, n) - количество предметов j - го наименования, запланированных к загрузке в ранец. Тогда:

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

Нахождение решения задачи целочисленного программирования графическим методом включает следующие этапы:

1. Получить для задачи целочисленного программирования многоугольник решений, удовлетворяющим ограничениям данной задачи;

2. Определить все целочисленные координаты, принадлежащие получившемуся многоугольнику решений;

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

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

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

Пример 6.1.

В цехе предприятия было решено установить дополнительное оборудование, для размещения которого выделено площади. На приобретение оборудования предприятие может израсходовать 10 тыс. руб., при этом оно может купить оборудование двух видов. Комплект оборудования I вида стоит 1000 руб., в II вида - 3000 руб. Приобретение одного комплекта оборудования I вида позволяет увеличить выпуск продукции за смену на 2 ед., а одного комплекта II вида - на 4 ед. Зная, что для установки одного комплекта оборудования I вида 2 площади, а оборудование II вида - 1 площади. Определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.

Решение:

Составим математическую модель задачи.

Пусть предприятие приобретает комплектов I вида и комплектов оборудования II вида. Тогда переменные и должны удовлетворять следующим неравенствам:

Если предприятие приобретает указанное количество оборудования, то общее увеличение выпуска продукции составит:

По своему экономическому содержанию переменные и могут принимать лишь целые неотрицательные значения, то есть

,

, - целые. (6.4)

Применим вышеуказанный алгоритм:

Построим многоугольник решений OABC, удовлетворяющий условиям (6.1) и (6.3) задачи (рис. 6.1).

Рис. 6.1. Решение задачи 6.1

Из рисунка видно, что условию целочисленности переменных многоугольника OABC, удовлетворяют лишь 12 координат отмеченных на рисунке точками. Чтобы найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник OABC областью, содержащей все допустимые точки с целочисленными координатами. Так как наша задача является задачей линейного программирования, то строим вектор = (2; 4), прямую 2x₁ + 4x₂ = h, проходящую через область, содержащую точки с целочисленным координатами.

Передвигаем прямую 2x₁ + 4x₂ = h в направлении вектора С, до тех пор, пока она не пройдет через последнюю общую точку с полученной областью, то есть точка Е (1; 3). Координаты этой точки и определяют оптимальный план, а значение целевой функции в ней является максимальным - F_max = 14.

Ответ: предприятию нужно приобрести один комплект оборудования I вида и три комплекта оборудования II вида. Это обеспечит предприятию при имеющихся у него ограничениях на производственные площади и денежные средства максимальное увеличение выпуска продукции, равное 14 ед. в смену.

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

Во многих задачах математического программирования исходные данные зависят от некоторого параметра. Такие задачи называются задачами параметрического программирования.

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

Задача, в которой коэффициенты целевой функции линейно зависят от параметра t, заключается в нахождении для каждого значения параметра t из промежутка его изменения [] максимального (минимального) значения функции

при условиях

где , и заданные постоянные числа.

Если от параметра t линейно зависят свободные члены системы ограничений, то задача состоит в нахождении для каждого значения параметра t из промежутка его изменения [] максимального (минимального) значения линейной функции

при условиях



где , и заданные постоянные числа.

В том случае, когда от параметра t линейно зависят как коэффициенты целевой функции, так и свободные члены системы ограничений, задача состоит в нахождении для каждого значения параметра t из промежутка его изменения [] максимального (минимального) значения функции

при условиях

Обобщением этих задач является общая задача параметрического программирования, в которой от параметра t линейно зависят коэффициенты при неизвестных в целевой функции, коэффициенты при неизвестных в системе уравнений и свободные члены системы уравнений. Она заключается в следующем: для каждого значения параметра t из некоторого промежутка его изменения [] требуется найти максимальное (минимальное) значение функции

при условиях



Рассмотрим графический метод задач параметрического линейного программирования, в случае задачи (7.1) -- (7.3).

Предположим, что множество неотрицательных решений системы линейных уравнений (7.2) (многогранник решений) не пусто и включает более чем одну точку. Тогда исходная задача состоит в определении при каждом значении параметра t такой точки многогранника решений, в которой функция (7.1) принимает максимальное (минимальное) значение. Чтобы найти указанную точку, будем считать t = t₀ и, используя графический метод, находим решение полученной задачи линейного программирования (7.1) -- (7.3), т.е. либо определяем вершину многогранника решений, в которой функция (7.1) имеет максимальное (минимальное) значение, либо устанавливаем, что при данном значении t₀ задача неразрешима. После того как найдена точка, в которой при t = t₀ функция (7.1) принимает максимальное (минимальное) значение, ищется множество значений t, для которых координаты указанной точки определяют оптимальный план задачи (7.1) -- (7.3). Найденные значения параметра t исключаются из рассмотрения, и берется некоторое новое значение t, принадлежащее промежутку . Для выбранного значения параметра t₁ определяется оптимальный план полученной задачи или устанавливается ее неразрешимость. После этого находится отрезок изменения параметра t, принадлежащий промежутку для которого найденная точка определяет оптимальный план или для которого задача неразрешима. В результате после конечного числа шагов для каждого значения параметра t из промежутка либо находится оптимальный план, либо устанавливается неразрешимость задачи.

Пример 7.1.

Предприятие должно выпустить два вида продукции А и В, для изготовления которых используется три вида сырья. Нормы расхода сырья каждого вида на производство единицы продукции данного вида приведены в таблице 7.1. В ней же указаны запасы сырья каждого вида, которое может быть использовано на производство единицы продукции данного вида.

Известно, что цена единицы продукции может изменяться для изделия А от 2 до 12 руб., а для изделия В -- от 13 до 3 руб., причем эти изменения определяются соотношениями где

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

Таблица 7.1. Данные задачи 7.1

Вид сырья	Нормы расхода сырья на произ-во 1 продукции	Запасы сырья
	А	В
I	4	1	16
II	2	2	22
III	6	3	36

Решение:

Предположим, что предприятие изготовит единиц продукции А и единиц продукции В. Тогда математическая постановка задачи состоит в определении для каждого значения параметра t (0 ? t ? 10) максимального значения функции

при условиях



Чтобы найти решение задачи (7.13) (7.14), строим многоугольник решений, определяемый системой линейных неравенств (7.14) (рис. 7.1). После этого, полагая t =0, строим прямую (число 26 взято произвольно) и вектор = (2; 13). Передвигая построенную прямую в направлении вектора , видим, что последней общей точкой ее с многоугольником решений OABCD является точка А(0; 11). Следовательно, задача, полученная из задачи (7.13) (7.14) при t =0, имеет оптимальный план Это означает, что если цена единицы продукции А равна 2 + 0 = 2 руб., а цена единицы продукции В равна 13 - 0 = 13 руб., то оптимальным планом производства является план, согласно которому производится 11 изделий В и не производятся изделия А. При таком плане производства продукции ее стоимость максимальна и равна

Рис. 7.1. Решение задачи 7.1

Положим теперь t =2 и построим прямую (2 + 2) + (13 + 2) = 4 + 11 = 44 (число 44 взято произвольно) и вектор =(4; 11). Передвигая построенную прямую в направлении вектора , видим, что последней ее общей точкой с многоугольником решений является точка А (0; 11). Следовательно, задача, полученная из задачи (7.13) -- (7.14) при t =2, имеет оптимальный план = (0; 11). Это означает, что если цена единицы продукции А равна 2 + 2 = 4 руб., а цена единицы продукции В равна 13--2=11 руб., то предприятию также наиболее целесообразно производить 11 ед. продукции вида В и совсем не производить продукцию вида А. При таком плане производства продукции ее общая стоимость является максимальной и составляет = (2 + 2)0 + (13 - 2)11 = 121 руб.

Как видно из рис. 7.1, данный план производства продукции будет оставаться оптимальным для всякого значения t, пока прямая не станет параллельной прямой . Это произойдет тогда, когда / 2= / 2, т.е. при t =5,5. При этом значении t координаты любой точки отрезка АВ дают оптимальный план задачи (7.13) -- (7.14).

Таким образом, для всякого задача (7.13) -- (7.14) имеет оптимальный план = (0; 11), при котором значение целевой функции (7.13) есть

Возьмем теперь какое-нибудь значение параметра t, большее 5,5, например 6. Полагая t = 6, найдем решение соответствующей задачи (7.13) -- (7.14). Для этого построим прямую (число 56 взято произвольно) и вектор =(8; 7). Передвигая построенную прямую в направлении вектора , видим, что последней ее общей точкой с многоугольником решений является точка В (1; 10). Следовательно, задача, полученная из задачи (7.13) -- (7.14) при t = 6, имеет оптимальный план = (1; 10). Это означает, что если цена единицы продукции А равна 2 + 6=8 руб., а цена единицы продукции В равна 13--6=7 руб., то оптимальным планом ее изготовления является план, согласно которому производится одно изделие вида А и 10 изделий вида В. При этом плане общая стоимость производимой продукции максимальна:

Как видно из рис. 7.1, план = (1; 10) является оптимальным планом задачи (7.13) -- (7.14) для всякого t > 5,5 до тех пор, пока прямая не станет параллельной прямой . Это произойдет тогда, когда (2 + t) / 6 =(13 - t) / 3, т. е. при t = 8. При этом значении t координаты любой точки отрезка ВС дают оптимальный план задачи (7.13) -- (7.14).

Таким образом, для всякого задача (7.13)--(7.14) имеет оптимальный план = (1; 10), при котором значение линейной функции (7.13) составляет

Используя рис. 7.1 и проводя аналогичные рассуждения, получим, что для всякого оптимальным планом задачи (7.13) -- (7.14) является = (2; 8). Это означает, что если цена единицы продукции вида А заключена между (или равна) 10 и 12 руб., а единицы продукции В -- между (или равна) 3 и 5 руб., то оптимальным планом ее производства является такой план, согласно которому изготовляется 2 ед. продукции вида А и 12 ед. продукции вида В. При этом плане производства продукции ее общая стоимость для каждого значения параметра составляет.

Ответ:

Если , то оптимальным планом является = (0; 11), причем;

если , то оптимальным планом является = (1; 10), причем ;

если , то оптимальный план = (2; 8), причем .

Теперь рассмотрим графический метод задач параметрического программирования, в случае задачи (7.4) -- (7.6), то есть задачи, в которой от параметра зависят свободные члены системы ограничений. Рассмотрим на примере.

Пример 7.2.

Решить задачу параметрического программирования, где :

Решение:

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

Найдем многоугольник решений для получившейся системы ограничений при значении параметра



Рис. 7.2.1. Решение задачи 7.2 для

Исходя из рисунка 7.2.1, видно, что оптимальное решение задачи 7.2 находится в точке А. Для определения координат точки А в общем виде, решим систему уравнений:

Решая данную систему, имеем, что это и есть координаты точки А в общем виде: А (). Значит, наибольшее значение функции F при равно

Так как значит следующее значение параметра . Подставим данное значение в систему ограничений задачи, получим:



Найдем многоугольник решений для получившейся системы ограничений при значении параметра

Рис. 7.2.2. Решение задачи 7.2 для

Исходя из рисунка, видно, что оптимальное решение задачи 7.2 находится так же в точке А, то есть А ().

Значит, наибольшее значение функции F при равно

Так как значит следующее значение параметра . Подставим данное значение в систему ограничений задачи, получим:



Найдем многоугольник решений для получившейся системы ограничений при значении параметра