«Основная задача линейного программирования. Область допустимых значений.» - Контрольная работа

1.3 Обоснование и описание вычислительной процедуры решения задачи 7
1.4 Решение задачи оптимизации аналитически 7
2 Технологическая часть 13
Заключение 14

1.2. Планирование — моделирование производства во времени 10
1.3. Новые возможности в решении задач планирования 13
1.4. Представление моделей планов 15
1.5. Графики Ганта 17
1.6. Сетевые графики 19
1.7. Математический аппарат решения задач планирования 22
1.8. Модели линейного программирования 23
1.9. Последовательные методы оптимизации 27
1.10. Методы моделирования 28
1.11. Персональный компьютер и решение задач планирования 29
2. ОПТИМИЗАЦИОННАЯ ЗАДАЧА. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 31
2.1. Оптимизационные задачи 31
2.2. Задача линейного программирования 33
2.3. Симплекс – метод (решение ЗЛП) 35
2.4. Метод искусственного базиса 43
2.5. Двойственные ЗЛП 47
3. ЧИСЛЕННАЯ РЕАЛИЗАЦИЯ ЗАДАЧИ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ ОБЪЕМА РАБОТ НА ПРЕДПРИЯТИИ 51
3.1. Постановка задачи 51
3.2. Выявление основных особенностей, взаимосвязей и количественных закономерностей 51
3.3. Построение математической модели 52
3.4. Решение задачи симплекс-методом 53
ЗАКЛЮЧЕНИЕ 58
ЛИТЕРАТУРА 59

Сущность метода линейного программирования 7
Область применения метода линейного программирования 9
Постановка задачи линейного программирования 11
Математический вид экономической задачи линейного программирования 12
Выводы 13
3. Использование метода линейного программирования на практике 15
задача об определении оптимального ассортимента продукции 15
Использование метода линейного программирования при работе со слабоструктурированными системами 18
выводы 21
4. Заключение 22
Источники 24

11) f(x )=x1x2max,
x1,x20,
1x1+x22,
2x12x23,
2x1+3x22.
Построим множество, ограниченное прямыми 1=x1+x2, x1+x2=2,
2=x12x2, x12x2=3, 2x1+3x2=2.

Данное множество не пересекает первую координатную четверть ни в одной точке, значит данная задача не имеет решения.
f(x )=x1x2max,
x1,x20,
-x1-x2-1
x1+x22,
x12x23,
-x1+2x2-2
2x1+3x22.
Формулировка двойственной задачи:
G(y)=-y1 +2y2+3 y3-2 y4+2 y5 min,
y1,y2, y3, y4, y5 0,
-y1 +y2+ y3- y4+2 y5 1,
-y1 +y2-2 y3+2 y4+3 y5 -1.
По теореме о дополняющей нежесткости получаем, что двойственная задача не имеет решения, т.к. если бы существовало решение двойственной задачи, то по нему можно было бы восстановить, исходя из теоремы, решение прямой задачи, а его нет.
> with(simplex);
> maximize(x1-x2,{x1+x2>=1,x1+x2<=2,x1-2*x2>=2,x1-2*x2<=3,2*x1+3*x2<=2},NONNEGATIVE);

7) f=x1-x2max,
x1,x20,
x1+x21,
x1-2x22,
2x1+3x22,
3x1+2x23,
x1+x21/2.
> inequal({y1>=0,y2>=0,y1+y2<=1,y1-2*y2<=1,2*y1+3*y2<=2,3*y1+2*y2<=3,y1+y2>=1/2},y1=-0.5.2,y2=0.1,optionsfeasible=(color=red),optionsopen=(color=blue,thickness=2),optionsclosed=(color=black,thickness=2),optionsexcluded=(color=white));

> with(simplex);maximize(x1-x2,{x1>=0,x2>=0,x1+x2<=1,x1-2*x2<=1,2*x1+3*x2<=2,3*x1+2*x2<=3,x1+x2>=1/2});

