Примеры решения задач симплекс-методом

Дата добавления: 2014-11-24 | Просмотров: 1531

Подавляющее большинство активной аудитории группы – жители города Конаково. Значительная часть пользователей проживает в Москве, Дубне или Твери, но регулярно приезжает в город. Большинство участников сообщества, проживающих в Конаковском районе, приходится на Завидовское, Вахонинское, Селиховское и Дмитрогорское сельские поселения. Есть пользователи из поселков Новозавидовский, Редкино, Козлово и с. Городня. В остальных населённых пунктах Конаковского района группа не пользуется популярностью.

Участники сообщества.
На 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 единиц. Нормы расхода сырья на изготовление каждого типа продукции, а также доход, полученный от выпуска единицы каждого типа продукции, заданы таблицей:

Составить план производства, обеспечивающий фирме наибольший суммарный доход.

Решение. Обозначим через план выпуска продукции. Математическая модель задачи примет вид:

.

Преобразуем ее к каноническому виду. Введем две дополнительные (балансовые) неотрицательные переменные х₅ и х₆ и перейдем к функции Z₁= – Z. Модель примет вид:

.

Поиск решения ЗЛП состоит из следующих этапов: нахождение первоначального опорного плана, проверка полученного опорного плана на оптимальность и переход от одного опорного плана к другому, если найденный опорный план не является оптимальным.

1. Запишем условия задачи в виде симплексной таблицы:

БП	Переменные	Свободный член
х1	х2	х3	х4	х5	х6
х5
х6
Z1	–15	–5	–3	–20

Так как все свободные члены неотрицательны, то таблица содержит первоначальный опорный план. Его получим, положив свободные переменные равными нулю: при этом базисные переменные равны значениям соответствующих свободных членов. Имеем:

2. Выпишем вектор , компонентами которого являются коэффициенты при свободных переменных целевой функции:

.

Все компоненты вектора r отрицательны, следовательно, первоначальный опорный план не является оптимальным.

3. Выберем максимальную по модулю отрицательную компоненту вектора r:

.

Ей соответствует четвертый столбец таблицы. Анализируем коэффициенты вектора-столбца коэффициентов при х₄. Они положительны: а₁₄=4, а₂₄=1. Есть возможность перейти к новому опорному плану, выведя из свободных переменных х_4.

Выбираем четвертый столбец за разрешающий и переходим к п. 4.

4. Для выбора разрешающей строки составляем неотрицательные отношения

и выбираем среди них минимальное:

.

Разрешающей строкой будет первая, разрешающим элементом – элемент а₁₄= 4.

5. Выполняя симплексное преобразование с разрешающим элементом а₁₄=4, придем к новой таблице:

Таблица содержит новый опорный план:

.

Видим, что все компоненты вектора r=(5, 5, 2, 5) положительные, следовательно, этот опорный план является оптимальным, при этом Z_{1 min=} – 6000.

Обратимся к исходной модели. В ней содержится 4 ограничения и целевая функция Z= – Z₁. Оптимальным решением исходной задачи будет:

,

при этом Z _max=6000.

Пример 2. Решить симплекс-методом задачу:

при ограничениях:

и дать геометрическую интерпретацию процесса решения.

Решение. Прежде всего, необходимо перейти к минимизации целевой функции. Для этого введем в рассмотрение функцию

Z₁= – Z.

Тогда

В системе ограничений уже выделены базисные переменные х₃ , х₄ и х₅. Теперь все исходные данные поместим в таблицу:

БП	Переменные	Свободный член
	–2	–1		–1

В клетку на пересечении Z₁-строки и столбца “Свободный член” запишем свободный член целевой функции с противоположным знаком. В данном случае он равен 0.

Приравняв свободные переменные нулю х₁=х₂=0, получим базисное решение системы ограничений:

где х₃=5, х₄=9, х₅=7.

Так как то базисное решение Х¹ является опорным решением (планом) задачи. Итак, первоначальное опорное решение найдено.

Для проверки его на оптимальность выразим функцию цели Z₁ через свободные переменные х₁ и х₂. Для исключения переменной х₃ из функции цели Z возьмем за разрешающий элемент а₁₃=1 в третьем столбце предыдущей таблицы. Сделав один шаг преобразований Жордана–Гаусса, придем к таблице вида:

БП	Переменные	Свободный член
	–3	–2		–1		–5

Сделав аналогично еще два шага исключения неизвестных х₄ и х₅ из функции цели Z₁, придем к таблице:

БП	Переменные	Свободный член
	x2
x5
	–2	–3				–3

Из таблицы видно, что

Z₁(Х⁽¹⁾)=3, r =(–2; –3).

Так как условие не выполняется, то полученный опорный план Х⁽¹⁾ не является оптимальным.

