Упражнения

Найти целочисленное решение следующих задач.

24.1. L() = 16x₁ + 9x₂ → max при ограничениях:

24.2. L() = 2x₁ + 3x₂ → min при ограничениях:

24.3. L() = 3x₁ + x₂ → max при ограничениях:

24.4. L() = 4x₁ + х₂ → max при ограничениях:

24.5. L() = x₁ + х₂ → max при ограничениях:

24.6. L() = 4x₁ + 5x₂ + x₃ → max при ограничениях:

24.7. L()= x₁ — 2x₂ + x₃ + 3x₄ → max при ограничениях:

24.8. Фирма выпускает три вида изделий А, Б, В, причем пла­новый сменный выпуск составляет 9 шт. изделия А, 7 шт. из­делия Б, 6 шт. изделия В.

Сменные ресурсы: 51 ед. производственного оборудования, 48 ед. сырья, 67 ед. электроэнергии, их расход на одно изделие дан в табл. 24.3.

Прибыль от реализации изделий А — 40 усл. ед., Б — 50 усл. ед., В — 10 усл. ед.

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

24.9. Для приобретения оборудования по сортировке зерна фер­мер выделяет 34 усл. ед. Оборудование должно быть размеще­но на площади, не превышающей 60 м².

Фермер может заказать оборудование двух видов: менее мощные машины А стоимостью 3 усл. ед., требующие произ­водственной площади 3 м² (с учетом проходов) и обеспечиваю­щие производительность за смену 2 т зерна, и более мощные машины В стоимостью 4 усл. ед., занимающие площадь 5 м² и обеспечивающие за смену сортировку 3 т зерна.

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

24.10. Три типа самолетов следует распределить между че­тырьмя авиалиниями. В табл. 24.4 приведены данные месяч­ного объема перевозок каждым самолетом на каждой линии и соответствующих эксплуатационных расходов.

Распределить самолеты по линиям так, чтобы при мини­мальных суммарных эксплуатационных расходах перевезти по каждой из четырех авиалиний не менее 300, 200, 1000 и 500 ед. груза соответственно.

Глава 25. Параметрическое линейное программирование

25.1. Постановка задачи

Общая задача линейного программирования имеет вид

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

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

25.2. Линейное программирование с параметром в целевой функции

Пусть коэффициент c_j целевой функции изменяется в пре­делах (c_j — c'_j,c_j + с''_j), тогда для удобства решения задачи его можно заменить выражением

где c'_j, с''_j — постоянные; λ — параметр, который изменяется в некоторых пределах (в общем случае от -до).

В общем виде задача линейного программирования с пара­метром в целевой функции записывается так:

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

Для каждого значения λ в промежутке δ ≤ λ ≤ φ, где δ и φ — произвольные действительные числа, найти вектор (x₁, x₂,..., x_п), удовлетворяющий системе ограничений и об­ращающий в максимум (минимум) целевую функцию.

Решая задачу на максимум симплексным методом и иссле­дуя ее решение в зависимости от изменения параметра λ, полу­чим выражения для определения нижнего (λ₁) и верхнего (λ₂) его значений:

где Δ"_j, — оценка симплексной таблицы, содержащая пара­метр λ; Δ'_j — оценка симплексной таблицы, не содержащая параметр λ.

Если для целевой функции отыскивается min, то границы изменения λ (λ₁ и λ₂) определяются следующим образом:

Приведем алгоритм решения.

1. Задачу решаем симплекс-методом при конкретном зна­чении параметра λ до получения оптимального решения.

2. Вычисляем значения параметров λ₁, λ₂.

3. Определяем множество значений параметра λ, для кото­рых полученное решение является оптимальным.

4. В случае необходимости в базис вводим вектор, соответ­ствующий столбцу, из которого определялось значение параметра λ₂.

5. Выбираем ключевую строку и ключевой элемент.

6. Определяем новое оптимальное решение.

7. Находим новое множество значений λ, для которых ре­шение останется оптимальным.

8. Процесс вычисления повторяем до тех пор, пока весь от­резок [δ, φ] не будет исследован.

Выясним геометрический смысл задачи.

Пусть L() = (c'_j + λc''_jx_j) → max. ABCDEF — область допустимых решений (рис. 25.1). При λ = 0 строим вектор и, перемещая линию уровня MN по направлению вектора , получим в точке D оптимальное решение. Итак, (D) — оп­тимальное решение, при котором имеем L((D))_max. При различных значениях λ линия M'N', параллельная линии уров­ня MN, будет определенным образом поворачиваться вокруг точки D. Пусть при λ = λ₁ прямая M'N' проходит через сторо­ну CD многоугольника допустимых решений, а при λ = λ₂ — через сторону DE. Тогда значения (D)_опт и L((D))_max не изменятся до тех пор, пока λ₁ ≤ λ ≤ λ₂. Такая картина будет повторяться до получения нового оптимального решения, соот­ветствующего новой целевой функции, для которой существует свой диапазон изменения λ.