kopilkaurokov.ru - сайт для учителей

Создайте Ваш сайт учителя Курсы ПК и ППК Видеоуроки Олимпиады Вебинары для учителей

Симплексный метод решения задач линейного программирования

Нажмите, чтобы узнать подробности

Симплексный метод решения задач линейного программирования - универсальный метод для решения задач, условие которых записано в канонической форме

Просмотр содержимого документа
«Симплексный метод решения задач линейного программирования»

Симплекс – метод

Симплекс – метод – универсальный метод для решения задач линейного программирования, представленных в канонической форме.

В канонической форме записи все переменные неотрицательны, ограничениями являются уравнения, и требуется найти такие значения переменных xj, j=1,n, при которых целевая функция имеет максимум:

Переход к канонической форме записи можно осуществить с помощью следующих действий:

  1. Ограничения вида «». В этом случае, для перехода к уравнению в левую часть неравенства добавляют дополнительную неотрицательную переменную.

  2. Ограничения вида «» . В этом случае, для перехода к соответствующему уравнению, вычитают из левой части дополнительную неотрицательную переменную.

  3. Если в задаче какая – либо из переменных произвольна, то от нее избавляются, заменяя ее разностью двух других неотрицательных переменных. Например, для произвольной переменной , где .

  4. Если в задаче требуется найти минимум f , то заменяя f на – f, переходят к задаче максимизации, так как .



Алгоритм симплекс- метода

  1. Приводим математическую модель задачи к каноническому виду ( в случае неканонической).

  2. Находим начальное решение и проверяем его на оптимальность.

Получение начального решения:

Выбираются m переменных, называемых базисными и обладающих следующим свойством: они входят с коэффициентом 1 только в одно уравнение и с коэффициентом 0 в остальные уравнения системы :

(1)

Остальные n-m переменных называются свободными.

Все свободные переменные полагаются равными нулю, а базисные переменные – равные правым частям соответствующих ограничений системы (1).

Если все , то начальное решение является допустимым.

3. Выражение функции f только через свободные переменные:

.

4. Проверка решения на оптимальность.

Для этого составляется симплекс- таблица:

Базисные переменные


Коэффициенты при переменных

Свободные члены


X1

X2

Xm

XP

Xn


X1

a11

a12

a1m

a1p

a1n

b1

X2

a21

a22

a2m

a2p

a2p

b2

Xq

aq1

aq2

aqm

aqp

aqn

bq

Xm

am1

am2

amm

amp

amn

bm

f

-c1

-c2

-cm

-cp

-cn

0


Для проверки решения на оптимальность просматривается последняя f-строка:

4.1 Если коэффициенты, стоящие при свободных переменных неотрицательны, то полученное решение оптимально.

4.2 Если все эти коэффициенты положительны, то полученное решение единственно.

4.3 Если среди неотрицательных коэффициентов встречается хотя бы один нулевой, то задача имеет бесконечное множество решений.

4.4 Если в последней строке есть хотя бы один отрицательный коэффициент, а в соответствующем этому коэффициенту столбце нет ни одного положительного элемента, то целевая функция не ограничена в области допустимых решений. (решение прекращаем).

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

5. Получение нового решения.

5.1 Выбор переменной, вводимой в список базисных переменных.

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

5.2. Выбор переменной, выводимой из списка базисных переменных.

Находят отношение элементов столбца свободных членов к элементам разрешающего столбца. При делении на отрицательный элемент и 0 результат полагают равным +∞. Среди отношений находят минимальное. Строка соответствующая минимальному отношению, называется разрешающей. Базисная переменная, стоящая в этой строке, выводится из списка базисных переменных. Элемент, стоящий на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом.

5.3.Выполнение симплекс-преобразования и переход к новой симплекс- таблице.

Переписываем разрешающую строку, разделив ее на ключевой элемент; остальные коэффициенты таблицы находим по правилу «прямоугольника»: новый элемент = (старый элемент)×(разрешающий элемент) - × .





Элемент находится в разрешающей строке в одном столбце со старым элементом. Элемент находится в разрешающем столбце в одной строке со старым элементом.

Получаем новое опорное решение, которое снова проверяем на оптимальность и т.д. по рассмотренному алгоритму, пока не получим оптимальное решение.

