Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Составим задачу, двойственную к исходной, и запишем ограничения:
Решим полученную задачу симплекс – методом.
Сведем задачу на максимум к задаче на минимум. Для этого целевую функцию умножим на -1, получим
Вводим неотрицательные дополнительные переменные для приведения задачи к каноническому виду:
Базисные перемененные , свободные .
Выражаем базисные переменные через свободные:
Получим систему уравнений допустимого вида.
Для составления первой симплекс – таблицы запишем задачу в виде:
Таблица 1
Базисные переменные | Свободные члены | Отно- шение | ||||||
W | 5 |
В последней строке есть положительные коэффициенты. Возьмем коэффициент в столбце переменной . Разрешающим элементом является 3.
Строим таблицу 2.
Для этого умножаем выделенную стрелкой строку на 1/3 и записываем результат вместо этой строки в таблицу 2.
Умножаем третью строку новой таблицы на (-1) и складываем с первой, умножаем на (-2) и складываем со второй, умножаем на (-5) и складываем с четвертой строкой старой таблицы.
Таблица 2
Базисные переменные | Свободные члены | Отно- шение | ||||||
2/3 | -1 | -1/3 | ||||||
1/3 | -2 | -2/3 | ||||||
1/3 | 1/3 | |||||||
W | -15 | 1/3 | -6 | -5/3 |
В новой таблице последняя строка имеет положительный коэффициент в столбце переменной . Разрешающим элементом является 1/3.
Строим таблицу 3. Для этого умножаем выделенную стрелкой строку на и записываем результат вместо этой строки в таблицу 3.
Умножаем вторую строку новой таблицы на и складываем с первой, на и складываем с третьей и на и складываем с четвертой строкой предыдущей таблицы.
Таблица 3
Базисные переменные | Свободные члены | ||||||
-2 | |||||||
-6 | -2 | ||||||
-1 | |||||||
W1 | -16 | -4 | -1 | -1 |
В полученной таблице последняя строка не имеет положительных чисел в последних шести столбцах. Значит, достигнуто оптимальное решение. Базисным решением для переменных являются соответственно свободные члены. Базисное решение для свободных переменных равно нулю. Таким образом, оптимальное решение имеет вид:
=2, =3, =1, =0, =0, =0,
,
.
Подставим оптимальное решение в систему ограничений. Получим, что первое второе ограничение выполняется как строгое неравенство:
По теореме 2 следует, что соответствующая координата оптимального решения двойственной задачи, то есть исходной задачи, равна нулю: .
Учитывая это и в силу теоремы 2, из системы ограничений исходной задачи получим систему:
Данная система получаетcя в силу того, что , следовательно первое и второе ограничения исходной задачи удовлетворяются оптимальным решением как равенство.
Решив систему:
получим .
Оптимальное решение исходной задачи
Ответ:
Дата публикования: 2015-03-26; Прочитано: 368 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!