Примеры решения задач симплекс-методом
Дата добавления: 2014-11-24 | Просмотров: 1532
Подавляющее большинство активной аудитории группы – жители города Конаково. Значительная часть пользователей проживает в Москве, Дубне или Твери, но регулярно приезжает в город. Большинство участников сообщества, проживающих в Конаковском районе, приходится на Завидовское, Вахонинское, Селиховское и Дмитрогорское сельские поселения. Есть пользователи из поселков Новозавидовский, Редкино, Козлово и с. Городня. В остальных населённых пунктах Конаковского района группа не пользуется популярностью.
Участники сообщества. На 12 ноября 2014 в сообществе более 10.300 участников. Их количество стабильно растёт на 150-200 человек в месяц.
2.Охват аудитории (на 12 ноября 2014 г).
В данном разделе рассматривается статистика по менее активной аудитории, большая часть которой преимущественно просматривает новости на стене сообщества и не принимает активного участия в жизни группы.
В новостной ленте за сутки новости сообщества просматривает от 3 до 5 тысяч человек. При наличии большого количества информационных поводов или значимых событий, эта цифра может возрастать в 2-3 раза.
Средний возраст 18-30 лет. Девушек больше.
География аудитории. Конаково лидирует, с более чем 50% аудитории, однако доля других населённых пунктов так же весьма велика. Многие живут в Москве, Твери, Дубне, либо Конаковском районе. Часто бывают в Конаково.
Общее количество пользователей, просматривающих новости сообщества за месяц – более 30.000 человек.
Охват аудитории по месяцам (на 12 ноября 2014 г)
Анатолий Плешанов. Руководитель проекта «Конаково Конаковский район В контакте». 8 (900) 471-85-53 Hiphoptonight@mail.ru
Примеры решения задач симплекс-методом
Пример 1. Фирма выпускает изделия четырех типов. При этом используется сырье двух видов, запасы которого соответственно 1200 и 1000 единиц. Нормы расхода сырья на изготовление каждого типа продукции, а также доход, полученный от выпуска единицы каждого типа продукции, заданы таблицей:
Сырье
| Нормы расхода
| Объем
ресурсов
| I
| II
| III
| IV
|
|
|
|
|
|
|
|
|
|
|
|
| Доход
|
|
|
|
|
|
Составить план производства, обеспечивающий фирме наибольший суммарный доход.
Решение. Обозначим через план выпуска продукции. Математическая модель задачи примет вид:
.
Преобразуем ее к каноническому виду. Введем две дополнительные (балансовые) неотрицательные переменные х5 и х6 и перейдем к функции Z1= – Z. Модель примет вид:
.
Поиск решения ЗЛП состоит из следующих этапов: нахождение первоначального опорного плана, проверка полученного опорного плана на оптимальность и переход от одного опорного плана к другому, если найденный опорный план не является оптимальным.
1. Запишем условия задачи в виде симплексной таблицы:
БП
| Переменные
| Свободный
член
| х1
| х2
| х3
| х4
| х5
| х6
| х5
|
|
|
|
|
|
|
| х6
|
|
|
|
|
|
|
| Z1
| –15
| –5
| –3
| –20
|
|
|
| Так как все свободные члены неотрицательны, то таблица содержит первоначальный опорный план. Его получим, положив свободные переменные равными нулю: при этом базисные переменные равны значениям соответствующих свободных членов. Имеем:
2. Выпишем вектор , компонентами которого являются коэффициенты при свободных переменных целевой функции:
.
Все компоненты вектора r отрицательны, следовательно, первоначальный опорный план не является оптимальным.
3. Выберем максимальную по модулю отрицательную компоненту вектора r:
.
Ей соответствует четвертый столбец таблицы. Анализируем коэффициенты вектора-столбца коэффициентов при х4. Они положительны: а14=4, а24=1. Есть возможность перейти к новому опорному плану, выведя из свободных переменных х4.
Выбираем четвертый столбец за разрешающий и переходим к п. 4.
4. Для выбора разрешающей строки составляем неотрицательные отношения
и выбираем среди них минимальное:
.
Разрешающей строкой будет первая, разрешающим элементом – элемент а14= 4.
5. Выполняя симплексное преобразование с разрешающим элементом а14=4, придем к новой таблице:
БП
| Переменные
| Свободный член
| х1
| х2
| х3
| х4
| х5
| х6
|
| | x4
|
| 1/2
| 1/4
|
| 1/4
|
|
| х6
|
| 9/2
| 11/4
|
| –1/4
|
|
| Z1
|
|
|
|
|
|
|
|
Таблица содержит новый опорный план:
.
Видим, что все компоненты вектора r=(5, 5, 2, 5) положительные, следовательно, этот опорный план является оптимальным, при этом Z1 min= – 6000.
Обратимся к исходной модели. В ней содержится 4 ограничения и целевая функция Z= – Z1. Оптимальным решением исходной задачи будет:
,
при этом Z max=6000.
Пример 2. Решить симплекс-методом задачу:
при ограничениях:
и дать геометрическую интерпретацию процесса решения.
Решение. Прежде всего, необходимо перейти к минимизации целевой функции. Для этого введем в рассмотрение функцию
Z1= – Z.
Тогда
В системе ограничений уже выделены базисные переменные х3 , х4 и х5. Теперь все исходные данные поместим в таблицу:
БП
| Переменные
| Свободный
член
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| –2
| –1
|
| –1
|
|
| В клетку на пересечении Z1-строки и столбца “Свободный член” запишем свободный член целевой функции с противоположным знаком. В данном случае он равен 0.
Приравняв свободные переменные нулю х1=х2=0, получим базисное решение системы ограничений:
где х3=5, х4=9, х5=7.
Так как то базисное решение Х1 является опорным решением (планом) задачи. Итак, первоначальное опорное решение найдено.
Для проверки его на оптимальность выразим функцию цели Z1 через свободные переменные х1 и х2. Для исключения переменной х3 из функции цели Z возьмем за разрешающий элемент а13=1 в третьем столбце предыдущей таблицы. Сделав один шаг преобразований Жордана–Гаусса, придем к таблице вида:
БП
| Переменные
| Свободный
член
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| –3
| –2
|
| –1
|
| –5
| Сделав аналогично еще два шага исключения неизвестных х4 и х5 из функции цели Z1, придем к таблице:
БП
| Переменные
| Свободный
член
|
| x2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| x5
|
|
|
|
|
|
|
| –2
| –3
|
|
|
| –3
|
Из таблицы видно, что
Z1(Х(1))=3, r =(–2; –3).
Так как условие не выполняется, то полученный опорный план Х(1) не является оптимальным.
Необходимо перейти к новому опорному плану, для которого значение функции уменьшится. Для перехода к следующему опорному плану нужно одну из свободных переменных (х1 либо х2) перевести в базис, а одну из базисных (х3, либо х4, либо х5) перевести в свободные. Выбор свободной переменной, вводимой в базис, определяется максимальной по модулю отрицательной компонентой вектора r= (–2; –3).
Компоненте r2= –3 соответствует в таблице переменная х2, которая вводится в базис, и второй столбец становится разрешающим.
Для выбора разрешающей строки вычислим
.
Итак, третья строка стала разрешающей, а разрешающим элементом стал элемент а32=2. Сделав один шаг в симплекс-таблице, получим новое опорное решение:
.
Это решение также не является оптимальным, так как в вектор r =(–1/2; 3/2) имеет отрицательную компоненту:
БП
| Переменные
| Свободный член
| x1
|
|
|
|
| x3
|
|
|
|
| –1/2
| 3/2
|
| 3/2
|
|
|
| –1/2
| 11/2
|
| 1/2
|
|
|
| 1/2
| 7/2
|
| –1/2
|
|
|
| 3/2
| 15/2
| Значение же функции цели Z1 уменьшилось от значения Z1 = 3 до значения Z1 = –15/2. (Напомним, что значение функции цели из таблицы берется с противоположным знаком.)
Очевидно, что на следующем шаге необходимо в базис ввести переменную х1, соответствующую отрицательной компоненте r1 = –1/2. И первый столбец в последней таблице становится разрешающим. Для выбора разрешающей строки найдем:
Минимальное из отношений соответствует первой строке. Сделав один шаг симплексных преобразований с разрешающим элементом а11=1/2, получим таблицу:
БП
| Переменные
| Свободный
член
|
|
|
|
|
|
|
|
|
|
| –1
|
|
|
|
| –3
|
| –2
|
|
|
|
| –1
|
|
|
|
|
|
|
|
|
|
| Из таблицы следует, что полученный опорный план:
является единственным оптимальным планом задачи, так как r =(1; 1)>0. При этом значение функции уменьшилось:
.
Итак, решением исходной задачи является:
а Z max = –Z1min=9.
Дадим геометрическую интерпретацию процесса нахождения решения. Для этого прежде всего перейдем от канонической формы модели:
при ограничениях:
к стандартной форме модели данной задачи. Это нетрудно сделать, так как система ограничений задачи уже приведена к единичному базису.
Выразим из системы ограничений базисные переменные через свободные:
и, подставив вместо х3, х4, х5 их выражения в функцию цели Z, получим:
.
Стандартная форма модели примет вид
при ограничениях:
Решение последней задачи можно найти, используя геометрическую интерпретацию решения ЗЛП, приведенную на рисунке.
Геометрическая интерпретация симплекс-метода
Исходный опорный план
соответствует точке О (0,0) ОДР.
После одного шага симплекс-метода (одной итерации) был получен новый опорный план
,
которому соответствует точка А ( ).
На рисунке переход от одного опорного плана (вершины) к другому опорному плану происходит по ребру ОА.
После второй итерации получен план
,
который является оптимальным. Он соответствует на чертеже точке В, т.е. осуществлен переход от точки А к точке В по ребру АВ.
Пример 3. Решить симплекс-методом ЗЛП:
Решение. Особенностью данной задачи является то, что система ограничений не приведена к базисному виду, нет разграничения переменных на базисные и свободные (есть только одна базисная переменная х4), поэтому прежде всего с помощью преобразований Жордана–Гаусса приведем систему к базисному виду. Для этого коэффициенты системы ограничений и целевой функции Z1= –Z занесем в таблицу:
БП
| Переменные
| Свободный
член
|
|
|
|
|
|
|
|
|
|
|
| –1
| –1
|
|
|
|
|
|
|
|
| –2
| –1
|
| –1
|
| За разрешающий столбец выберем любой столбец, содержащий хотя бы один положительный элемент, например первый.
Выбор разрешающей строки осуществим по тому же правилу, что при переходе от одного опорного решения к другому. Это правило гарантирует, что свободные члены новой таблицы останутся неотрицательными.
Имеем
т.е. за разрешающую строку примем вторую, а за разрешающий элемент а21=1. Выполнив шаг преобразований Жордана–Гаусса, придем к таблице:
БП
| Переменные
| Свободный член
|
|
|
|
|
|
|
|
|
|
|
|
| –1
| –1
|
|
|
|
|
|
|
|
|
|
| –3
| –2
| –1
|
| Система, записанная в данной таблице, разрешена относительно х1 и х4, но так как она содержит три уравнения, то необходимо ввести в базис еще одну переменную (х2 или х3) и при этом иметь в качестве разрешающей третью строку. Посмотрим, какой столбец с этой точки зрения следует брать за разрешающий. Если возьмем второй столбец, то за разрешающую строку следует выбрать третью (благоприятный случай):
Если же возьмем третий столбец, то за разрешающую строку также следует выбрать третью:
следовательно, можно выбрать любой из них. Выберем, например, второй столбец и, выполнив шаг преобразований Жордана–Гаусса с разрешающим элементом а32= 2, придем к таблице:
БП
| Переменные
| Cвободный
член
член
| х1
| х2
| х3
| х4
| х4
|
|
| –1
|
|
| х1
|
|
| 1/2
|
| 1/2
| х2
|
|
| 3/2
|
| 1/2
| Z1
|
|
| 5/2
| –1
| 3/2
| Теперь система приведена к базисному виду, базисными переменными являются х1,х2, х4, свободной – х3. Все свободные члены положительны, поэтому можем записать первоначальный опорный план:
Чтобы ответить, является ли он оптимальным, необходимо выполнить еще один шаг преобразований с разрешающим элементом а14 = 1, чтобы выразить целевую функцию Z1 только через свободную переменную х3. Получим новую таблицу:
БП
| Переменные
| Cвобод-ный член
член
| х1
| х2
| х3
| х4
| х4
|
|
| –1
|
|
| х1
|
|
| 1/2
|
| 1/2
| х2
|
|
| 3/2
|
| 1/2
| Z1
|
|
| 3/2
|
| 5/2
|
Опорное решение
содержащееся в таблице, является оптимальным, так как вектор r = (3/2) содержит одну положительную компоненту. Минимальное значение целевой функции:
и, очевидно, .
Итак, .
1 |
|