Курсовая работа: Решение задач линейного программирования в среде Maple
Для вывода критерии
оптимальности транспортной задачи построим двойственную задачу.
Структура матрицы
ограничений транспортной задачи такова, что столбец, соответствующей переменной
 содержит ровно два ненулевых
элемента: единицу в строке с номером i и единицу в строке m + i.
Вектор двойственных
переменных Y = ( ,…, , ,…, ) имеет m + n компонент (по числе ограничений ТЗ),
которые называются потенциалами: переменные  , ,…, - потенциалы поставщиков; переменные  , …, - потенциалы потребителей.
Используя схему для
построения двойственной задачи к ЗЛП в стандартной форме, имеем: 
В полученной двойственной
задаче n·m ограничений, соответствующих каждой переменной  ТЗ. Вспоминая, что невязка между левой и правой частью
в ограничений двойственной задачи есть оценка для соответствующей переменной
исходной задачи , запишем условия оптимальности текущего плана перевозок в ТЗ:
 .
Неизвестные потенциалы  и  (их общее количество равно m + n)
могут быть найдены (и именно так отыскиваются) из условия равенства нулю оценок
для базисных переменных (заполненных клеток таблицы) ТЗ (таких равенств (m+n - 1), что следует из замечания ниже).
 ,
для заполненных клеток (i,j) таблицы ТЗ.
Решение полученной
системы (содержащей неизвестных на единицу больше, чем число уравнений) ищется,
когда одно из неизвестных (вообще говоря, любое) полагается равным некоторому
числу (тоже, вообще говоря, любому). После этого оставшаяся система имеет
единственное решение.
§4. Пример решения
задача линейного программирования
Решим
задачу линейного программирования симплекс – методом :
f(x) = 2x1 + 3x2 + 4x3→ max
3x1 + x2 + 3x3<=5
5x1 + 4x2 + 4x3<=12
2x1 + x2 + 2x3<=8
x1>=0; x2>=0; x3>=0;
Данные
задачи заносим в симплекс таблицу.
| x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
значения |
базис |
оценка |
| 3 |
1 |
3 |
1 |
0 |
0 |
5 |
x4 |
5/3 |
| 5 |
4 |
4 |
0 |
1 |
0 |
12 |
x5 |
3 |
| 2 |
1 |
2 |
0 |
0 |
1 |
8 |
x6 |
4 |
| 2 |
3 |
4 |
0 |
0 |
0 |
0 |
- f |
|
В
этой таблице первая, вторая и третья строки соответствуют ограничениям задачи,
последняя строка – функция цели. Это оценочная строка. Значение функции цели
берём 0. Выделяем базисные переменные. Эта переменная находиться в столбце, для
которой имеется одна единица, остальные нули. В столбце «базис» отмечаем
одноимённые переменные в той строке, где расположена эта единственная единица.
Остальные переменные называются свободными.
Страницы: 1, 2, 3, 4, 5, 6 |
