Контрольная работа по "Математическое программирование"

Автор работы: Пользователь скрыл имя, 02 Октября 2011 в 13:19, контрольная работа

Описание

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

Работа состоит из  1 файл

Математическое программирование контрольная работа.doc

— 330.50 Кб (Скачать документ)

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

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

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

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

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

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

Вариант 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,…, А5 содержат коэффициенты при соответствующих переменных системы ограничений. Столбец Аб содержит вектора, соответствующие базисным переменным. Столбец В содержит первоначальный опорный план задачи. Столбец Сб содержит коэффициенты целевой функции при соответствующих переменных.

     Таблица 1

Сб В 300 400 0 0 0
A1 A2 A3 A4 A5
A3 0 3000 120 40 1 0 0
A4 0 252 3 12 0 1 0
A5 0 120 4 4 0 0 1
m+1   0 -300 -400 0 0 0
 

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

     

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

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

     

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

     

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

     

     и т.д.

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

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

     Таблица 2

Сб В 300 400 0 0 0
A1 A2 A3 A4 A5
A3 0 2160 110 0 1 -3 1/3 0
A2 400 21 1/4 1 0 0 0
A5 0 36 3 0 0 - 1/3 1
m+1   8400 -200 0 0 33 1/3 0
 

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

     

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

     Таблица 3

Сб В 300 400 0 0 0
A1 A2 A3 A4 A5
A3 0 840 0 0 1 8  8/9 -36  2/3
A2 400 18 0 1 0   1/9 -  1/12
A1 300 12 1 0 0 -  1/9   1/3
m+1   10800 0 0 0 11  1/9 66  2/3
 

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

     

     

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

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

Информация о работе Контрольная работа по "Математическое программирование"