Пример.

Анализ эффективности использования производственного потенциала предприятия.

Предприятие располагает тремя производственными ресурсами (сырьем, электроэнергией, оборудованием) и может организовать производство продукции двумя различными способами. Расход ресурсов за один месяц и общий ресурс при каждом способе производства даны в таблице ( в у.е.)

Производственные ресурсы

Расход ресурсов за 1 месяц при работе


Общий ресурс

1-м способом

2-м способом

Сырье

1

2

4

Оборудование

1

1

3

Электроэнергия

2

1

8


При первом способе производства предприятие выпускает за 1 месяц – 3 тыс. изделий, при втором – 4 тыс. изделий.

Сколько месяцев должно работать предприятие каждым из этих способов, чтобы при наличных ресурсах обеспечить максимальный выпуск продукции?

Решение: Пусть - время работы предприятия 1-м способом, - вторым способом.

Математическая модель задачи имеет вид:

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

Приведем задачу к каноническому виду:


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

Решение:

  1. Составляем симплекс – таблицу 1-го шага:

Базис

Свободные члены

4

1

2

1

0

0

3

1

1

0

1

0

8

2

1

0

0

1

f

0

-3

-4

0

0

0

Решение (0;0;4;3;8), L(x) = 0

Видим, что в последней строке таблицы есть отрицательные числа - переходим к пункту 2.

2)Выбираем столбец, содержащий максимальное положительное число – 4 и отмечаем его. Переходим к пункту 3.

3)Делим, свободные члены на соответствующие положительные числа из выделенного столбца и выбираем наименьшее частное:

min=(4;3;2)=2

Отмечаем строку таблицы, которая соответствует наименьшему частному. Выделяем разрешающий элемент равный 2.

4) Делим элементы выделенной строки на этот элемент и начинаем заполнять новую таблицу.

Базис

Свободные члены

2

1/2

1

1/2

0

0

1

1/2

0

-1/2

1

0

6

3/2

0

-1/2

0

1

f

8

-1

0

2

0

0

Переходим снова к шагу 1.

Базис

Свободные

члены

1

0

1

1

-1

0

2

1

0

-1

2

0

3

0

0

1

-3

1

f

10

0

0

1

2

0

min=(4;3;2)=2

Все коэффициенты в строке f положительные, значит оптимальное решение получено. X опт = (2;1;0;0;3) , f= 3*2+4=10. Таким образом, по 1-ому способу предприятие должно работать 2 месяца, по 2-ому – 1 месяц, при этом максимальный выпуск продукции составит 10 тыс. рублей.























Контрольные задания по теме

«Симплекс – метод»

Предприятие рекламирует свою продукцию с использованием 4-ех источников массовой информации: телевидения, радио, газет и расклейки объявлений. Анализ рекламной деятельности в прошлом показал, что эти средства приводят к увеличению прибыли соответственно на a, b, c и d у .е. в расчете на 1 у.е., затраченную на рекламу. На рекламу выделено N у.е. Администрация предприятия не намерена тратить на телевидение более 40%, а на радио и газеты – не более 50% общей суммы выделенных средств. Как следует предприятию организовать рекламу, чтобы получить максимальную прибыль?


№ варианта

a

b

c

d

N

1

10

5

7

4

50000

2

10

6

7

4

50000

3

10

5

6

3

60000

4

9

6

7

4

60000

5

9

6

5

4

48000

6

9

7

6

5

48000

7

9

6

5

4

52000

8

10

6

5

3

52000

9

10

5

6

3

54000

10

10

6

5

4

54000




Получите в подарок сайт учителя

Предмет: Математика

Категория: Прочее

Целевая аудитория: Прочее

Скачать
Симплексный метод решения задач линейного программирования

Автор: Трушникова Галина Петровна

Дата: 18.11.2018

Номер свидетельства: 486292

Получите в подарок сайт учителя

Видеоуроки для учителей

Курсы для учителей

ПОЛУЧИТЕ СВИДЕТЕЛЬСТВО МГНОВЕННО

Добавить свою работу

* Свидетельство о публикации выдается БЕСПЛАТНО, СРАЗУ же после добавления Вами Вашей работы на сайт

Удобный поиск материалов для учителей

Ваш личный кабинет
Проверка свидетельства