Геометрический метод решения ЗЛП с n=2

Геометрический способ решения ЗЛП целесообразно использовать для:

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

Рассмотрим ЗЛП в стандартной форме с двумя переменными:

а11Х112Х2

а21Х1 а,22Х2 —

z = c1x1+c2x2 max (min)

  • (4)
  • (5)

Целевая функция (5) определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значение Z.

План решения ЗЛП геометрическим методом

  • 1. Строится ОДР X. Если X = 0, то задача не имеет решения.
  • 2. Строим вектор градиента целевой функции

dz dz

'2

- нормальный вектор, он указывает направление возрастания целевой функции z.

Прямая, перпендикулярная вектору N(cpC2), определяет множество

равных значений целевой функции

z = c1x1 + c2x2 =(с.

= const

3. Строим прямую равных значений У?о, проходящую через начало координат

z = c1x1 + с2х2 =0.

В каждой точке этой прямой целевая функция равна нулю.

4. Мысленно перемещаем прямую в направлении вектора N(cpC2), тогда:

ближайшая угловая точка встречи с областью X является точкой min z, а самая дальняя угловая точка встречи, является точкой max z.

Геометрический метод решения ЗЛП

Рисунок 4 - Геометрический метод решения ЗЛП

На втором рисунке задача на max решений не имеет, т.е. Z не ограничена сверху (аналогично может быть не ограничен min).

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

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

Пример решения ЗЛП на плоскости (с n=2)

Пример. Определение оптимального ассортимента продукции.

Предприятие изготавливает два вида продукции - Пх и П2 которые поступают в оптовую продажу. Для производства продукции используются два вида сырья - А и В. Максимально возможные запасы сырья в сутки составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции вида П1 и вида П2 дан в таблице 1.

Опыт работы показал, что суточный спрос на продукцию Пх никогда не превышает спроса на продукцию П2 более чем на 1 ед. Кроме того, известно, что спрос на продукцию П2 никогда не превышает 2 ед. в сутки. Оптовые цены единицы продукции равны: 3 д. е. - для Пх и 4 д. е. для П2.

Таблица 1

Расход сырья продукции

Сырье

Расход сырья на 1 ед. продукции

Запас сырья, ед.

д

д

А

2

3

9

В

3

2

13

Цена, д.е.

3

4

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

Построение математической модели задачи

Предположим, что предприятие изготовит

Xj - единиц продукции П{ и

х2 - единиц продукции П2.

Тогда должны выполняться следующие неравенства:

  • 2х, 4-3x2 <9;
  • 3xj 4-2x2 <13;

Х| - х2 < 1; (6)

х2 <2;

х, >0;

х2 > 0.

Доход от реализации Xj единиц продукции П{ и единиц продукции П2 составит

Z = 3xj + 4x2 max. (7)

Решение.

Построим многоугольник решений (рис.5). Для этого в системе координат XjOX2 на плоскости изобразим граничные прямые:

1+Зх2=9 (Ц);

ЗХ] +2xj = 13 (Lj);

Xi-X2 =1 (Ц);

х2 =2 (L4).

Для построения прямой Z = 3х1 + 4х2 = 0 строим вектор - градиент С = (3;4) и через точку 0 проводим прямую, перпендикулярную ему.

Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора С. Из рис. 5 следует, что по отношению к многоугольнику решений опорной эта прямая становится в точке С, где функция принимает максимальное значение. Точка С лежит на пересечении прямых L, и L,. Для определения ее координат решим систему уравнений:

2х!+Зх2=9; [5x2=7;

I =>

х, — х2 = 1. 15х} =12.

Оптимальный план задачи Xj = 2,4; х2 = 1Л- Подставляя значения и х2 в линейную функцию, получим:

Zmax =3-2,4 + 4-1,4 = 12,8.

Полученное решение означает, что объем производства продукции Пх должен быть равен 2,4 ед., а продукции Пх - 1,4 ед. Доход, получаемый в этом случае, составит: Z =12,8 д. е.

Задания для решения в аудитории

1. Производственному участку может быть запланировано к изготовлению на определённый плановый период времени два вида изделий: А и В . На производство единицы изделия А оборудование первого типа используется 1 час, оборудование второго типа - 4 часа. На производство единицы изделия В оборудование первого типа используется 2 часа, оборудование второго типа - 2 часа.

Фонд полезного времени первого типа оборудования составляет 120 часов, второго типа оборудования - 240 часов. Отпускная цена единицы изделия А составляет 4 руб., а изделия В - 6 руб.

Спланировать выпуск изделий А и В при условии, что план должен быть выполнен в стоимостном выражении на сумму не менее 320 руб. и оборудование первого типа должно быть загружено минимально.

Решить задачу графическим методом.

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

Компоненты

Расход компонента на единицу продукции

Запасы компонентов

А

в

1

1

2

6

2

2

1

8

3

0

1

2

Прибыль

3

2

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

Питательные вещества

Содержание питательного вещества в единице корма

Необходимое количество питательных веществ

А

В

1

2

1

12

2

1

1

10

3

2

3

24

Цена

60

60

4. Леспромхоз, имеющий лесопильный и фанерный цеха, столкнулся с проблемой наиболее рационального использования выделенной лесосеки. Чтобы получить 2,5 м3 коммерчески реализуемых комплектов пиломатериалов, необходимо израсходовать 2,5 м3 еловых и 7,5 м3 пихтовой древесины. Для изготовления 100 м2 фанеры требуется 5 м3 еловых и 10 м3 пихтовой древесины. Выделенная лесосека содержит 80 м3 еловых и 180 м3 пихтовой древесины. Согласно условиям поставок, в течение планируемого периода необходимо произвести по крайней мере 10 м3 пиломатериалов и 1200 м2 фанеры. Доход с 1 м3 пиломатериалов составляет 80000 руб., а со 100 м2 фанеры - 300000 руб. Составить план выпуска продукции, обеспечивающий максимальную прибыль, решить задачу графически.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >