ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
ГРАФИЧЕСКИЙ МЕТОД
Фирма выпускает 2 вида мороженого: сливочное и шоколадное. Для изготовления мороженого используются два исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы даны в табл. 20.1.
Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого 16 р., шоколадного — 14 р.
Какое количество мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным?
Решение. Обозначим: x1 — суточный объем выпуска сливочного мороженого, кг; x2 — суточный объем выпуска шоколадного мороженого, кг.
Составим математическую модель задачи.
Целевая функция будет иметь вид
при ограничениях:
OABDEF — область допустимых решений (рис. 20.1). Строим вектор (1, 1). Линия уровня L0 задается уравнением
Перемещаем линию уровня по направлению вектора . Точкой выхода L0 из области допустимых решений является точка D, ее координаты определяются как пересечение прямых, заданных уравнениями:
Решая систему, получим координаты точки D (312,5; 300), в которой и будет оптимальное решение, т.е.
при этом
Таким образом, фирма должна выпускать в сутки 312,5 кг сливочного мороженого и 300 кг шоколадного мороженого, при этом доход от реализации составит 9 200 р.
Решить задачи с использованием графического метода.
1. L() = 3x1 + х2→ max при ограничениях:
2. L() = 2x1 — 10x2 → min при ограничениях:
3.Обработка деталей А и В может производиться на трех станках, причем каждая деталь должна последовательно обрабатываться на каждом из станков. Прибыль от реализации детали А — 100 р., детали В — 160 р. Исходные данные приведены в табл. 20.4.
Определить производственную программу, максимизирующую прибыль при условии: спрос на деталь А — не менее 300 шт., на деталь В — не более 200 шт.
СИМПЛЕКСНЫЙ МЕТОД
Предприятие располагает тремя производственными ресурсами (сырьем, оборудованием, электроэнергией) и может организовать производство продукции двумя различными способами. Расход ресурсов за один месяц и общий ресурс при каждом способе производства даны в табл. 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 тыс. ед.
Пример. Дана задача линейного программирования
при ограничениях:
Решение. Составим симплексную таблицу (табл. 21.6).
В индексной строке имеется одна положительная оценка. Полученное решение можно улучшить. Ключевым элементом является (4). Составляем симплексную таблицу 2-го шага (табл. 21.7).
Получаем
Так как Δ2 = 0, то задача имеет альтернативный оптимум. Найдем еще одно оптимальное решение, введя вместо базисной переменной х1 свободную переменную х2 (табл. 21.8).
Получаем
ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
Симметричные двойственные задачи
Рассмотрим решение задач с использованием теорем двойственности.
Решим исходную задачу графическим методом, получим опт = (4, 1), при этом L( )mах = 3.
На основании 1-й теоремы двойственности
Так как x1, х2 > 0, то по 2-й теореме двойственности систему ограничений двойственной задачи можно записать в виде равенств:
Подставим опт в систему ограничений исходной задачи:
Тогда система ограничений двойственной задачи примет вид
Откуда опт = (0, 2/3, 1/3), при этом S( )min = 3.
Пусть дано решение двойственной задачи опт = (0, 2/3, 1/3), S( )min = 3, найдем решение исходной.
По 1-й теореме двойственности L( )max = S( )min = 3. Так как у2, y3 > 0, то по 2-й теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства:
Откуда опт = (4,1), при этом L( )mах = 3.
Рассмотрим решение задач методом, основанным на взаимно однозначном соответствии между переменными: основным переменным исходной задачи соответствуют балансовые переменные двойственной, и наоборот. Для этого решим двойственную задачу симплексным методом:
при ограничениях:
Из табл. 22.1 следует, что опт = (0, 2/3, 1/3), S( )min = 3.
На основании 1-й теоремы двойственности получаем
Решение другой задачи найдем по соответствию между переменными:
Значение xj определяем по последней симплексной таблице в строке Δi в соответствующем столбце, причем значения xj берем по модулю:
Таким образом, решение исходной задачи:
Если исходная задача решена симплексным методом, то решение двойственной задачи может быть найдено по формуле
где С — матрица-строка коэффициентов при базисных переменных целевой функции в оптимальном решении исходной задачи; А-1 — обратная матрица для матрицы А, являющейся матрицей коэффициентов базисных переменных системы ограничений исходной задачи в оптимальном решении.
Решим симплексным методом исходную задачу вида
при ограничениях:
Из табл. 22.2 следует, что опт = (4,1), L( )max = 3. Матрицы записываются в виде
тогда
Таким образом, решение двойственной задачи следующее:
Несимметричные двойственные задачи
Рассмотрим решение задач с использованием теорем двойственности.
Решив двойственную задачу графическим методом, получим
По 1-й теореме двойственности L( )min = S( )max = 33/2.
Подставим опт в систему ограничений двойственной задачи:
Так как х3 = х4 = 0, то система ограничений исходной задачи примет вид
Решая данную систему, получим
Рассмотрим решение задач с использованием обратной матрицы.
Пусть решение исходной задачи
Решение двойственной задачи найдем по формуле
где
Таким образом, oпт = (1/2, 2), при этом S( )max = 33/2.
Решение смешанных двойственных задач
Смешанные двойственные задачи можно решать с использованием теорем двойственности.
Найдем оптимальное решение двойственной задачи:
По 1-й теореме двойственности
Так как х1 > 0, x3 > 0, то по 2-й теореме двойственности первое и третье ограничения двойственной задачи выполняются в виде равенств:
Стратегическое планирование выпуска изделий с учетом имеющихся ресурсов
Фирма выпускает три вида изделий, располагая при этом сырьем 4 типов: А, Б, В, Г соответственно в количествах 18, 16, 8 и 6 т. Нормы затрат каждого типа сырья на единицу изделия первого вида составляют соответственно 1, 2, 1, 0, второго вида — 2, 1, 1, 1 и третьего вида — 1, 1, 0, 1. Прибыль от реализации единицы изделия первого вида равна 3 усл. ед., второго — 4 усл. ед., третьего — 2 усл. ед.
Требуется:
1) составить план производства трех видов, максимизирующих прибыль;
2) определить дефицитность сырья;
3) установить размеры максимальной прибыли при изменении сырья А на 6 т, Б — на 3 т, В — на 2 т, Г — на 2 т. Оценить раздельное влияние этих изменений и суммарное их влияние на прибыль;
4) оценить целесообразность введения в план производства фирмы нового вида изделий (четвертого), нормы затрат на единицу которого соответственно равны 1, 2, 2, 0, а прибыль составляет 15 усл. ед.
Решение. 1. Обозначим через = (x1, x2, x3) план производства изделий трех видов, тогда математическая модель задачи примет вид
при ограничениях:
Решаем задачу симплексным методом, при этом последняя таблица будет иметь вид табл. 22.3.
Из таблицы следует
Согласно теоремам двойственности
2. Наиболее дефицитным является сырье типа В, для которого двойственная оценка у3 = 2. Менее дефицитным является сырье вида Б, для которого у2 = 1/2. Совсем не дефицитным является сырье A (y1 = 0).
Для определения интервала устойчивости оценок найдем обратную матрицу для матрицы коэффициентов при базисных переменных в оптимальном решении системы ограничений. Базисными переменными в оптимальном решении являются x1, x2, х3, x4. Матрица коэффициентов при этих переменных в системе ограничений имеет вид
Тогда обратная матрица для матрицы А следующая:
Найдем интервал устойчивости оценок по видам сырья:
Интервал устойчивости оценок по отношению к первому ограничению:
Аналогично определим интервалы устойчивости оценок по отношению к ограничениям остальных видов сырья:
Интервалы устойчивости оценок по отношению ко второму ограничению:
к третьему ограничению:
к четвертому ограничению:
3. Изменения сырья согласно условиям задачи на +6, -3, +2, +2 т приводят к ограничению запаса сырья до 24, 13, 10, 8 т соответственно. Поскольку эти изменения находятся в пределах устойчивости оценок, на что указывают интервалы, то раздельное их влияние на прибыль определяется по формуле
тогда
Суммарное влияние на прибыль:
Если изменение сырья не находится в пределах устойчивости оценок, то необходимо найти новые условные оценки, т.е. решить задачу симплексным методом с изменением количества сырья соответствующих видов.
4. Для оценки целесообразности введения в план производства фирмы четвертого вида изделий используем формулу
Так как прибыль превышает затраты, то введение в план производства четвертого вида изделий целесообразно.
Для следующих задач составить математические модели двойственных задач и по решению исходной найти оптимальное решение двойственной.
1. L( ) = x1 + 3x3 + 3x4 → min при ограничениях:
2. L( ) = 2х1 + х2 – 3x3 + х4 → max при ограничениях:
3. L( ) = -х1 + x2 + 6x3 — х4 → min при ограничениях:
4. L( ) = -3x2 + х3 – х4 → max при ограничениях:
5. Для производства трех изделий А, В и С используются три вида сырья. Каждый из них используется в объеме, не превышающем 180, 210 и 236 кг. Нормы затрат каждого из видов сырья на одно изделие и цена единицы изделий приведены в табл. 22.4.
Определить план выпуска изделий, обеспечивающий получение максимального дохода.
Составить для данной задачи двойственную и найти:
1) оптимальный план двойственной задачи;
2) интервалы устойчивости двойственных оценок;
3) увеличение максимального дохода при увеличении количества сырья 2-го и 3-го видов на 80 и 160 кг соответственно и при уменьшении количества сырья 1-го вида на 40 кг. Оценить раздельное и суммарное влияние этих изменений;
4) целесообразность введения в план производства 4-го изделия, нормы затрат сырья на одно изделие которого составляют 2, 4 и 6 кг, а цена изделия равна 18 усл. ед.;
5) оптимальные планы исходной и двойственной задач, если количество сырья 1, 2 и 3 равно 140, 250 и 240 кг соответственно.
Таблица для решения задачи симплекс-методом.
i
| Ci
| Б
| bi
|
|
|
|
|
|
| X1
| X2
| X3
| X4
| X5
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| i
| Ci
| Б
| bi
|
|
|
|
|
|
| X1
| X2
| X3
| X4
| X5
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| i
| Ci
| Б
| bi
|
|
|
|
|
|
| X1
| X2
| X3
| X4
| X5
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| i
| Ci
| Б
| bi
|
|
|
|
|
|
| X1
| X2
| X3
| X4
| X5
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|