Сделай Сам Свою Работу на 5

ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ





ГРАФИЧЕСКИЙ МЕТОД

Фирма выпускает 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 — х4min при ограничениях:

 

 

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 Все материалы защищены законодательством РФ.