Файл: Егоров, Казаков Мет. по лин. програм..pdf

18

ствам заданной системы линейных неравенств. Поэтому областью решений системы линейных неравенств является неограниченное множество.

4)Область решений задачи линейного программирования – многоугольник

Рис. 1.4.

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

Вопросы для самопроверки

Что задается в задаче линейного программирования системой линейных неравенств?

Что является решением системы линейных неравенств?

Что представляет собой область решений задачи линейного программирования?

Из чего состоит область решений неравенства?

Как определить, какая из двух полуплоскостей удовлетворяет неравенству?

Из каких последовательных шагов состоит построение области решений задачи линейного программирования с ограничениями в виде системы линейных неравенств?

19

Какие возможны случаи областей решений задачи линейного программирования?

Может ли область решений задачи линейного программирования состоять из одного ре-

шения, двух решений и т.д., из множества решений?

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

▼

Пример

Словесная формулировка задачи

Фирма изготовляет два вида изделий.

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

Изучение рынка сбыта показало, что суточный спрос на изделие 1-ого вида никогда не превышает спроса на изделие 2-ого вида более чем на 1 тонну. Кроме того, установлено, что суточный спрос на изделие 1-ого вида никогда не превышает 2 тонн.

Оптовая цена одной тонны изделия 1-ого вида равна 2 тыс. у.е., 2-ого вида равна 3

тыс. у.е.

Какой объем изделий каждого вида должна производить фирма в сутки, чтобы суточный доход от реализации продукции был максимальным?

Математическая формулировка задачи

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

просов:

1)С помощью каких искомых величин можно выразить числом заданную цель на основе заданных исходных данных?

2)Каким алгебраическим выражением можно представить заданную цель с помощью исходных данных и соответствующих искомым величинам переменных?

3)Какие алгебраические ограничения должны быть наложены на переменные, чтобы

20

выполнялись все заданные исходные условия?

Ответы на эти вопросы для рассматриваемой задачи:

Пронумеруем ограничения рассматриваемой задачи линейного программирования: z 2 x1 3x2 max

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

2x1 2 x2 8,

3x1 x2 1,

Областью допустимых решений задачи, или заданной областью определения целевой функции называются все значения вектора x 2 ( x1 , x2 ), удовлетворяющие заданным

ограничениям задачи.

Каждому одному ограничению геометрически соответствует полуплоскость, состоящая из двух множеств:

1) множества точек, удовлетворяющих уравнению (обозначено прямой с соответствую-

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

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

21

Рис. 1.5.

Целевая функция геометрически представляется (рис. 1.6) прямой, соответствующей произвольно выбранному значению z . Выбирая последовательно увеличивающиеся значе-

ния z (направление увеличения обозначено стрелкой и определяется вектором N , коорди-

натами которого являются коэффициенты целевой функции), можно найти оптимальное ре-

Рис. 1.6.

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

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