При решении задач линейного программирования симплексным методом критерием оптимальности является условие Δj ≥ 0 для задач на максимум и условие Δj < 0 для задач на минимум. Если на каком-то шаге окажется, что хотя бы одна оценка свободной переменной Δj = 0, а все остальные Δj > 0 для задач на максимум (Δj < 0 для задач на минимум), то, приняв в качестве ключевого столбца столбец, где Δj = 0, и найдя новое оптимальное решение, заметим, что значение целевой функции при этом не изменится. Говорят, что в этом случае задача имеет альтернативный оптимум.
Критерием альтернативного оптимума при решении задач симплексным методом является равенство нулю хотя бы одной оценки свободной переменной (Δj = 0).
Если только одна оценка свободной переменной равна нулю, то решение находится по формуле
где 0 ≤ t ≤ 1.
Если две оценки и более, например S, свободных переменных равны нулю, то оптимальное решение определяется по формуле
В задачах, имеющих альтернативный оптимум, возникает возможность включения в ее модель других критериев эффективности.
В индексной строке имеется одна положительная оценка. Полученное решение можно улучшить. Ключевым элементом является (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 м ткани.
По этим исходным данным решить следующие задачи:
1) определить оптимальный ассортимент, максимизирующий товарную продукцию предприятия;
2) приняв условие, что количество тканей трех артикулов находится в отношении 2:1:3, определить, какое максимальное количество комплектов ткани может выпустить предприятие;
3) определить оптимальный ассортимент, максимизирующий доход предприятия, если цена 1 м ткани составляет 8, 5 и 15 усл. ед. соответственно;
4) решить задачу (1) при условии, что станки 1-го типа ткань первого артикула не производят.