Линейная и векторная алгебра Кратные интегралы Математическая статистика Математический анализ

Симплексный метод

Общая постановка задачи

Метод является универсальным, так как позволяет решить практически любую задачу линейного программирования, записанную в каноническом виде.

Идея симплексного метода (метода последовательного улучшения плана) заключается в том, что начиная с некоторого исходного опорного решения осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному. Значение целевой функции при этом перемещении для задач на максимум не убывает. Так как число опорных решений конечно, то через конечное число шагов получим оптимальное опорное решение. Опорным решением называется базисное неотрицательное решение. Задача 4. Дана функция двух переменных: z = x2 – xy + y2 – 4x + 2y + 5 и уравнения границ замкнутой области D на плоскости xОy: x = 0, y = –1,

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

1. Математическая модель задачи должна быть канонической. Если она неканоническая, то ее надо привести к каноническому виду.

2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу (табл. 21.1). Все строки таблицы 1-го шага, за исключением строки Δj (индексная строка), заполняем по данным системы ограничений и целевой функции.

Индексная строка для переменных находится по формуле

и по формуле

Возможны следующие случаи при решении задачи на максимум:

— если все оценки Δj ≥ 0, то найденное решение оптимальное;

— если хотя бы одна оценка Δj ≤ 0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращаем, так как L() → , т.е. целевая функция неограничена в области допустимых решений;

— если хотя бы одна оценка отрицательная, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению;

— если отрицательных оценок в индексной строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка.

Если хотя бы одна оценка Δk < 0, то k-й столбец принимаем за ключевой. За ключевую строку принимаем ту, которой соответствует минимальное отношение свободных членов (bi) к положительным коэффициентам k-гo столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называется ключевым элементом.

3. Заполняем симплексную таблицу 2-го шага:

— переписываем ключевую строку, разделив ее на ключевой элемент;

— заполняем базисные столбцы;

— остальные коэффициенты таблицы находим по правилу "прямоугольника"*. Оценки можно считать по приведенным выше формулам или по правилу "прямоугольника" Получаем новое опорное решение, которое проверяем на оптимальность, и т.д.

* Правило "прямоугольника" заключается в следующем. Пусть ключевым элементом 1-го шага является элемент 1-й строки (m + 1)-го столбца h1,m+1. Тогда элемент i-й строки (m + 2)-го столбца 2-го шага — обозначим его h’i,m+2 — согласно правилу "прямоугольника" выражается формулой

где hi,m+2, hi,m+1, h1,m+1 — элементы 1-го шага.

Примечание. Если целевая функция L() требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок Δj при всех j = .

 

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

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

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

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

Решение. Составим математическую модель задачи. Обозначим: x1 — время работы предприятия первым способом, x2 — время работы предприятия вторым способом.

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

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

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

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

Составляем симплексную таблицу 1-го шага (табл. 21.3).

Получим решение:

В индексной строке Δj имеются две отрицательные оценки, значит, найденное решение не является оптимальным и его можно улучшить. В качестве ключевого столбца следует принять столбец базисной переменной х2, а за ключевую строку взять строку переменной x3, где min (4/2,3/l, 8/1) = min (2, 3, 8) = 2.

Ключевым элементом является (2). Вводим в столбец базисной переменной х2, выводим х3. Составляем симплексную таблицу 2-го шага (табл. 21.4).

Получим

В индексной строке имеется одна отрицательная оценка. Полученное решение можно улучшить. Ключевым элементом является (1/2). Составляем симплексную таблицу 3-го шага (табл. 21.5).

Все оценки свободных переменных Δj ≥ 0, следовательно, найденное опорное решение является оптимальным:

Таким образом, по первому способу предприятие должно работать два месяца, по второму — один месяц, при этом максимальный выпуск продукции составит 10 тыс. ед.

Альтернативный оптимум

При решении задач линейного программирования симплексным методом критерием оптимальности является условие Δj ≥ 0 для задач на максимум и условие Δj < 0 для задач на минимум. Если на каком-то шаге окажется, что хотя бы одна оценка свободной переменной Δj = 0, а все остальные Δj > 0 для задач на максимум (Δj < 0 для задач на минимум), то, приняв в качестве ключевого столбца столбец, где Δj = 0, и найдя новое оптимальное решение, заметим, что значение целевой функции при этом не изменится. Говорят, что в этом случае задача имеет альтернативный оптимум.