f=x1-x2max,
x1,x20,
x1+x21,
x1-2x21,
2x1+3x22,
3x1+2x23,
-x1-x2-1/2.
Формулировка двойственной задачи:
G(y)=y1 +y2+2 y3+3 y4-1/2 y5 min,
y1,y2, y3, y4, y5 0,
y1 +y2+2y3+3y4- y5 1,
y1 -2y2+3y3+2y4-y5 -1.
По теореме о дополняющей нежесткости получаем:
1(y1 +y2+2y3+3y4- y5-1)=0,
0 (y1 -2y2+3y3+2y4-y5 +1)=0,
y1(1-1)=0,
y2(1-1)=0,
y3(2-2)=0,
y4(3-3)=0,
y5(-1+1/2)=0.
Решение системы: бесконечное множество оптимальных планов;y5=0.
> minimize(y1+2*y2+3*y3+y4-1/2*y5, {y1>=0,y2>=0,y3>=0,y4>=0,y5>=0,-1 <= -2*y1+3*y2+2*y3+y4-y5, 1 <= y1+2*y2+3*y3+y4-y5});

т. е. Gmin(0,0,1/3,0,0)=1.
19) f=12x1-4x2max,
x1,x20,
-3x1-x2-4,
x1+5x21,
-2x1-2,
-x1+x20,
-x1-x2-1.
Построим множество
x1,x20, -3x1-x2-4,
x1+5x21,
-2x1-2,
-x1+x20,
-x1-x2-1.

Данная задача не имеет решения.
> maximize(12*x1-4*x2,{x1>=0,x2>=0,3*x1+x2>=4,-x1-5*x2>=-1,2*x1>=2,x1-x2>=0,x1+x2>=1});

f=12x1-4x2max,
x1,x20,
-3x1-x2-4,
x1+5x21,
-2x1-2,
-x1+x20,
-x1-x2-1.
Формулировка двойственной задачи:
G(y)=-4y1 +y2-2y3-y5min,
y1,y2, y3, y4 0,
-3y1 +y2- 2y3- y4 –y512,
-y1 +5y2+y4 –y5-4.
По теореме о дополняющей нежесткости получаем, что двойственная задача не имеет решения, т.к. если бы существовало решение двойственной задачи, то по нему можно было бы восстановить, исходя из теоремы, решение прямой задачи, а его нет.
31) f=2x14x2min,
x1,x20,
2x1-x2-1,
x1+2x21,
x1-x2-2,
5x1-3x2 15
2x1+3x26.
Построим множество
Вектор градиента направлен как (5\20,-11\20), значит, точка минимума функции будет располагаться на пересечении прямых 3x1+x2=8 и x1+x2=2. Т.е. x1=3\2, x2=7\2. fmin(3\2,7\2)=-31.
> minimize(5*x1-11*x2 ,{-2*x1+x2<=1,-x1+x2<=2,3*x1+x2<=8,-2*x1+3*x2>=-9,4*x1+3*x2>=0},NONNEGATIVE);

f=5x111x2min,
x1,x20,
2x1-x2-1,
x1-x2-2,
-3x1-x2-8,
2x1+3x29,
4x1+3x20.
Формулировка двойственной задачи:
G(y)=-y1 -2y2-8 y3 -9 y4 max,
y1,y2, y3, y4 , y50,
2y1 +y2- 3y3- 2y4 +4y5 5,
-y1 -y2- y3 +3y4 +3 y5-11.
По теореме о дополняющей нежесткости получаем:
3\2(2y1 +y2- 3y3- 2y4 +4y5 -5)=0,
7\2(-y1 -y2- y3 +3y4 +3 y5+11)=0,
y1 (3-7\2+1)=0,
y2 (3\2-7\2+2)=0,
y3 (-9\2-7\2+8)=0,
y4 (3+21\2+9)=0,
y5 (6+21\2)=0.
Получаем:
y1 =0, y4=0,y5 =0
y2- 3y3-5=0,
-y2- y3 +11=0, т.е:
y1 =0, y2 =19\2, y3 =3\2, y4=0,y5 =0.
> maximize(-y1-2*y2-8*y3-9*y4,{2*y1+y2-3*y3-2*y4+4*y5<=5,-y1-y2-y3+3*y4+3*y5<=-11},NONNEGATIVE);

§3. Необходимые сведения из теории графов…. стр. 14
§4. Построение полного графа задачи о коммивоя-
жере на основе анализа графа коммуникаций…. стр. 17
Глава 2. Методы решения задачи о коммивояжере… стр. 19
§1. Эвристические методы и методы Монте-Карло. стр. 19
§2. Сведение задачи о коммивояжере к задачам це-
лочисленного линейного программирования … стр. 21
§3.Решение задачи о коммивояжере методами дина-
мического программирования…. стр. 25
§4.Метод ветвей и границ…. стр. 27
Заключение …. стр. 36
Литература …. стр. 37