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

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

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

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

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

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

Вариант 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

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

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

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

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

     Найдем  решение двойственной задачи.

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

     Подставим (оптимальный план исходной задачи) в ограничения исходной задачи и получим:

     Тогда

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

     Задача  2

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

     Требуется составить такой план перевозок, при котором их общая стоимость окажется минимальной.

     Решить  транспортную задачу методом потенциалов. 

     Решение

     Т.к. выполняется условие баланса: , а , то данная транспортная задача является закрытой.

     Найдем  опорное решение с помощью  метода минимальной стоимости (табл. 4).

     Находим наименьшую стоимость  . Сравниваем запасы и потребности, распределяем груз. Вычеркиваем из рассмотрения 2 столбец. Снова находим наименьшую стоимость и т.д.

     Таблица 4

     Транспортные  расходы составляют:

     Проверим  полученный опорный план на оптимальность  с помощью метода потенциалов.

     Построим  систему потенциалов:

     Найдем  оценки каждой свободной клетки:

       и т.д.

     В результате получим (табл. 5):

     Таблица 5

     Т.к. имеются положительные оценки, план не является оптимальным. Выбираем максимальную из положительных. Поэтому строим цикл, начиная с клетки (3,1). . Учитывая это, получим табл. 6.

     Таблица 6

     Положительный оценок нет, поэтому план является оптимальным. Минимальные транспортные расходы составляют:

     План  перевозок имеет вид: