РОССИЙСКАЯ ФЕДЕРАЦИЯ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

ИНСТИТУТ ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ

СПЕЦИАЛЬНОСТЬ «Менеджмент организаций » К О Н Т Р О Л Ь Н А Я Р А Б О Т А

По предмету: Экономико-математический практикум

 

Выполнил:

Студент 2 курса

4 семестр

Рахимова Лидия Рустамовна

Ташкент,2009

Задача № 1

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

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

1. Найти оптимальный план прямой задачи:

а) графическим методом;

б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).

2. Построить двойственную задачу.

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

4. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».

5. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, который был получен графическим методом (см. п. 1а).

6. Найти оптимальное целочисленное решение:

а) графическим методом;

б) Методом Гомори.

Сравнить значения функций целочисленного и нецелочисленного решений

4

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

1. Найдем оптимальный план решения графическим методом:

;

Построим на координатной плоскости Ох1х2 граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе):

  

Область допустимых решений определяется многоугольником ОАВСD (см. график 1).

Для линий уровня х1 - 3х2 = h (h — const) строим нормальный вектор . Перпендикулярно нормальному вектору построим одну из линий уровня (на рис. 1 она проходит через начало координат) Так как задача на минимум, то перемещаем линию уровня в направлении вектора  до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L3 и L4, т. е. через точку . Для определения координат точки P решаем систему уравнений

.

Получаем х1 = 5,3, х2 = 0,6. Это и будет оптимальным решением данной задачи, которому соответствует минимальное значение целевой функции Zmin=3,5

 
    
    
    

    
      

    
    
    

    
        

    
    
    

    
         

    
    
    

    
        

    
    
    

    
        

 

    
    
    

    
      
    
    
    
    
      
    
    
    
    
      

График № 1

1б) Перейдем к расширенной задаче:

Данная расширенная задача имеет начальное опорное решение  с базисом . ............