АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  2. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  3. I. Ситуационные задачи и тестовые задания.
  4. II. Основные задачи и функции
  5. II. ЦЕЛИ, ЗАДАЧИ И ПРИНЦИПЫ ДЕЯТЕЛЬНОСТИ ВОИ
  6. II. Цель и задачи государственной политики в области развития инновационной системы
  7. III. Цели и задачи социально-экономического развития Республики Карелия на среднесрочную перспективу (2012-2017 годы)
  8. VI. ДАЛЬНЕЙШИЕ ЗАДАЧИ И ПУТИ ИССЛЕДОВАНИЯ
  9. Анализ и интерпретация результатов.
  10. Анализ спинномозговой жидкости и ее клиническая интерпретация.
  11. Аналитические возможности, задачи и основные направления анализа СНС
  12. БАЛАНС КОММЕРЧЕСКОГО БАНКА, ЦЕЛИ И ЗАДАЧИ ЕГО АНАЛИЗА

Каждой паре чисел х1 и х2 поставим в соответствие точку плоскости (2-мерного пространства) с координатами х1 и х2, тогда каждое ограничение (П.1) задает полупространство, а вся система (П.1) определяет многоугольник (в n-мерном пространстве – многогранник), полученный в результате их пересечения. В общем случае многогранник может быть неограниченным или пустым (система неравенств противоречива).

В примере П.1 множество допустимых планов соответствует на плоскости множеству точек многоугольника OABCD (рис. П.1.).

Целевая функция F=5х1 + 6х2 определяет на плоскости семейство прямых линий (в n-мерном пространстве – плоскостей), параллельных друг другу, причем, чем дальше прямая от точки О, тем большее значение принимает целевая функция. Таким образом, оптимальное решение будет в точке многоугольника OABCD, где целевая функция касается этого многоугольника при удалении от точки О.

х2                            
11 (I)                          
10                            
9                            
8                            
7F                            
6         n                  
5A   B                        
4                            
3 n2     C         (III)          
2             (II)              
1 n1 2 3 4 5 D 6 7 8 9 10 11 12 14 15

O Рис.П.1. Графическое представление задачи П.1. х1

 

В нашем примере это будет вершина многоугольника С с координатами (примерно) х1=4.5; х2=3. Для точного определения координат точки С рассмотрим уравнения прямых, пересечение которых ее образовало.

Получаем систему из двух уравнений:

2х1 + 1х2 = 12,

2х1 + 3х2 = 18,

решив которую получим точные значения х1=4.5; х2=3.

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

Напомним кратко его суть:

Для решения системы

a11 х1 + a12 х2 = b1,

a21 х1 + a22 х2 = b2,

вычисляем D = a11 a22 - a12 a21,

D1 = b1a22 - a12 b2,

D2 = a11 b2 - b1a21,

и затем х1 = D1 / D; х2 = D2 / D.

В нашем примере: D=2´3 – 1´2 = 4,

D1 = 12´3 – 1´18 = 18,

D2 = 2 ´18 – 12 ´2 = 12,

откуда х1 = 18/4 = 4.5, х2 = 12/4 = 3 (совпало с первоначальным приближением).

Вычислим значение целевой функции в точке С:

F = 5 ´ 4.5 + 6 ´3 = 40.5.

Таким образом мы решили поставленную задачу, нашли объемы производства х1 первого и х2 второго вида продукции, удовлетворяющие ограничениям (П.1) и доставляющие максимальное значение целевой функции F = 40.5 усл.ед.

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

Таблица П.2

Виды кормов Содержание в 1 кг Себестоимость 1 кг (усл. ед).
Кормовых ед. Белок (г) Кальций (г)
Сено (х1) 0.5 1.5
Концентраты (х2) 2.5
Норматив  

Под нормативом понимается необходимый минимум питательных веществ суточного рациона. В этой задаче необходимо найти такие объемы кормов х1, х2 , чтобы обеспечить содержание в них кормовых единиц, белка и кальция не менее нормативного при минимальной стоимости. Опять же предполагая, что количество полезных веществ, а также стоимость пропорциональны объемам кормов, получаем следующую математическую модель задачи:

(I) 0.5 х1 + 1х2 ³ 20

(II) 50 х1 + 200 х2 ³ 2000

(III) 10 х1 + 2 х2 ³ 100 (П.2)

х1 ³ 0, х2 ³ 0,

F=1.5 х1 + 2.5 х2® min.

Геометрическую интерпретацию данной задачи приведем на рис.П.2.

 

х2                            
50                            
A                            
(II)                            
40                            
35                            
30                            
F   n                        
20 B                          
(III)                            
10         (I)                  
5             C              

5 10 15 20 25 30 35 40 х1

Рис.П.2. Графическое представление задачи П.2

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

Целевая функция принимает наименьшее значение в точке В.

Визуально на графике координаты этой точки х1 @ 7, х2 @ 17.

Сделаем аналитическую проверку:

D=0.5´2 – 1´10 = –9,

D1 = 20´2 – 1´100 = –60,

D2 = 0.5 ´100 – 20 ´10 = –150.

Откуда х1 = –60 / –9 = 6.67, х2 = –150 / –9 = 16.67.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |

Поиск по сайту:



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