Автор работы: Пользователь скрыл имя, 02 Октября 2011 в 13:19, контрольная работа
решение задач по математическому программированию
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение высшего профессионального образования
ЦЕНТР
ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ
Контрольная
работа
по математическому программированию
Вариант
7
Студент: Полукеева Оксана
Екатеринбург
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)
Найдем полуплоскость решения каждого неравенства. Для этого выберем любую контрольную точку и подставим в неравенство. Если неравенство верно, но необходимо выбрать полуплоскость, в которой содержится контрольная точка.
Для
всех прямых в качестве контрольной
точки возьмем точку с
На
рис.1 выбранные полуплоскости
Рис. 1. Графическое решение задачи
Направление
вектора нормали
показывает направление возрастания
целевой функции. Следовательно, по направлению
целевая функция возрастает. В точке C
целевая функция принимает максимальное
значение. Найдем координаты точки С, как
пересечение прямых II и III.
Найдем значение целевой функции в этой точке:
Таким
образом, максимальная прибыль составляет
усл.ед. при производстве изделий А
в количестве 12 ед., изделий В в количестве
18 ед.
в) Найдем решение исходной задачи симплекс-методом. Для этого приведем систему ограничений к каноническому виду. В результате получим задачу линейного программирования:
Система ограничений содержит базисные переменные.
Построим первоначальный опорный план. Для этого свободные переменные приравняем к нулю и вычислим базисные переменные . Первоначальный опорный план имеет вид:
Составим исходную симплекс-таблицу (табл.1).
Столбцы А1,…, А5 содержат коэффициенты при соответствующих переменных системы ограничений. Столбец Аб содержит вектора, соответствующие базисным переменным. Столбец В содержит первоначальный опорный план задачи. Столбец Сб содержит коэффициенты целевой функции при соответствующих переменных.
Таблица 1
Aб | Сб | В | 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
|
Критерий оптимальности не выполняется. Отрицательная оценка соответствует вектору А1. Столбец А1 направляющий, в базис вводится переменная . Найдем переменную, исключаемую из базиса. Для этого находим минимальное из отношений элементов столбца В к элементам направляющего столбца А1:
Значит, строка А5 является направляющей, переменная исключается из базиса. Элемент, стоящий на пересечении направляющего столбца и направляющей строки называется разрешающим. Разрешающий элемент равен 3. С учетом этого строим новую симплекс-таблицу (табл.3).
Таблица 3
Aб | Сб | В | 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 |
Отрицательных оценок нет, значит, полученный план является оптимальным планом. В столбце В найден оптимальный план:
г) к исходной задаче запишем двойственную и решим ее, используя соотношение двойственности и решение исходной.
Для этого используем правила построения симметричных двойственных задач. Ставим в соответствие каждому неравенству системы ограничений исходной задачи новую переменную:
Информация о работе Контрольная работа по "Математическое программирование"