Необходимо перейти к новому опорному плану, для которого значение функции уменьшится. Для перехода к следующему опорному плану нужно одну из свободных переменных (х₁ либо х₂) перевести в базис, а одну из базисных (х₃, либо х₄, либо х₅) перевести в свободные. Выбор свободной переменной, вводимой в базис, определяется максимальной по модулю отрицательной компонентой вектора r= (–2; –3).

Компоненте r₂= –3 соответствует в таблице переменная х₂, которая вводится в базис, и второй столбец становится разрешающим.

Для выбора разрешающей строки вычислим

.

Итак, третья строка стала разрешающей, а разрешающим элементом стал элемент а₃₂=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

Значение же функции цели Z₁ уменьшилось от значения Z₁ = 3 до значения Z₁ = –15/2. (Напомним, что значение функции цели из таблицы берется с противоположным знаком.)

Очевидно, что на следующем шаге необходимо в базис ввести переменную х₁, соответствующую отрицательной компоненте r₁ = –1/2. И первый столбец в последней таблице становится разрешающим. Для выбора разрешающей строки найдем:

Минимальное из отношений соответствует первой строке. Сделав один шаг симплексных преобразований с разрешающим элементом а₁₁=1/2, получим таблицу:

БП	Переменные	Свободный член
					–1
			–3		–2
			–1

Из таблицы следует, что полученный опорный план:

является единственным оптимальным планом задачи, так как r =(1; 1)>0. При этом значение функции уменьшилось:

.

Итак, решением исходной задачи является:

а Z _max = –Z_1min=9.

Дадим геометрическую интерпретацию процесса нахождения решения. Для этого прежде всего перейдем от канонической формы модели:

при ограничениях:

к стандартной форме модели данной задачи. Это нетрудно сделать, так как система ограничений задачи уже приведена к единичному базису.

Выразим из системы ограничений базисные переменные через свободные:

и, подставив вместо х₃, х₄, х₅ их выражения в функцию цели Z, получим:

.

Стандартная форма модели примет вид

при ограничениях:

Решение последней задачи можно найти, используя геометрическую интерпретацию решения ЗЛП, приведенную на рисунке.

Геометрическая интерпретация симплекс-метода

Исходный опорный план

соответствует точке О (0,0) ОДР.

После одного шага симплекс-метода (одной итерации) был получен новый опорный план

,

которому соответствует точка А ( ).

На рисунке переход от одного опорного плана (вершины) к другому опорному плану происходит по ребру ОА.

После второй итерации получен план

,

который является оптимальным. Он соответствует на чертеже точке В, т.е. осуществлен переход от точки А к точке В по ребру АВ.

Пример 3. Решить симплекс-методом ЗЛП:

Решение. Особенностью данной задачи является то, что система ограничений не приведена к базисному виду, нет разграничения переменных на базисные и свободные (есть только одна базисная переменная х₄), поэтому прежде всего с помощью преобразований Жордана–Гаусса приведем систему к базисному виду. Для этого коэффициенты системы ограничений и целевой функции Z₁= –Z занесем в таблицу:

БП	Переменные	Свободный член
	–1	–1
	–2	–1		–1

За разрешающий столбец выберем любой столбец, содержащий хотя бы один положительный элемент, например первый.

Выбор разрешающей строки осуществим по тому же правилу, что при переходе от одного опорного решения к другому. Это правило гарантирует, что свободные члены новой таблицы останутся неотрицательными.

Имеем

т.е. за разрешающую строку примем вторую, а за разрешающий элемент а₂₁=1. Выполнив шаг преобразований Жордана–Гаусса, придем к таблице:

БП	Переменные	Свободный член
		–1	–1
		–3	–2	–1

Система, записанная в данной таблице, разрешена относительно х₁ и х₄, но так как она содержит три уравнения, то необходимо ввести в базис еще одну переменную (х₂ или х₃) и при этом иметь в качестве разрешающей третью строку. Посмотрим, какой столбец с этой точки зрения следует брать за разрешающий. Если возьмем второй столбец, то за разрешающую строку следует выбрать третью (благоприятный случай):

Если же возьмем третий столбец, то за разрешающую строку также следует выбрать третью:

следовательно, можно выбрать любой из них. Выберем, например, второй столбец и, выполнив шаг преобразований Жордана–Гаусса с разрешающим элементом а₃₂= 2, придем к таблице:

Теперь система приведена к базисному виду, базисными переменными являются х₁,х₂, х₄, свободной – х₃. Все свободные члены положительны, поэтому можем записать первоначальный опорный план:

Чтобы ответить, является ли он оптимальным, необходимо выполнить еще один шаг преобразований с разрешающим элементом а₁₄ = 1, чтобы выразить целевую функцию Z₁ только через свободную переменную х₃. Получим новую таблицу:

Опорное решение

содержащееся в таблице, является оптимальным, так как вектор r = (3/2) содержит одну положительную компоненту. Минимальное значение целевой функции:

и, очевидно, .

Итак, .