Создан заказ №752763
16 октября 2015
Дана каноническая задача линейного программирования а) Решить задачу графически
Как заказчик описал требования к работе:
Задание: сделать решение задач по теории вероятности за 2 дня, красиво оформить. Сколько стоит решение задач пишите точно.
Фрагмент выполненной работы:
Дана каноническая задача линейного программирования.
а) Решить задачу графически.
б) Методом искусственного базиса найти угловую точку.
в) Найти оптимальное решение симплекс-методом.
г) Составить двойственную задачу.
д) Проверить правильность решения ЗЛП и найти решение двойственной задачи, используя условия дополняющей нежесткости.
-3x1+x2-2x4min
4x1-3x2-2x3+x4=0
-5x1+5x2+3x3-x4=3
X1,2,3,4≥0
Решение:
Выразим х3 и х4 через переменные х1 и х2 методом жардана-Гауса
Получим систему ограничений вида:
Выразим х3 и х4:
Получим задачу уже с двумя переменными:
Или
Решаем эту задачу графически:
127254090233500104394043789600092964041656000
Оптимальная точка имеет координаты х1=0, х2=0.
Тогда:
F=
б) Найдем начальную угловую точку методом искусственного базиса
В систему вводим искусственные переменные x5 ≥0, x6 ≥0, новую целевую функцию, как сумму всех искусственных переменных, а старую присоединяем – к ограничениям:
X1,2,3,4,5,6≥0
0 0 0 0 1 1
Базисные переменные Свободные члены b x1 x2 x3 x4 x5 x6 Отношение a/b
F 0 3 -1 0 2 0 0 -
x6 0 4 -3 -2 1 1 0 0
x7 3 -5 5 3 -1 0 1 0,6
Z= 3 -1 2 1 0 0 0
F 0 1 2/3 0 2/3 1 2/3 - 1/3 0 0
x2 0 -1 1/3 1 2/3 - 1/3 - 1/3 0 0
x7 3 1 2/3 0 - 1/3 2/3 1 2/3 1 1 4/5
Z= 3 1 2/3 0 - 1/3 2/3 2/3 0
F -3 0 0 1 1 -2 -1
x2 2 2/5 0 1 2/5 1/5 1 4/5
x1 1 4/5 1 0 - 1/5 2/5 1 3/5
Z= 0 0 0 0 0 -1 -1
Начальная угловая точка:
x1=1,8
х2=2,4
x3 = 0
x4 = 0
в) Найдем оптимальное решение симплекс-методом:
Базисные переменные Свободные члены b x1 x2 x3 x4 Отношение
x1 1,80 1 0 - 1/5 2/5
x2 2,40 0 1 2/5 1/5 6
F= -3 0 0 1 1
x1 3 1 0,5 0 0,5 6
x3 6 0 2 1/2 1 1/2 12
F= -9 1 0,5 1 1,5
x4 6 2 1 0 1
x2 3 -1 2 1 0 3
F= -9 -2 -1 1 0
x4 6 2 1 0 1
x3 3 -1 2 1 0
F= -12 -1 -3 0 0
Поскольку нет положительных симплекс разностей, то найден оптимальный план:
x1=0
х2=0
x3 = 3
x4 = 6
Значение целевой функции:
г) Составить двойственную задачу.
Составим двойственную задачу:
Исходная задача
Двойственная задача
- 3x1 + x2 - 2x4 → min
↔ 3y2 → max
4x1 - 3x2 - 2x3 + x4=0 ↔ y1 любое число
- 5x1 + 5x2 + 3x3 - x4=3 ↔ y2 любое число
x1 ≥ 0 ↔ 4y1 - 5y2≤-3
x2 ≥ 0 ↔ - 3y1 + 5y2≤1
x3 ≥ 0 ↔ - 2y1 + 3y2≤0
x4 ≥ 0 ↔ y1 - y2≤-2
д) Проверить правильность решения ЗЛП и найти решение двойственной задачи, используя условия дополняющей нежесткости.
190690555689500Найдем решение двойственной задачи через условия дополняющей нежёсткости:
y1 (4x1 - 3x2 - 2x3 + x4)=0
y2 (- 5x1 + 5x2 + 3x3 - x4-3)=0
x1 (4y1 - 5y2≤+3) =0
x2 (- 3y1 + 5y2-1) =0
x3 (- 2y1 + 3y2) =0
x4 (y1 - y2+2) =0
Подставляем решение прямой задачи:
y1 (0 - 0 – 2*3 + 6)=0
y2 (- 5x1 + 5x2 + 3*3 - 6-3)=0
0 (4y1 - 5y2≤+3) =0
0 (- 3y1 + 5y2-1) =0
3 (- 2y1 + 3y2) =0
6 (y1 - y2+2) =0
Получим:
- 2y1 + 3y2=0
y1 - y2=-2
Получим
y1=-6
y2=-4
W(Y) = 3*(-4) = -12
W(Y) =
Транспортная задача задана таблицей
Заголовки В1
В2
В3 В4
Запасы
А1
6 3 1 0 40
A2 9 1 2 0 90
A3 5 6 9 0 50
Потребности 30 30 30 90
Найти базисную перевозку методом минимального элемента...Посмотреть предложения по расчету стоимости
Заказчик
заплатил
заплатил
20 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
17 октября 2015
Заказ завершен, заказчик получил финальный файл с работой
5
Дана каноническая задача линейного программирования
а) Решить задачу графически.jpg
2018-12-20 18:58
Последний отзыв студента о бирже Автор24
Общая оценка
5
Положительно
Все хорошо. Работа выполнена на высшем уровне. Четко и быстро. Спасибо. Рекомендую !
Хочешь такую же работу?
300 ₽
