Решение задачи нахождения минимума целевой функции
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
р.
Условия не отрицательности выполнены, следовательно, найдено оптимальное решение.
3. Решение задачи линейного программирования с использованием симплекс-таблицы
Решение: Приведем задачу к стандартному виду для решения с помощью симплекс-таблицы.
Все уравнения системы приведем к виду:
Строим симплекс-таблицу:
В верхний угол каждой клетки таблицы вписываем коэффициенты из системы уравнений;
Выбираем максимальный положительный элемент в строке F, кроме b, это будет генеральный столбец;
Для того, чтобы найти генеральный элемент строим отношение для всех положительных a. 3/3; 9/1;- минимальное соотношение в строке x3. Следовательно - генеральная строка и a=3 - генеральный элемент.
Находим l=1/a=1/3. Вносим l в нижний угол клетки, где находится генеральный элемент;
Во все незаполненные нижние углы генеральной строки вносим произведение значения в верхнем углу клетки на l;
Выделяем верхние углы генеральной строки;
Во все нижние углы генерального столбца заносим произведение значения в верхнем углу на -l и выделяем полученные значения;
Остальные клетки таблицы заполняются, как произведения соответствующих выделенных элементов;
Затем строим новую таблицу, в которой обозначения клеток элементов генерального столбца и строки меняются местами (x2 и x3);
В верхний угол бывших генеральных строки и столбца записываются значения, которые до этого были в нижнем углу;
В верхний угол остальных клеток записывается сумма значений верхнего и нижнего угла этих клеток в предыдущей таблице
4. Решение задачи линейного программирования методом отыскания допустимого решения
Пусть дана система линейных алгебраических уравнений:
Можно предположить, что все , в противном случае умножаем соответствующее уравнение на -1.
Вводим вспомогательные переменные:
Вводим так же вспомогательную функцию
Будем минимизировать систему при ограничениях (2) и условиях .
ПРАВИЛО ОТЫСКАНИЯ ДОПУСТИМОГО РЕШЕНИЯ: Для отыскания допустимого решения системы (1) минимизируем форму (3) при ограничениях (2), в качестве свободных неизвестных берем xj, в качестве базисных .
При решении задачи симплекс-методом могут возникнуть два случая:f=0, тогда все xi обязаны быть равными нулю. А получившиеся значения xj будут составлять допустимое решение системы (1).f>0, т.е. исходная система не имеет допустимого решения.
Исходная система:
Используется условие задачи предыдущей темы.
Внесем дополнительные переменные:
Найдено допустимое решение исходной задачи: х1 = 3, х2 = 3, F = -12. Основываясь на полученном допустимом решении найдем оптимальное решение исходной задачи, пользуясь симплекс-методом. Для этого построим новую симплекс-таблицу из таблицы полученной выше, удалив строку и строку с целевой функцией вспомогательной задачи:
Св. Баз.13/8-1/8031/41/403-1/83/80-12-11/8-7/80
Анализируя построенную симплекс-таблицу, видим, что оптимальное решение для исходной задачи уже найдено (элементы в строке, соответствующей целевой функции , отрицательны). Таким образом, допустимое решение, найденное при решении вспомогательной задачи совпадает с оптимальным решением исходной задачи:
6. Двойственная задача линейного программирования
Исходная система ограничений и целевая функция задачи показаны на рисунке ниже.
при ограничениях:
Решение: Приведем систему ограничений к стандартному виду:
Задача, двойственная данной будет иметь вид:
,
Решение двойственной задачи будет выполняться простым симплекс-методом.
Преобразуем целевую функцию так, чтобы решалась задача минимизации, и запишем систему ограничений в стандартной форме для решения симплекс-методом.
y6 = 1 - ( -2 y1 + 2y2 +y3 + y4+ y5)= 5 - ( -3y1 - y2 + y3 + y4 )
Ф = 0 - ( 3y1 + 9y2 + 3y3 + y4 ) ??min
Построим исходную симплекс-таблицу для решения двойственной задачи ЛП.
?Y1Y2Y3 Y4 Y5Y61 1/2-2 -12 1/21 1/21 1/21 1/2Y75 1/2-3 -1-1 1/21 1/21 1/20 1/2Фmin0 -9/23 99 -9/2 3 -9/21 -9/2 0 -9/2
Первый шаг симплекс-метода
?Y1Y6Y3 Y4 Y5Y21/2 -11/8 -1 -1/4 1/2 -1/8 1/2 -3/81/2 -3/81/2 -1/8 Y711/2 -11/8-4 -1/41/2 -1/83/2 -3/83/2 -3/8 -1/8Фmin-9/2 33/212 3-9/2 3/2-3/2 9/2-7/2 9/2-9/2 3/2
Второй шаг симплекс-метода
?Y1Y6Y3 Y4 Y5Y21/2 -11/8 -1 -1/4 -1/8 1/2 -3/81/2 -3/81/2 -1/8 Y711/2 -11/8-4 -1/41/2 -1/83/2 -3/83/2 -3/81/2 -1/8Фmin-9/2 33/212 3-9/2 3/2-3/2 9/2-7/2 9/2-9/2 3/2Третий шаг симплекс-метода
?Y7Y6Y3 Y4 Y5Y2-7/8 -1/4 3/81/81/81/8Y1-11/8-1/4-1/8 -3/8-3/8-1/8Фmin123 -331-3
Итак, на третьем шаге симплекс-метода найдено оптимальное решение задачи минимизации со следующими результатами : y2 = -7 /8, y1 = -11/8, Ф = 12. Для того, чтобы найти значение целевой функции двойственной задачи, подставим найденные значения базисных и свободных переменных в функцию максимизации:
Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12
Так как значение целевой функции прямой и двойственной задач совпадают, решение прямой задачи найдено и равно 12.
Fmin = Фmax = -12
7. Решение задачи целочисленного линейного программирования методом ветвей и границ
Преобразуем исходную задачу таким образом, чтобы не выполнялось условие целочисленности при решении обычными методами.
Исходный многоугольник решений задачи целочисленного программирования.
Для преобразованного многоугольника решений построим новую систему ограничений.