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

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

а) найти  область допустимых значений (многоугольник  решений);

б) найти  оптимум целевой функции.

max и min Z = 4х₁ + 5х₂

                  5х₁ + 3х₂ £ 75

                  4х₁ + 7х₂ £ 83

                  х₁ + 5х₂ £ 50

                 

     Решение задачи:

    Структура всех трёх ограничений одинакова 

    Перейдём  из неравенств к уравнениям

 
 
 
 
 
 
 

    Построим  прямые на плоскости 

    

    Многоугольник решений  .

    Для нахождения максимума функции  построим начальную прямую и вектор .

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

    

     . 

 

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

max f (X) = 4*x1+5*x2+6*x3

4*x1+5*x2+6*x3<=2000 
8*x1+6*x2+4*x3<=1770 
6*x1+4*x2+5*x3<=1600

x1,x2,x3 >=0/

     Решение задачи:

Математическая  модель задачи:

     Целевая функция:

max f (X) = 4*x1+5*x2+6*x3

     Система ограничений:

4*x1+5*x2+6*x3<=2000  
8*x1+6*x2+4*x3<=1770  
6*x1+4*x2+5*x3<=1600

x1,x2,x3, >=0; - условие неотрицательности переменных. 

Приведем  систему неравенств к каноническому  виду:

     Целевая функция:

max f (X) = 4*x1+5*x2+6*x3+0*x4+0*x5+0*x6

     Система ограничений:

4*x1+5*x2+6*x3+x4=2000  
8*x1+6*x2+4*x3+x5=1770  
6*x1+4*x2+5*x3+x6=1600  

Векторный анализ системы ограничений:

     Расширенная целевая функция:

max f (X) = 4*x1+5*x2+6*x3+0*x4+0*x5+0*x6 

     Вектора:

     Базис: 
Базисный вектор №1: P4(x4) 
Базисный вектор №2: P5(x5) 
Базисный вектор №3: P6(x6)

     Расширенная целевая функция: 
max f (X) = 4*x1+5*x2+6*x3+0*x4+0*x5+0*x6

     Заполним  первую таблицу:

     Таблица №1

 
Замещаемый  базисный вектор: P6 (3-я строка)  
Новый базисный вектор: P3 (3-й столбец)  
Заменяем базисный вектор P6 на P3.  
  
 
 
 

Таблица №2

 
Замещаемый базисный вектор: P5 (2-я строка)  
Новый базисный вектор: P2 (2-й столбец)  
Заменяем базисный вектор P5 на P2.  
 Таблица №3

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

     Из  таблицы получим значения переменных целевой функции:

 
  Целевая функция:  
max f (X) = 4*0+5*175+6*180  
 И в результате:  
max f (X) = 1955. 
 
 3. Решить венгерским методом задачу о назначении шести кандидатов на шесть должностей, при котором суммарные затраты по времени на выполнение работ минимальны. Таблица времени выполнения конкретной работы (по столбцам) конкретным кандидатом (по строкам) .

 

n = 6. 

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

     1. В каждой строке найти наименьшее  значение и вычесть его из  содержимого всех ячеек этой  строки матрицы. (Получится по  крайней мере один нуль в  каждой строке.)

 

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