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

Государственное образовательное учреждение высшего  профессионального образования 

«Уральский  государственный экономический  университет»

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

Контрольная работа 

по математическому  программированию

Вариант 7 

                                  
 
 
 
 
 
 
 
 
 
 
 

                                Преподаватель: Петрова С.Н. 

   Студент: Полукеева Оксана Александровна,

                                                                 Экономика- правовая безопасность предприятия,

                                       ЭПБ-09 ЕК

  
 
 
 
 

Екатеринбург 

2010г.

     Задача  1

     Макаронная  фабрика производит два вида изделий  А и В, используя три вида сырья: муку, яйца, соль. Общие запасы каждого вида сырья соответственно равны 3000, 252, 120 усл. ед. Норма расхода сырья на единицу веса изделия А – 120; 3; 4 усл. ед., на единицу веса изделий В – 40; 12; 4 усл. ед. Составить план производства, обеспечивающий максимальную прибыль, если единица веса изделий А дает прибыль 300 р., а В – 400 р.:

     а) записать математическую модель;

     б) решить задачу графическим методом;

     в) решить задачу симплекс-методом;

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

     Решение

     а) Составим экономико-математическую модель задачи.

     Обозначим - количество изделий А и Б, запланированных к производству. Для их изготовления (табл.1) потребуется ( ) усл. ед. муки, ( ) усл. ед. яиц, ( ) усл. ед. соли. Суммарная прибыль составит руб. от реализации изделий вида А, руб. от реализации изделий Б. Тогда математическая модель задачи имеет вид:

     

     б) Найдем оптимальный план задачи графическим методом.

     Для того чтобы найти оптимальное  решение ЗЛП графическим методом, построим в прямоугольной системе координат прямые, соответствующие каждому неравенству системы ограничений (рис. 1):

     Прямую  I построим по точкам (0; 75), (25;0)

     Прямую  II построим по точкам (0;21), (84;0)

     Прямую  III построим по точкам (0;30), (30;0)

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

     Для всех прямых в качестве контрольной  точки возьмем точку с координатами (0;0).

     

     На  рис.1 выбранные полуплоскости обозначены стрелками. В результате получили многоугольник допустимых решений АВСDE.

     

     Рис. 1. Графическое решение задачи

     Направление вектора нормали  показывает направление возрастания целевой функции. Следовательно, по направлению целевая функция возрастает. В точке C целевая функция принимает максимальное значение. Найдем координаты точки С, как пересечение прямых II и III. 

     

     Найдем  значение целевой функции в этой точке:

     

     Таким образом, максимальная прибыль составляет усл.ед. при производстве изделий А в количестве 12 ед., изделий В в количестве 18 ед. 

     в) Найдем решение исходной задачи симплекс-методом. Для этого приведем систему ограничений к каноническому виду. В результате получим задачу линейного программирования:

     

     Система ограничений содержит базисные переменные.

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

     

     Составим  исходную симплекс-таблицу (табл.1).

     Столбцы А₁,…, А₅ содержат коэффициенты при соответствующих переменных системы ограничений. Столбец А_б содержит вектора, соответствующие базисным переменным. Столбец В содержит первоначальный опорный план задачи. Столбец С_б содержит коэффициенты целевой функции при соответствующих переменных.

     Таблица 1

 

     Рассчитаем  оценки свободных переменных по формуле:

     

     где - коэффициенты целевой функции.

     Например, оценка столбца А₁ равна:

     

     Т.к. все оценки свободных переменных отрицательные, то критерий оптимальности не выполняется. Из этих оценок выбираем максимальную по абсолютной величине. Эта оценка соответствует вектору А₂: . Столбец А₂ направляющий, в базис вводится переменная . Найдем переменную, исключаемую из базиса. Для этого находим минимальное из отношений элементов столбца В к элементам направляющего столбца А₂:

     

     Значит, строка А₄ является направляющей, переменная   исключается из базиса. Элемент, стоящий на пересечении направляющего столбца и направляющей строки называется разрешающим. Разрешающий элемент равен 12. С учетом этого строим новую симплекс-таблицу. В столбце А_б записываем вместо вектора A₄ вектор A₂. Все элементы строки A₂ получаются следующим образом: все элементы строки A₄ делят на разрешающий элемент:

     

     и т.д.

     Все остальные элементы пересчитывают  по правилу прямоугольника:

     В результате получим табл. 2

     Таблица 2

 

     Критерий оптимальности не выполняется. Отрицательная оценка соответствует вектору А₁. Столбец А₁ направляющий, в базис вводится переменная . Найдем переменную, исключаемую из базиса. Для этого находим минимальное из отношений элементов столбца В к элементам направляющего столбца А₁:

     

     Значит, строка А₅ является направляющей, переменная   исключается из базиса. Элемент, стоящий на пересечении направляющего столбца и направляющей строки называется разрешающим. Разрешающий элемент равен 3. С учетом этого строим новую симплекс-таблицу (табл.3).

     Таблица 3

 

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

     

     

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

     Для этого используем правила построения симметричных двойственных задач. Ставим в соответствие каждому неравенству системы ограничений исходной задачи новую переменную: