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

где r — ранг системы ограничений; hi,r+1 — коэффициент сим­плексной таблицы i-й строки, (r + 1)-го столбца; fi — свобод­ный член i-й строки.

Пусть fi и хотя бы одно hij (j = , r = ) — дроб­ные числа.

Обозначим через [fi] и [hij] целые части чисел fi и hij.

Определение 1. Целой частью числа fi называют наибольшее целое число, не превосходящее числа fi.

Дробную часть чисел fi и hij обозначим {fi} и {hij}, она определяется следующим образом:

Пример.

Если fi и хотя бы одно значение hij дробны, то с учетом введенных обозначений целых и дробных чисел дополнитель­ное ограничение по целочисленности примет вид

{hi,r+l} xr+1 + {hi, r+2} xr+2 + • • • + {hi,п} xп ≥ {fi}.

Примечания. 1) Если fi — дробное число, а все hij — целые числа, то задача линейного программирования не имеет целочисленного решения.

2) Ограничение целочисленности может быть наложено не на все переменные, а лишь на их часть. В этом случае задача является частично целочисленной.

24.2. Графический метод решения задач

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

В системе координат Х1ОХ2 находят область допустимых решений, строят вектор и линию уровня. Перемещая линию уровня по направлению для задач на максимум, находим наиболее удаленную от начала координат точку и ее коорди­наты.

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

Аналогично решается задача на минимум.

24.3. Прогнозирование эффективного использования производственных площадей

Рассмотрим следующую задачу.

Для улучшения финансового положения фирма приняла ре­шение об увеличении выпуска конкурентоспособной продук­ции, для чего принято решение об установке в одном из це­хов дополнительного оборудования, занимающего 19/3 м2 пло­щади. На приобретение дополнительного оборудования фирма выделила 10 усл. ед., при этом она может купить оборудование двух видов. Приобретение 1-го комплекта оборудования 1-го вида стоит 1,0 усл. ед., 2-го вида — 3 усл. ед. Приобретение одного комплекта оборудования 1-го вида позволяет увеличить выпуск продукции в смену на 2 шт., а одного комплекта обору­дования 2-го вида — на 4 шт. Зная, что для установки одного комплекта оборудования 1-го вида требуется 2м2 площади, а для оборудования 2-го вида — 1м2 площади, определить такой набор дополнительного оборудования, который дает возмож­ность максимально увеличить выпуск продукции.

Решение. Составим математическую модель задачи. Предположим, что фирма приобретает х1 комплектов допол­нительного оборудования 1-го вида и x2 комплектов оборудо­вания 2-го вида. Математическая модель задачи будет иметь вид

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

Получим задачу целочисленного программирования, так как неизвестных только два (x1 и x2). Найдем решение задачи графическим способом (рис. 24.1).

ОABC — область допустимых решений (ОДР). Оптималь­ное решение задача имеет в точке B (9/5, 41/15), при этом мак­симальное значение целевой функции составляет 218/15 ед. По­лученное оптимальное решение нецелочисленное.

Условию целочисленности переменных удовлетворяют ко­ординаты 12 точек. Чтобы найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник ОABC многоугольником OKEMRNF, содержащим все допус­тимые точки с целочисленными координатами.

Строим вектор (2, 4). Линию уровня перемещаем по на­правлению , получим в точке Е (1, 3) максимальное значение целевой функции:

Таким образом, фирме следует приобрести один комплект оборудования 1-го вида и три комплекта оборудования 2-го ви­да, что обеспечит ей при имеющихся ограничениях на произ­водственные площади и денежные средства максимальное уве­личение выпуска продукции, равное 14 усл. ед. в смену.

24.4. Метод Гомори

Решим эту же задачу методом Гомори, ее математическая модель:

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

Симплексная таблица представлена в табл. 24.1.

Получим

Найдем дробные части чисел 9/15 и 41/15:

Учитывая дробные части чисел 3/5 и - 1/5:

составляем дополнительное ограничение целочисленности для 1-й строки:

которое вводим в табл. 24.2.

Получим

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

Ответ. цел. = (1, 3), L() = 14.

УПРАЖНЕНИЯ

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

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

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

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

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

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

24.6. L() = 4x1 + 5x2 + x3 → max при ограничениях:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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