Критерием альтернативного оптимума при решении задач симплексным методом является равенство нулю хотя бы одной оценки свободной переменной (Δj = 0).

Если только одна оценка свободной переменной равна нулю, то решение находится по формуле

где 0 ≤ t ≤ 1.

Если две оценки и более, например S, свободных переменных равны нулю, то оптимальное решение определяется по формуле

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

Пример. Дана задача линейного программирования

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

Решение. Составим симплексную таблицу (табл. 21.6).

В индексной строке имеется одна положительная оценка. Полученное решение можно улучшить. Ключевым элементом является (4). Составляем симплексную таблицу 2-го шага (табл. 21.7).

Получаем

Так как Δ2 = 0, то задача имеет альтернативный оптимум. Найдем еще одно оптимальное решение, введя вместо базисной переменной х1 свободную переменную х2 (табл. 21.8).

Получаем

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

Давая t значения из [0,1], получим различные опт, при которых L() = -12.

УПРАЖНЕНИЯ

Решить следующие задачи симплексным методом.

21.1. L() = x1 — 3x2 — 5x3 — х4 → max при ограничениях:

21.2. L() = x1 + 2x2 + 3x3 → min при ограничениях:

21.3. L() = —2x1 — x2 + x3 + x4 → max при ограничениях:

21.4. L() = 3x1 + x2 + 2x3 → min при ограничениях:

21.5. L() = x1 + х2 + x3 → max при ограничениях:

21.6. L() = x1 + 2х2 + 2х3 → min при ограничениях:

21.7. L() = 3x1 + x2 + x3 + x4 → max при ограничениях:

21.8. L() = x1 - 5x2 – x3 → max при ограничениях:

21.9. L() = x1 + х2 + x3 + x4 → min при ограничениях:

21.10. L() = 3x1 + 5x2 + 4x3 → max при ограничениях:

21.11. Механический завод при изготовлении двух типов деталей использует токарное, фрезерное и сварочное оборудование. При этом обработку каждой детали можно вести двумя различными технологическими способами. Необходимые исходные данные приведены в табл. 21.9.

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

21.12. Торговая фирма для продажи товаров трех видов использует ресурсы: время и площадь торговых залов. Затраты ресурсов на продажу одной партии товаров каждого вида даны в табл. 21.10. Прибыль, получаемая от реализации одной партии товаров 1-го вида, — 5 усл. ед., 2-го вида — 8 усл. ед., 3-го вида — 6 усл. ед.

Определить оптимальную структуру товарооборота, обеспечивающую фирме максимальную прибыль.

21.13. Фирма выпускает четыре пользующихся спросом изделия, причем месячная программа выпуска составляет 10 изделий типа 1 и 3, 200 изделий типа 2 и 120 изделий типа 4. Нормы затрат сырья на единицу различных типов изделий приведены в табл. 21.11.

Прибыль от реализации изделий типа 1 равна 6 усл. ед., изделий типа 2 — 2 усл. ед., изделий типа 3 — 2,5 усл. ед. и изделий типа 4 — 4 усл. ед.

Определить, является ли месячная программа выпуска изделий оптимальной, и если нет, то определить оптимальную месячную программу и дополнительный доход, который фирма может при этом получить.

21.14. Металлургический завод из металлов A1, A2, А3 может выпускать сплавы B1, В2, В3. В течение планируемого периода завод должен освоить не менее 640 т металла A1 и 800 т металла А2, при этом металла А3 может быть израсходовано не более 860 т.

Определить минимальные затраты, если данные о нормах расхода и себестоимость даны в табл. 21.12.

21.15. Ткань трех артикулов производится на ткацких станках двух типов с различной производительностью. Для изготовления ткани используются пряжа и красители. В табл. 21.13 указаны мощности станков в тысячах станко-часов, ресурсы пряжи и красителей в 1000 кг, производительности станков в метрах за час, нормы расхода пряжи и краски в килограммах на 1000 м и цена 1 м ткани.

По этим исходным данным решить следующие задачи:

определить оптимальный ассортимент, максимизирующий товарную продукцию предприятия;

приняв условие, что количество тканей трех артикулов находится в отношении 2:1:3, определить, какое максимальное количество комплектов ткани может выпустить предприятие;

определить оптимальный ассортимент, максимизирующий доход предприятия, если цена 1 м ткани составляет 8, 5 и 15 усл. ед. соответственно;

решить задачу (1) при условии, что станки 1-го типа ткань первого артикула не производят.


На главную