Раздел 2. Детерминированные задачи

Раздел 2. Детерминированные задачи

Тема 2.1. Линейное программирование

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

2. Основная задача линейного программирования.

3. Графический метод решения задач линейного программирования

4 Симплекс-метод решения задач линейного программирования

5. Практические занятия.

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

2. Нахождение начального решения транспортной задачи.

3. Решение транспортной задачи методом потенциалов.

Приложения.

1. Решение систем m линейных неравенств с двумя переменными

***

Основная задача линейного программирования.

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

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

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

В общем виде математическая модель задачи линейного программирования (ЛП) записывается как

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

где x_j — неизвестные; a_ij, b_i, c_j — заданные постоянные вели­чины.

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

Математическая модель в более краткой записи имеет вид

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

Определение. Допустимым решением (планом) зада­чи линейного программирования называется вектор = (x ₁, x ₂,..., x_п), удовлетворяющий системе ограничений.

Множество допустимых решений образует область допус­тимых решений (ОДР).

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

Базисное допустимое решение (х ₁, х ₂ ,..., x _r, 0, …, 0) яв­ляется опорным решением, где r — ранг системы ограничений.

Математическая модель задачи ЛП может быть каноничес­кой и неканонической.

Определение.

1. Если все ограничения системы заданы урав­нениями и переменные x_j неотрицательные, то такая модель задачи называется канонической.

2. Если хотя бы одно ограничение является неравенством, то модель задачи ЛП является неканонической.

Чтобы перейти от неканонической модели к канонической, необходимо в каждое неравенство ввести балансовую переменную x_n+i.

Если знак неравенства ≤, то балансовая переменная вводится со знаком плюс, если знак неравенства ≥, то — минус.

В целевую функ­цию балансовые переменные не вводятся.

Алгоритм составления математической модели задачи ЛП:

~ ввести обозначения переменных;

~ исходя из цели экономических исследований, составить целевую функцию;

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

 

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

1. Находим область допустимых решений системы ограни­чений задачи.

2. Строим вектор.

3. Проводим линию уровня L ₀, которая перпендикулярна.

4. Линию уровня перемещаем по направлению вектора для задач на максимум и в направлении, противоположном, для задач на минимум.

Перемещение линии уровня производится до тех пор, пока у нее не окажется только одна общая точка с областью допусти­мых решений. Эта точка, определяющая единственное решение задачи ЛП, и будет точкой экстремума.

Если окажется, что линия уровня параллельна одной из сторон ОДР, то в таком случае экстремум достигается во всех точках соответствующей стороны, а задача ЛП будет иметь бесчисленное множество решений. Говорят, что такая задача ЛП имеет альтернативный оптимум, и ее решение находится по формуле:

где 0 ≤ t ≤ 1, ₁ и ₂ — оптимальные решения в угловых точках ОДР.

Задача ЛП может быть неразрешима, когда определяющие ее ограничения окажутся противоречивыми.

5. Находим координаты точки экстремума и значение це­левой функции в ней.

Пример 3. Выбор оптимального варианта выпуска изделий

Фирма выпускает 2 вида мороженого: сливочное и шоко­ладное. Для изготовления мороженого используются два ис­ходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы даны в таблице.

Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное мороженное, но не бо­лее чем на 100 кг.

Кроме того, установлено, что спрос на шо­коладное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого 16 р., шоколадного — 14 р.

Какое количество мороженого каждого вида должна про­изводить фирма, чтобы доход от реализации продукции был максимальным?

Решение. Обозначим: x ₁ - суточный объем выпуска сли­вочного мороженого, кг; x ₂ — суточный объем выпуска шоко­ладного мороженого, кг.

Составим математическую модель задачи.

Цены на мороженное известна: соответственно 16руб и 14руб., поэтому целевая функция будет иметь вид:

Установим ограничения по молоку для мороженного. Расход его на сливочное мороженное - 0,8кг, на шоколадное - 0,5кг. Запас молок 400кг. Поэтому первое неравенство будет иметь вид:

0,8х₁+ 0,5х₂ ≤400 – первое неравенство – ограничение. Аналогично составляются остальные неравенства.

В результате получится система неравенств. что область решения каждого неравенства. Это можно сделать, подставив в каждое из неравенств координаты точки О(0:0). В результате получим:

Фигура OABDEF — область допустимых решений. Строим вектор (16; 14). Линия уровня L ₀ задается уравнением 16x₁+14x₂=Const. Выбираем любое число, например число 0, тогда 16x₁+14x₂=0. На рисунке для линии L₀ выбрано некоторое положительное число, не равное нулю. Все линии уровня параллельны между собой. Вектор нормаль линии уровня.

Перемещаем линию уровня по направлению вектора. Точ­кой выхода L ₀ из области допустимых решений является точка D, ее координаты определяются как пересечение прямых, за­данных уравнениями:

Решая систему, получим координаты точки D (312,5; 300), в которой и будет оптимальное решение, т.е.

при этом

Таким образом, фирма должна выпускать в сутки 312,5 кг сли­вочного мороженого и 300 кг шоколадного мороженого, при этом доход от реализации составит 9 200 р.

Пример 4. Решить задачу примера 1(столы и стулья). Математическая модель ее имеет вид:

 

Целевая функция: 45 Х₁ + 80 Х₂ → max

Ограничения по материалу: 5 Х₁ + 20 Х₂ ≤ 400

Ограничения по труду: 10 Х₁ + 15 Х₂ ≤ 450,

Х₁ ≥ 0, Х₂ ≥ 0.

По горизонтальной оси откладывается значения Х₁, а по вертикальной оси - значения Х₂.

Строим фигуру, ограниченную неравенствами, получим множество возможных значений объемов выпуска стульев и столов (Х₁, Х₂ ), или, в других терминах, множество А, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис.3

Три его вершины очевидны - это (0,0), (45,0) и (0,20).

Четвертая - это пересечение двух прямых - границ треугольников на рис.1 и рис.2, т.е. решение системы уравнений: 5 Х₁ + 20 Х₂ = 400 и 10 Х₁ + 15 Х₂ = 450 есть четвертая вершина четырехугольника - это (24, 14).

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

Целевая функция 45 Х₁ + 80 Х₂ принимает минимальное значение, равное 0, в вершине (0,0). При увеличении аргументов эта функция увеличивается. В вершине (24,14) она принимает значение 2200. При этом прямая 45 Х₁ + 80 Х₂ = 2200 проходит между прямыми ограничений 5 Х₁ + 20 Х₂ = 400 и 10 Х₁ + 15 Х₂ = 450, пересекающимися в той же точке. Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный 2200, достигается в вершине (24,14).

Таким образом, оптимальный выпуск: 24 стула и 14 столов.

Пример 5. Продолжить решение задачи примера 2. (Кондитерская фабрика…)

4. Симплекс-метод решения задач линейного программирования

Основное содержание симплексного метода

Для решения задачи симплекс методом необходимо:

1. Указать способ нахождения оптимального опорного решения

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

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

Алгоритм симплексного метода решения задач линейного программирования

1. Привести задачу к каноническому виду

2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение, в виду несовместимости системы ограничений)

3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается

5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

Пример1

Решить симплексным методом задачу:

Решение:

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x₆ с коэффициентом +1. В целевую функцию переменная x₆ входит с коэффициентом ноль (т.е. не входит).

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х₁ = х₂ = х₃ = 0.

Получаем опорное решение

Х₁ = (0,0,0,24,30,6) с единичным базисом Б₁ = (А4, А5, А6).

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле: Δ_k = C_бX_k — c_k ,

Где: C_б = (с₁, с₂,..., с_m) — вектор коэффициентов целевой функции при базисных переменных

X_k = (x_1k, x_2k,..., x_mk) — вектор разложения соответствующего вектора Ак по базису опорного решения

С_к — коэффициент целевой функции при переменной х_к.

Оценки векторов входящих в базис всегда равны нулю. Опорное решение, коэффициенты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу 26.1

Сверху над таблицей для удобства вычислений оценок записываются коэффициенты целевой функции. В первом столбце "Б" записываются векторы, входящие в базис опорного решения. Порядок записи этих векторов соответствует номерам разрешенных неизвестных в уравнениях ограничениях. Во втором столбце таблицы "С_б" записываются коэффициенты целевой функции при базисных переменных в том же порядке. При правильном расположении коэффициентов целевой функции в столбце "С_б" оценки единичных векторов, входящих в базис, всегда равных нулю.

В последней строке таблицы с оценками Δ_k в столбце "А₀" записываются значения целевой функции на опорном решении Z(X₁).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ₁ = -2, Δ₃= -9 для векторов А₁ и А₃ отрицательные.

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

Определим, введение, какого из двух векторов приведет к большему приращению целевой функции.

Приращение целевой функции находится по формуле:.

Вычисляем значения параметра θ₀₁ для первого и третьего столбцов по формуле:

Получаем θ₀₁ = 6 при l = 1, θ₀₃ = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции при введении в базис первого вектора ΔZ₁ = — 6·(- 2) = 12, и третьего вектора ΔZ₃ = — 3·(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х₁₃ = 2, получаем второе опорное решение Х₂ = (0,0,3,21,42,0) с базисом Б₂ = (А₃, А₄, А5). (таблица 26.2)

Это решение не является оптимальным, так как вектор А₂ имеет отрицательную оценку Δ₂ = — 6. Для улучшение решения необходимо ввести вектор А₂ в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ₀₂ для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А₄. Производим преобразование Жордана с элементом х₂₂ = 3, получаем третье опорное решение Х₃ = (0,7,10,0,63,0) Б₂ = (А3, А2, А5) (таблица 26.3).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ1 = 7/2, Δ4 = 2, Δ6 = 7/2.

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

Предприятия

 

Предприятие располагает тремя производственными ре­сурсами (сырьем, оборудованием, электроэнергией) и может организовать производство продукции двумя различными спо­собами. Расход ресурсов за один месяц и общий ресурс при каждом способе производства даны в табл. 21.2 (в усл. ед.).

При первом способе производства предприятие выпускает за один месяц 3 тыс. изделий, при втором — 4 тыс. изделий.

Сколько месяцев должно работать предприятие каждым из этих способов, чтобы при наличных ресурсах обеспечить мак­симальный выпуск продукции?

Решение. Составим математическую модель задачи. Обо­значим: x ₁ — время работы предприятия первым способом, x ₂ — время работы предприятия вторым способом.

Математическая модель имеет вид

 

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

 

Приведем задачу к каноническому виду:

 

 

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

 

Составляем симплексную таблицу 1-го шага (табл. 21.3).

Получим решение:

 

В индексной строке Δ _j имеются две отрицательные оцен­ки, значит, найденное решение не является оптимальным и его можно улучшить. В качестве ключевого столбца следу­ет принять столбец базисной переменной х ₂, а за ключевую строку взять строку переменной x ₃, где min (4/2,3/l, 8/1) = min (2, 3, 8) = 2.

Ключевым элементом является (2). Вводим в столбец ба­зисной переменной х ₂, выводим х ₃. Составляем симплексную таблицу 2-го шага (табл. 21.4).

Получим

В индексной строке имеется одна отрицательная оценка. Полученное решение можно улучшить. Ключевым элементом является (1/2). Составляем симплексную таблицу 3-го шага (табл. 21.5).

Все оценки свободных переменных Δ _j ≥ 0, следовательно, найденное опорное решение является оптимальным:

Таким образом, по первому способу предприятие должно работать два месяца, по второму — один месяц, при этом мак­симальный выпуск продукции составит 10 тыс. ед.

Альтернативный оптимум

При решении задач линейного программирования сим­плексным методом критерием оптимальности является условие Δ _j ≥ 0 для задач на максимум и условие Δ _j < 0 для задач на минимум. Если на каком-то шаге окажется, что хотя бы одна оценка свободной переменной Δ _j = 0, а все остальные Δ _j > 0 для задач на максимум (Δ _j < 0 для задач на минимум), то, приняв в качестве ключевого столбца столбец, где Δ _j = 0, и найдя новое оптимальное решение, заметим, что значение це­левой функции при этом не изменится. Говорят, что в этом случае задача имеет альтернативный оптимум.

Критерием альтернативного оптимума при решении за­дач симплексным методом является равенство нулю хотя бы одной оценки свободной переменной (Δ _j = 0).

Если только одна оценка свободной переменной равна ну­лю, то решение находится по формуле

где 0 ≤ t ≤ 1.

Если две оценки и более, например S, свободных перемен­ных равны нулю, то оптимальное решение определяется по формуле

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

Пример. Дана задача линейного программирования

 

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

 

Решение. Составим симплексную таблицу (табл. 21.6).

В индексной строке имеется одна положительная оцен­ка. Полученное решение можно улучшить. Ключевым элемен­том является (4). Составляем симплексную таблицу 2-го шага (табл. 21.7).

Получаем

 

 

Так как Δ₂ = 0, то задача имеет альтернативный оптимум. Найдем еще одно оптимальное решение, введя вместо базисной переменной х ₁ свободную переменную х ₂ (табл. 21.8).

Получаем

 

Найдем координаты оптимального решения задачи:

 

Давая t значения из [0,1], получим различные _опт, при кото­рых L() = -12.

Практические занятия.

УПРАЖНЕНИЯ

Решить следующие задачи симплексным методом.

 

1. L() = x ₁ — 3 x ₂ — 5 x ₃ — х ₄ → max

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

2. L() = x ₁ + 2 x ₂ + 3 x ₃ → min

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

 

 

3. L() = —2 x ₁ — x ₂ + x ₃ + x ₄ → max

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

 

 

4. L() = 3 x ₁ + x ₂ + 2 x ₃ → min

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

 

5. L() = x ₁ + х ₂ + x ₃ → max

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

 

6. L() = x ₁ + 2 х ₂ + 2 х ₃ → min

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

 

7. L() = 3 x ₁ + x ₂ + x ₃ + x ₄ → max

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

 

 

8. L() = x ₁ - 5 x ₂ – x ₃ → max

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

 

 

9. L() = x ₁ + х ₂ + x ₃ + x ₄ → min

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

 

10. L() = 3 x ₁ + 5 x ₂ + 4 x ₃ → max

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

 

 

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

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

12. Торговая фирма для продажи товаров трех видов ис­пользует ресурсы: время и площадь торговых залов. Затраты ресурсов на продажу одной партии товаров каждого вида да­ны в табл. 21.10. Прибыль, получаемая от реализации одной партии товаров 1-го вида, — 5 усл. ед., 2-го вида — 8 усл. ед., 3-го вида — 6 усл. ед.

Определить оптимальную структуру товарооборота, обес­печивающую фирме максимальную прибыль.

13. Фирма выпускает четыре пользующихся спросом изде­лия, причем месячная программа выпуска составляет 10 изде­лий типа 1 и 3, 200 изделий типа 2 и 120 изделий типа 4. Нормы затрат сырья на единицу различных типов изделий приведены в табл. 21.11.

Прибыль от реализации изделий типа 1 равна 6 усл. ед., изделий типа 2 — 2 усл. ед., изделий типа 3 — 2,5 усл. ед. и изделий типа 4 — 4 усл. ед.

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

14. Металлургический завод из металлов A ₁, A ₂, А ₃ может выпускать сплавы B ₁, В ₂, В ₃. В течение планируемого пери­ода завод должен освоить не менее 640 т металла A ₁ и 800 т металла А ₂, при этом металла А ₃ может быть израсходовано не более 860 т.

Определить минимальные затраты, если данные о нормах расхода и себестоимость даны в табл. 21.12.

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

По этим исходным данным решить следующие задачи:

1) определить оптимальный ассортимент, максимизирую­щий товарную продукцию предприятия;

2) приняв условие, что количество тканей трех артикулов находится в отношении 2:1:3, определить, какое мак­симальное количество комплектов ткани может выпус­тить предприятие;

3) определить оптимальный ассортимент, максимизирую­щий доход предприятия, если цена 1 м ткани составляет 8, 5 и 15 усл. ед. соответственно;

4) решить задачу (1) при условии, что станки 1-го типа ткань первого артикула не производят.

***

Приложения

Решение систем m линейных неравенств с двумя переменными

Дана система т линейных неравенств с двумя переменными

Знаки некоторых или всех неравенств могут быть ≥.

Рассмотрим первое неравенство в системе координат Х ₁ ОХ ₂. Построим прямую

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

Эта прямая делит плоскость на две полуплоскости 1 и 2.

Полуплоскость 1 содержит начало координат, полуплос­кость 2 не содержит начала координат.

Для определения, по какую сторону от граничной прямой расположена заданная полуплоскость, надо взять произволь­ную точку на плоскости (лучше начало координат) и подста­вить координаты этой точки в неравенство. Если неравенство справедливо, то полуплоскость обращена в сторону этой точки, если не справедливо, то в противоположную от точки сторону.

Направление полуплоскости на рисунках показываем стрел­кой.

Определение. Решением каждого неравенства систе­мы является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее.

Определение. Пересечение полуплоскостей, каждая из ко­торых определяется соответствующим неравенством системы, называется областью решения системы (ОР).

Определение. Область решения системы, удовлетворяю­щая условиям неотрицательности (x_j ≥ 0, j =), называ­ется областью неотрицательных, или допустимых, решений (ОДР).

Если система неравенств совместна, то ОР и ОДР могут быть многогранником, неограниченной многогранной облас­тью или одной точкой.

Если система неравенств несовместна, то ОР и ОДР — пус­тое множество.

Пример 1. Найти ОР и ОДР системы неравенств и опреде­лить координаты угловых точек ОДР

 

Решение.. Найдем ОР первого неравенства: х ₁ + 3 x ₂ ≥ 3. Построим граничную прямую х ₁ +3 x ₂ – 3 = 0.Под­ставим координаты точки (0,0) в неравенство: 1∙0 + 3∙0 > 3; так как координаты точки (0,0) не удовлетворяют ему, то решени­ем неравенства (19.1) является полуплоскость, не содержащая точку (0,0).

Аналогично найдем решения остальных неравенств систе­мы. Получим, что ОР и ОДР системы неравенств является выпуклый многогранник ABCD.

Найдем угловые точки многогранника. Точку А определим как точку пересечения прямых Решая систему, получим А (3/7, 6/7).

Точку В найдем как точку пересечения прямых

Из системы получим B (5/3, 10/3). Аналогично найдем коорди­наты точек С и D: С (11/4; 9/14), D (3/10; 21/10).

Пример 2. Найти ОР и ОДР системы неравенств

 

Р

 

 

Решение.. Построим прямые и определим решения не­равенств. ОР и ОДР являются неограниченные многогранные области ACFM и ABDEKM соответственно.

Пример 3. Найти ОР и ОДР системы неравенств

 

 

Решение. Найдем решения неравенств (19.8)-(19.10). ОР представляет неограниченную многогранную область ABC; ОДР — точка В.

Пример 4. Найти OP и ОДР системы неравенств

 

 

Решение. Построив прямые, найдем решения неравенств системы. ОР и ОДР несовместны.

УПРАЖНЕНИЯ

Найти ОР и ОДР систем неравенств

 

 

 

Найти ОР и ОДР систем неравенств

 

 

Найти ОР и ОДР систем неравенств

Раздел 2. Детерминированные задачи