Основы математики и ее приложения в экономическом образовании (стр. 33 )

при этом величина дохода составляет

Рассмотрим увеличение ограничения по наполнителям (рис. 20.3). При перемещении параллельно самой себе прямой (20.2) вправо до пересечения с прямыми (20.1) и (20.4) в точ­ке N ограничение (20.2) будет оставаться активным. Точку N определим как точку пересечения прямых

Откуда получаем N(281,25; 350).

Предельно допустимый суточный запас наполнителей мож­но увеличивать до значения

при этом величина дохода составит

Рассмотрим возможность изменения правой части пассив­ных ограничений (20.3) и (20.4). Не изменяя оптимальное ре­шение (рис. 20.4), прямую (20.3) можно перемещать парал­лельно самой себе вверх до пересечения с точкой D(312,5; 300), т. е. правую часть ограничения (20.3) можно уменьшать до величины

Прямую (20.3) можно перемещать параллельно самой себе вниз до пересечения с осью ОХ1 в точке Р(500; 0), т. е. правую часть ограничения (20.3) можно увеличивать до 500 кг.

Таким образом, при неизменном оптимальном решении раз­ница в покупательском спросе на сливочное и шоколадное мо­роженое может изменяться в диапазоне от 12,5 до 500 кг.

Аналогично, не изменяя оптимальное решение (рис. 20.5), прямую (20.4) можно перемещать параллельно самой себе вверх до пересечения с осью ОХ2 в точке R(0; 456,25) или вниз до пересечения с прямой (20.1) в точке D(312,5; 300).

Таким образом, при неизменном оптимальном решении по­купательский спрос на шоколадное мороженое может изме­няться в диапазоне от 300 до 456,25 кг.

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

Изменение коэффициентов целевой функции оказывает вли­яние на наклон линии уровня. Уравнение линии уровня запи­сывается в общем виде (рис. 20.6):

Угловой коэффициент прямой (20.1):

Так как прямые совпадают, то К = К1, откуда c1max = 22,4 при c2 = 14. Коэффициент с1 можно уменьшать до сов­падения линии уровня с прямой (20.2), поэтому

Таким образом, оптимальное решение задачи не изменится, ес­ли розничная цена 1 кг сливочного мороженого лежит в диапа­зоне от 7 до 22,4 р., при этом доход фирмы будет от 6 387,5 до 11200 р.

Аналогичные рассуждения для случая с1 = 16 позволили сделать вывод, что оптимальное решение задачи не изменит­ся, если розничная цена 1 кг шоколадного мороженого лежит в диапазоне от 10 до 32 р., при этом доход фирмы будет от 8000 дор.

УПРАЖНЕНИЯ

Решить задачи с использованием графического метода.

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

20.2. L() = 2x1 — 10x2 → min при ограничениях:

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

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

20.5. L() = 4x1 + 6x2 → min при ограничениях:

20.6. L() = 4x2 → min при ограничениях:

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

20.8. В суточный рацион включают два продукта питания П1 и П2, причем продукта П1 должно войти в дневной рацион не более 200 ед. Стоимость 1 ед. продукта П1 составляет 2 р., про­дукта П2 — 4р. Содержание питательных веществ в 1 ед. про­дукта, минимальные нормы потребления указаны в табл. 20.2.

Определить оптимальный рацион питания, стоимость ко­торого будет наименьшей.

Провести анализ задач с использованием графического ме­тода.

20.9. L() = x1 + x2 → max (min) при ограничениях:

20.10. Фирма выпускает изделия двух типов: А и В. При этом используется сырье четырех видов. Расход сырья каждого вида на изготовление единицы продукции и запасы сырья заданы в табл 20.3.

Запасы сырья 1-го вида составляют 21 ед., 2-го вида — 4 ед., 3-го вида — 6 ед. и 4-го вида — 10 ед. Выпуск одного из­делия типа А приносит доход 300 р., одного изделия типа В — 200р.

Составить план производства, обеспечивающий фирме наи­больший доход.

20.11. Обработка деталей А и В может производиться на трех станках, причем каждая деталь должна последовательно об­рабатываться на каждом из станков. Прибыль от реализации детали А — 100 р., детали В — 160 р. Исходные данные при­ведены в табл. 20.4.

Определить производственную программу, максимизирую­щую прибыль при условии: спрос на деталь А — не менее 300 шт., на деталь В — не более 200 шт.

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

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

Идея симплексного метода (метода последовательного улуч­шения плана) заключается в том, что начиная с некоторого исходного опорного решения осуществляется последовательно направленное перемещение по опорным решениям задачи к оп­тимальному. Значение целевой функции при этом перемеще­нии для задач на максимум не убывает. Так как число опорных решений конечно, то через конечное число шагов получим оп­тимальное опорное решение. Опорным решением называется базисное неотрицательное решение.

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

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.3. Анализ эффективности использования производственного потенциала предприятия

Предприятие располагает тремя производственными ре­сурсами (сырьем, оборудованием, электроэнергией) и может организовать производство продукции двумя различными спо­собами. Расход ресурсов за один месяц и общий ресурс при каждом способе производства даны в табл. 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.4. Альтернативный оптимум

При решении задач линейного программирования сим­плексным методом критерием оптимальности является условие Δ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 при ограничениях: