Содержание
1. Решить графическим методом задачи с двумя переменными (табл. 1).
Z(X)=-5×1+x2—>min
2×1-3×2>=0
x1+3×2>=9
x1-3×2
-x1+3×2
x1,x2>=0
2. Решить графическим методом задачи с п переменными (табл. 2).
Z(X)=2×1+3×2+4×3-6×4—>max
x1+x2+2×3+2×4=8
2×1+x2+x3+3×4=6
xj>=0,j=1,2,3,4
3. Решить методом искусственного базиса задачи линейного программирования (см. табл. 2).
Z(X)=2×1+3×2+4×3-6×4—>max
x1+x2+2×3+2×4=8
2×1+x2+x3+3×4=6
xj>=0,j=1,2,3,4
4. Решить симплексным методом задачи (табл. 3).
Z(X)=x1+2×2+2×3—>min
-x1-x2+4×3
x1-2×2+2×3=2
x1+2×2-2×3
xj>=0,j=1,2,3
5. Решить методом потенциалов транспортные задачи (табл. 4).
100 200 200 100 200
100 2 3 4 2 5
200 3 1 1 3 1
300 4 3 3 5 4
200 5 1 2 6 7
100 2 9 8 7 6
6. Решить методом потенциалов транспортные задачи с ограничениями на пропускную способность (табл. 5).
x34=50
50 100 100 150
50 1 3 4 1
100 3 2 2 4
150 4 8 9 5
150 9 6 7 10
Выдержка из текста
Вариант 26
1. Решить графическим методом задачи с двумя переменными (табл. 1).
Решение:
построим многоугольник допустимых значений, для этого построим на плоскости прямые:
и отметим полуплоскости, которые обозначают неравенства ограничения:
Далее, построим вектор-градиент целевой функции и линии уровня целевой функции . Т.к. минимум целевая функция достигает в самой крайней точке многоугольника допустимых значений, которую проходит линия уровня, если перемещать ее в направлении противоположном направлению вектора-градиента:
Таким образом, задача не имеет решений, т.к. область допустимых значений не ограничена.
2. Решить графическим методом задачи с п переменными (табл. 2).
Решение:
для того чтобы решить данную задачу графическим методом составим двойственную задачу к данной:
т.к. исходная задача на максимум содержит 4 переменные и два равенства-ограничения, то двойственная задача будет задачей на минимум и содержать 4 неравенства-ограничения и две переменные, итак получим:
,
Решим полученную задачу графически:
построим многоугольник допустимых значений, для этого построим на плоскости прямые:
и отметим полуплоскости, которые обозначают неравенства ограничения, а также построим вектор-градиент целевой функции и линии уровня целевой функции . Т.к. минимум целевая функция достигает в самой крайней точке многоугольника допустимых значений, которую проходит линия уровня, если перемещать ее в направлении противоположном направлению вектора-градиента:
следовательно, в точке М минимум, найдем ее координаты:
т.е. и .
Тогда по первому критерию (теореме) оптимальности планов двойственных задач.
Оптимальный план исходной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальности допустимых решений и пары двойственных задач необходимо и достаточно выполнение условий:
и
т.е. из первой системы имеем, подставив в нее :
следовательно, из второй системы получим:
тогда .
Итак, искомое решение исходной задачи , где .