Содержание
1 Составить экономико-математическую модель 2
2 Решить симплексным методом, составить задачи, двойственные данным, и найти их решения, используя теоремы двойственности 4
Список литературы 8
1
Составить экономико-математическую модель
На двух автоматических линиях выпускают аппараты трех типов. Другие условия задачи приведены в таблице.
Таблица 1
Тип аппарата
Производительность работы линий, шт. в сутки
Затраты на работу линий, ден. ед. в сутки
План, шт.
1
2
1
2
А
4
3
400
300
50
В
6
5
100
200
40
С
8
2
300
400
50
Составить такой план загрузки станков, чтобы затраты были минимальными, а задание выполнено не более чем за 10 суток.
Решение.
Решение задачи начнём с допущения, что неизвестная xА1 обозначает количество суток работы линии 1 по выпуску аппаратов А, xА2 ? количество суток работы линии 2 по выпуску аппаратов А и так далее... Тогда получаем, что затраты на данном предприятии, согласно заданным в табл. 1 определяются зависимостью
400 xА1+300 xА2+100 xВ1+ 200xВ2+300 xС1+400 xС2
При этом затраты должны быть минимальными.
Существует плановое задание, поэтому составляем систему органичений:
4 xА1+3 xА2?50
6 xВ1+ 5xВ2?40
8 xС1+ 2 xС2?50
Так как задание выполнено не более чем за 10 суток:
xА1+ xВ1+ xС1?10
xА2+ xВ2+ xС2?10
Кроме того, поскольку количество дней работы линии не может быть отрицательной величиной, естественно потребовать, чтобы выполнялись неравенства
xА1 ? 0; xВ1 ? 0; xС1 ? 0.
xА2 ? 0; xВ2 ? 0; xС2 ? 0.
Решение задачи оптимизации заключается в нахождении такого плана работы линий, который обеспечивают функции издержек минимальное значение при заданных ограничениях по количеству дней выполнения плана при условии полного выполнения и перевыполнения плана. Каждое из решений системы неравенств будет допустимым решением (планом) для данной задачи. Оптимальным решением называется то из допустимых решений, при котором целевая функция имеет минимальное значение. В разных задачах оптимальных решений может быть как множество, так и не быть вообще, или может существовать единственное оптимальное решение (план).
Таким образом, объединяя составленные по данным задания зависимости, получаем математическую модель задачи:
F(X ) =400 xА1+300 xА2+100 xВ1+ 200xВ2+300 xС1+400 xС2> min
4 xА1+3 xА2?50
6 xВ1+ 5xВ2?40
8 xС1+ 2 xС2?50
xА1+ xВ1+ xС1?10
xА2+ xВ2+ xС2?10
xА1 ? 0; xВ1 ? 0; xС1 ? 0.
xА2 ? 0; xВ2 ? 0; xС2 ? 0.
2
Решить симплексным методом, составить задачи, двойственные данным, и найти их решения, используя теоремы двойственности
Z= 10y2-3y3>min
при ограничениях:
-2y1+ y2- y3?1
-y1+ 2y2- y3?3
y1?0; y2?0; y3?0;
Составим двойственную задачу. Используем общие правила составления двойственных задач. Связь исходной и двойственной задач состоит в том, что коэффициенты целевой функции исходной задачи являются свободными членами системы ограничений двойственной задачи, свободные члены системы ограничений исходной задачи служат коэффициентами целевой функции двойственной задачи, а матрица коэффициентов системы ограничений двойственной задачи является транспонированной матрицей коэффициентов системы ограничений двойственной задачи. Сопряженная задача примет вид:
максимизировать
х1 +3х2 >max
при условиях
-2х1-х2?0
х1+2х2?10
-х1-х2?-3
х 1?0; х 2?0
Решим задачу симплекс-методом.
Приводим задачу к каноническому виду. Поскольку ограничения задачи являются неравенствами "с недостатком", введём дополнительные вспомогательные переменные x3, x4, x5 которые называют "выравнивающими", и с помощью них превратим неравенства в равенства. Для этого в левую часть ограничения-неравенства типа "меньше или равно" вводим дополнительную переменную xi с коэффициентом +1. В целевую функцию переменная xi входит с коэффициентом 0 (т.е. не входит). Получаем:
х1 +3х2 +0* x3+0* x4+0* x5>max
-2х1-х2+ x3 =0
х1+2х2+ x4 =10
-х1-х2 + x5=-3
х 1?0; х 2=0
Метод Жордана ? Гаусса ? это метод нахождения базисных решений систем m линейных алгебраических уравнений относительно n неизвестных, если n? m, в специальных таблицах, позволяющих в ходе решения замещать базисный элемент одним из свободных переменных. Среди найденных базисных решений могут быть и вырожденные, то есть такие, в которых значение базисной переменной равно нулю.
В качестве первого базиса берём систему векторов (x3 , x4 , x5), и соответствующий базисный вектор имеет нулевые координаты, поскольку коэффициенты целевой функции при соответствующих переменных равны:
C1 = 1; C2 = 3; C3 = 0; C4 = 0; C5 = 0.
При решении системы и нахождении того её базисного решения, которое обеспечивает максимум рассматриваемой функции прибыли (целевой функции) Z , использованы критерии симплексного метода для задач линейного программирования.