Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Пусть задана некоторая задача линейного программирования, система ограничений которой имеет следующий вид:
Решить данную задачу с помощью симплекс-метода, если целевая функция задана следующим соотношением:
На основании исходных данных построим симплексную таблицу, в строке которой, помеченной слева нулем, запишем целевую функцию, а на ниже расположенных строках – уравнения системы линейных ограничений:
При решении задачи будем производить преобразования именно с этой таблицей. Решим задачу в соответствии с алгоритмом симплекс-метода:
1 итерация (k=1):
В соответствии с выражением (13) вычислим текущее допустимое решение:
Так как все коэффициенты при свободных переменных положительны (в общем случае достаточно и одного такого положительного коэффициента), то найденное решение не является оптимальным. Улучшим найденное решение.
В соответствии с формулой (14) алгоритма найдем е-строку и s-столбец:
e-строке будет соответствовать максимальный положительный коэффициент при свободной переменной. Таким образом, определяем:
Для определения s-строки необходимо, прежде всего, рассчитать столбец g. Результаты расчетов представлены ниже:
е | |||||
s | |||||
Тогда, очевидно (см. соотношение (14)), что на данной итерации индекс s строки равен 3, т.е.:
В соответствии с формулами (15), (16), (17) и (18) произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:
-18 | ||||
2 итерация (k=2):
В соответствии с выражением (13) вычислим текущее допустимое решение:
Так как один из коэффициентов при свободных переменных положителен, то найденное решение не является оптимальным. Улучшим найденное решение.
В соответствии с формулой (14) алгоритма найдем е-строку и s-столбец:
Для определения s-строки необходимо, прежде всего, рассчитать столбец g. Результаты расчетов представлены ниже:
e | |||||
-18 | |||||
s | |||||
Тогда, очевидно (см. соотношение (14)), что на данной итерации индекс s строки равен 3, т.е.:
В соответствии с формулами (15), (16), (17) и (18) произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:
-1 | -1 | -20 | ||
-1 | ||||
-1 | ||||
-2 |
3 итерация (k=3):
В соответствии с выражением (13) вычислим текущее допустимое решение:
Так все коэффициенты при свободных переменных отрицательны, то найденное решение является единственным оптимальным решением данной задачи. Улучшить найденное решение не возможно.
Пример. Задача о планировании производства.
Пусть некоторому производственному объединению необходимо составить план выпуска продукции на следующий месяц. Предприятие способно производить, т.е. имеет все необходимые для производства средства два вида товара и . Для производства каждого из этих товаров необходимы некоторые ресурсы. Пусть известно, что на начало следующего месяца в распоряжении предприятия будут иметься ресурсы (сырьё, рабочая сила, оборудование) в количестве единиц.
Известно также, что для производства одной единицы товара необходимо единиц ресурса . Было посчитано, что в условиях предполагаемого бесконечного (для простоты) спроса, каждая единица после реализации будет приносить прибыль .
Необходимо определить, в каком количестве должны производится товары , чтобы суммарная прибыль, полученная предприятием по итогам месячной работы, была наибольшей, если
, .
Решение:
Очевидно, что данная задача является основной задачей линейного программирования, т.е. может быть решена уже рассмотренными нами методами. Математическая модель задачи может быть представлена следующим образом:
Еще раз рассмотрим графический метод решения задач линейного программирования, для чего дадим геометрическую интерпретацию задачи в пространстве решений и .
|
Решим теперь данную задачу симплекс-методом.
Прежде всего, как и в предыдущем примере, на основании исходных данных построим симплекс-таблицу:
1 итерация (k=1):
В соответствии с формулой (13) вычислим текущее допустимое решение:
Так как все коэффициенты при свободных переменных положительны, то найденное решение не является оптимальным. Улучшим найденное решение.
В соответствии с формулой (14) алгоритма симплекс-метода найдем е-строку и s-столбец:
e-строке будет соответствовать максимальный положительный коэффициент при свободной переменной. Таким образом, определяем:
Для определения s-строки необходимо дополнительно рассчитать столбец значений g. Результаты расчетов представлены ниже:
е | |||||
s | |||||
Тогда в соответствии с формулой (14) делаем вывод о том, что на данной итерации индекс s строки равен 4, т.е.:
Опираясь на соотношения (15), (16), (17) и (18), произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:
-1 | -24 | |||
2 итерация (k=2):
В соответствии с формулой (13) вычислим текущее допустимое решение:
Так как один из коэффициентов при свободных переменных положителен, то найденное решение не является оптимальным. Улучшим найденное решение.
В соответствии с формулой (14) алгоритма найдем е-строку и s-столбец:
Для определения s-строки необходимо дополнительно рассчитать столбец значений g. Результаты расчетов представлены ниже:
е | |||||
-1 | -24 | ||||
s |
Из приведенной таблицы видно (см. соотношение (14)), что на данной итерации индекс s строки равен 5, т.е.:
В соответствии с формулами (15), (16), (17) и (18) произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:
-2 | -26 | |||
-6 | ||||
-1 | ||||
3 итерация (k=3):
В соответствии с формулой (13) вычислим текущее допустимое решение:
Так все коэффициенты при свободных переменных отрицательны, то найденное решение является единственным оптимальным решением данной задачи. Улучшить найденное решение не возможно.
Снимем ранее введенные требования (A, B, C, D) к ЗЛП, расширив тем самым класс решаемых задач:
Требование А - если речь идет о минимизации функции F, то достаточно записать, что необходимо максимизировать (-F), то есть
min F = max (-F) (оператор М);
Требование В – если существует ограничения вида , то достаточно умножить их на (-1), чтобы требование В выполнялось (оператор N);
Требование C – если существуют переменные, принимающие отрицательные значения, то достаточно произвести замену:
, где (оператор P);
Требование D – если существует отрицательный свободный, член выполнить оператор К. Поиск опорного решения, иначе выполнить оператор L.
Поиск опорного решения (оператор К)
Таким образом, общий алгоритм решений ЗЛП можно представить следующей схемой:
1.
Рассмотрим теперь решение симплекс-методом задачи линейного программирования заданной в форме, отличной от стандартной формы.
Пример. Задача линейного программирования в произвольной форме.
Пусть задана некоторая задача линейного программирования с линейной системой ограничений и целевой функцией, представленными ниже:
Решить данную задачу симплекс-методом.
Несмотря на форму задачи, на основании исходных данных построим симплексную таблицу, в строке которой, помеченной слева нулем, запишем целевую функцию, а на ниже расположенных строках – уравнения системы линейных ограничений:
Так как данная задача не подходит под определение стандартной формы основной задачи линейного программирования, перед применением симплекс-метода необходимо выполнить ряд преобразований (операторов).
По условию задачи необходимо минимизировать целевую функцию. Тогда, основываясь на результатах проверки условия A, применим к данной целевой функции оператор M. Новая симплекс таблица примет вид:
-12 | -8 | -6 | |||
По условию задачи все неравенства системы линейных ограничений содержат знаки «больше или равно». Тогда, основываясь на результатах проверки условия B, применим к каждому неравенству данной системы ограничений оператор N. Новая симплекс таблица примет вид:
-12 | -8 | -6 | |||
-1 | -1 | -1 | -2 | ||
-2 | -1 | -3 |
При решении задачи будем производить преобразования именно с этой таблицей. Решим задачу в соответствии с алгоритмом симплекс-метода:
1 итерация (k=1):
Так как преобразованная система линейных ограничений содержит отрицательные свободные члены (выполняется условие D), то к полученной на предыдущем этапе симплекс-таблице необходимо применить оператор K – поиск опорного решения.
В соответствии с алгоритмом поиска опорного решения возьмем любое неравенство системы ограничений, содержащее отрицательный свободный член, например первое неравенство (индекс строки в симплекс-таблице 4), и выберем в нем любой отрицательный элемент, например первый (он равен -1). Тогда в качестве e-столбца будет выступать столбец 1, т.е.:
Для определения s-строки необходимо, прежде всего, рассчитать столбец g. Результаты расчетов представлены ниже:
e | ||||||
-12 | -8 | -6 | ||||
-1 | -1 | -1 | -2 | |||
S | -2 | -1 | -3 |
В соответствии с пунктом 2 алгоритма поиска опорного решения на данной итерации индекс s строки равен 5, т.е.:
В соответствии с формулами (15), (16), (17) и (18) алгоритма симплекс-метода произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:
-6 | -2 | -6 | |||
-1 | |||||
2 итерация (k=2):
Так как преобразованная система линейных ограничений содержит отрицательный свободный член (строка с индексом 4), т.е. выполняется условие D, то к полученной на предыдущем этапе симплекс-таблице необходимо снова применить оператор K – поиск опорного решения.
В соответствии с алгоритмом поиска опорного решения возьмем первое неравенство системы ограничений (индекс строки в симплекс-таблице 4), и выберем в нем любой отрицательный элемент, например второй (он равен -2). Тогда в качестве e-столбца будет выступать столбец 2, т.е.:
Для определения s-строки необходимо дополнительно рассчитать столбец g. Результаты расчетов представлены ниже:
e | ||||||
-6 | -2 | -6 | ||||
s | -1 | |||||
В соответствии с пунктом 2 алгоритма поиска опорного решения на данной итерации индекс s строки равен 4, т.е.:
В соответствии с формулами (15), (16), (17) и (18) алгоритма симплекс-метода произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:
-4 | -4 | -2 | |||
-2 | |||||
-1 | -1 |
3 итерация (k=3):
В соответствии с выражением (13) вычислим текущее допустимое решение:
Так все коэффициенты при свободных переменных отрицательны, то найденное решение является единственным оптимальным решением данной задачи. Улучшить найденное решение не возможно.
Дата публикования: 2015-07-22; Прочитано: 1037 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!