Балашовский филиал

Ответы
В ответах на задачи 1—10 приведено только оптимальное значение целевой функции, этого достаточно для проверки.
1. L_max = 2. 2. L_min = –∞. 3. L_min = 5. 4. L_max = 8/3. 5. L_min = 4.
6. L_max = +∞. 7. L_min = 0. 8. L_max = 6. 9. L_min = –16²/₃. 10. L_max = 20/3.
11. = (4 000; 7 000), L_max = 590 000 (руб.). 12. а) = (11,688; 0), L_max= 11,688 (шт.); б) = (1,2; 8,448), L_max = 676 046,4 (тыс. руб.);
в) = (1,2; 0), L_min = 41 592 (тыс. руб.). 13. = (0; 3),
L_max= 600 (руб.). 15. = (27 – 27 ; 48 + 15 ), ,
L_max = 453 600 (руб.). 16. = (2; 3), L_min = 26 (усл. ден. ед.).
17. На зубофрезерном станке надо выпустить 80 колес первого вида и 100 колес второго вида, а на зубодолбежном — 10 колес второго вида и 140 колес третьего вида, L_min = 4 060 (мин).
18. а) = , , L_max= 2 600;
б) = , , L_min= 1 790.

§ 3. Симплексный метод

1. Каноническая задача линейного программирования

Графический метод решения задачи линейного программирования применяется только в случае двух или трех переменных. Симплексный метод (или симплекс-метод) в отличие от него является универсальным, так как позволяет решить общую задачу линейного программирования (ОЗЛП) практически с любым количеством переменных. Но для этого она должна быть приведена к каноническому виду или к канонической задаче линейного программирования (КЗЛП). Множество канонических задач является подмножеством всех задач линейного программирования. Перечислим отличительные черты КЗЛП:

1. 
   Все ограничения в системе ограничений являются равенствами.
   
2. 
   Требование неотрицательности наложено на все переменные, входящие в систему ограничений.
   
3. 
   Целевая функция минимизируется. Надо отметить, что это требование влечет только лишь признак прекращения вычислений, который мы укажем при изложении алгоритма симплекс-метода, и не является принципиальным.
   

Покажем, что любая задача линейного программирования может быть приведена к каноническому виду. Для этого необходимо выполнить следующие преобразования ОЗЛП:

1. 
   Всякое условие вида , где s = 1 или 2, или …, или n заменяется условием
   
2. 
   Всякое условие вида , где s = 1 или 2, или …, или n заменяется условием
   
3. 
   Все переменные x_p, на которые не наложены требования неотрицательности, подставляются в равенства, полученные на двух предыдущих шагах, и в целевую функцию в виде x_p = w_p – v_p, w_p ≥ 0, v_p ≥ 0.
   

После преобразований 1—3 все новые переменные удобно обозначить буквой x, пронумеровав их по порядку введения, начиная с номера m + 1. Причем на шаге 3 переменную w_p удобно обозначить x_p, а v_p — буквой x
с первым свободным номером. Возможно, за счет введения новых переменных на шаге 3 изменится и целевая функция. Новую целевую функцию обозначим L₁(X).

4. 
   В случае оптимизации вида L₁(X)→max воспользуемся равенством max L₁(X) = –min(–L₁(X)). Поэтому введем новую целевую функцию
   (X) = –L₁(X), решим задачу при условии (X)→min, после чего сделаем замену max L₁(X) = –min(– (X)).