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

Графическое решение

Читайте также:
  1. I. Решение логических задач средствами алгебры логики
  2. I.5.4. Решение задачи линейного программирования
  3. II этап: Решение задачи на ЭВМ в среде MS Excel
  4. II этап: Решение задачи на ЭВМ в среде MS Excel
  5. II этап: Решение задачи на ЭВМ в среде MS Excel
  6. II этап: Решение задачи на ЭВМ средствами пакета Excel
  7. II. Решение логических задач табличным способом
  8. II.1.3. Решение транспортной задачи в QSB
  9. III. Разрешение споров в международных организациях.
  10. III. Решение логических задач с помощью рассуждений
  11. IV. Воскрешение мертвых
  12. MatLab: решение дифференциальных уравнений

Составляем ЗЛП по условиям задачи. Обозначим за x1 – объем производства продукции А, за x2 – объем производства продукции В. Тогда целевая функция F, отображающая стоимость всей произведенной продукции, может быть записана как

F=7,5x1+3x2®max.

Ограничения по ресурсам запишутся в виде неравенств

2x1+x2£150

x1+5x2£200

3x1 £200

при x1,x2³0

Рассчитаем точки для построения прямых ограничений (рис. 2.2).

2x1+x2=150 x1+5x2=200 3x1=200

 

x1 x2 x1 x2 x1 x2
        66,6  
        66,6  

 

Рис. 2.2. Расчет точек для построения линий ограничений

Граничные условия (неотрицательность переменных x1 и x2) определяются первым координатным углом. Поскольку знаки всех неравенств меньше или равно (при положительном коэффициенте при x2), то область под графиками всех прямых ограничений и ограниченная осями координат есть ОДР данной задачи.

 

 

Строим прямую нулевого уровня целевой функции 7,5x1+3x2 =0 (рис. 2.3).

7,5x1+3x2=0
x1 x2
   
-4  

Рис. 2.3. Расчет точек линии нулевого уровня целевой функции

Переносим линию целевой функции во все вершины ОДР и определяем точку, в которой она проходит выше, чем в других (рис. 2.4).

 
 

 

 


Рис. 2.4. Графическое решение ЗЛП

 

Это точка пересечения прямых, заданных уравнениями 2x1+x2=150 и 3x1=200. Решив систему из этих уравнений, получаем координаты этой точки x1= и x2=. Это значит что для оптимального решения нужно выпустить 66,66 кг продукции А и 16,66 кг продукции В. Стоимость произведенной продукции равна

F=7,5×66,66+3×16,66= 594,98 руб.

и показывает максимально возможную прибыль при данных условиях.

Решение ЗЛП симплекс-методом с использованием симплекс таблиц

 

 

Приводим общую ЗЛП

F=7,5x1+3x2®max

2x1+x2£150

x1+5x2£200

3x1 £200

при x1,x2³0

к каноническому виду, добавляя в левые части неравенств дополнительные переменные

F=7,5x1+3x2®max

2x1+x2+x3=150

x1+5x2 + x4=200

3x1 + x5 =200

при xi³0, i=1…5

и записываем ее в виде 0-уравнений

F=0 – (–7,5x1 – 3x2)

x3=150 – (2x1+x2)

x4=200 – (x1+5x2)

x5 =200 – (3x1)

Заполняем первую симплекс-таблицу (рис. 2.5).

Базисные переменные Вектор свободных членов Переменные ЗЛП
x1 x2 x3 x4 x5
x3            
x4            
x5            
Индексы в целевой функции     -7,5   -3      

Рис. 2.5. Первая симплекс-таблица ЗЛП

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

Ищем разрешающий столбец. Максимальное по модулю из отрицательных значений это –7,5. Оно определяет разрешающий столбец таблицы x1 (в новой таблице эта переменная перейдет в базис).

Для нахождения разрешающей строки таблицы составляем отношения элементов столбца свободных членов к элементам разрешающего столбца и находим из них наименьшее

min (150/2, 200/1,200/3)=200/3=66,6.

Это значение определяет разрешающую строку таблицы x5.

Разрешающий элемент таблицы находится на пересечении разрешающего столбца и разрешающей строки (x5./ x1) и равен 3.

Переходим к новой симплексной таблице.

В ней вместо переменной x5 в базисе появилась переменная x1. Строка, соответствующая новой базисной переменной в новой таблице, получается из разрешающей строки предыдущей таблицы делением ее элементов на разрешающий элемент, равный 3.

Другие строки вычисляются согласно пункту 11 приведенного выше алгоритма симплекс-метода. Например, элемент на пересечении строки x3 и столбца свободных членов равен

150 – (200×2)/3,

элемент на пересечении строки x3и столбца x1 равен соответственно

1 – (2×0)/3 и т.д.

Вторая симлекс-таблица имеет вид (рис. 2.6):

Базисные переменные Вектор свободных членов Переменные ЗЛП
x1 x2 x3 x4 x5
x3 16,66         -0,66
x4 133,33         -0,66
x1 66,66         0,33
Индексы в целевой функции       -3       2,5

 

 

Рис. 2.6. Вторая симплекс таблица ЗЛП

Этот план тоже не оптимальный – в индексной строке есть отрицательное значение. Повторяем алгоритм снова и в результате получаем третью таблицу (рис. 2.7).

 

 

Базисные переменные Вектор свободных членов Переменные ЗЛП
x1 x2 x3 x4 x5
x2 16,66         -0,66
x4 50,03     -5   2,64
x1 66,66         0,33
Индексы в целевой функции   594,98           0,52

Рис. 2.7. Оптимальный план решения ЗЛП

Этот план оптимален. Значения базисных переменных x1 и x2 равны соответственно 66,66 и 16,66, значения добавленных переменных x3 и x4 равно 0. Значение целевой функции равно 594,98. Полученное симплекс-методом решение ЗЛП полностью совпадает с решением задачи, полученным графически.

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |

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



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