Часть 5. элементы линейного программирования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Виды математических моделей

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

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

Если хотя бы одно ограничение является неравенством, то модель задачи ЛП является неканонической. Чтобы перейти от неканонической модели к канонической, необходимо в каждое неравенство ввести балансовую переменную x_n+i. Если знак неравенства ≤, то балансовая переменная вводится со знаком плюс, если знак неравенства ≥, то — минус. В целевую функ­цию балансовые переменные не вводятся.

Чтобы составить математическую модель задачи ЛП, не­обходимо:

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

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

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

Для рассмотрения решения задач линейного программиро­вания дадим некоторые понятия аналитической геометрии в n-мерном пространстве.

Глава 19. ЭЛЕМЕНТЫ АНАЛИТИЧЕСКОЙ ГЕОМЕТРИИ В n-МЕРНОМ ПРОСТРАНСТВЕ

19.1. Основные понятия и определения

Дано n-мерное пространство, точки которого имеют коор­динаты (x₁, x₂, . . . ,x_п).

Определение 1. Множество точек n-мерного пространства, координаты которых удовлетворяют уравнению

где хотя бы одно из чисел а₁, a₂, ..., a_n отлично от нуля, на­зывается гиперплоскостью п-мерного пространства.

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

где = (a₁, a₂,..., a_n), = (x₁, x₂,..., x_n).

Даны две гиперплоскости

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

Дано неравенство

Эта зависимость определяет полуплоскость двухмерного про­странства, лежащую по одну сторону от прямой

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

Определение 3. Множество точек n-мерного пространства, координаты которых удовлетворяют неравенству

называется полупространством n-мерного пространства, рас­положенным по одну сторону от гиперплоскости

Определение 4. Множество точек n-мерного пространства, содержащее вместе с любыми двумя точками A и В и все точ­ки отрезка АВ, называется выпуклым телом (областью, фи­гурой).

Примеры плоских выпуклых фигур приведены на рис. 19.1.

Примеры невыпуклых фигур приведены на рис. 19.2.

Дадим некоторые определения выпуклой области.

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

Определение 6. Точка В называется граничной точкой вы­пуклой области, если в сколь угодно малой окрестности этой точки содержатся как точки данной области, так и не принад­лежащие ей (рис. 19.3).

Определение 7. Точка С называется угловой точкой вы­пуклой области, если она является граничной и не лежит внутри отрезка, соединяющего две другие точки этой облас­ти (рис. 19.3).

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

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

Определение 9. Ограниченной называется область, если су­ществует такое число М > 0, что радиус-вектор , соединяю­щий начало координат с любой точкой области, по абсолютной величине меньше М, т.е. || ≤ М.

Для этой области все ее точки находятся на конечном рас­стоянии от начала координат.

Определение 10. Если найдутся точки области, сколь угод­но удаленные от начала координат, то область называется не­ограниченной.

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

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

Определение 13. Линейная комбинация S векторов

в которой коэффициенты t_i удовлетворяют условиям

называется выпуклой линейной комбинацией.

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

ТЕОРЕМА 1. Пересечение выпуклых областей есть выпуклая область.

ТЕОРЕМА 2. Множество точек выпуклого п-мерного много­гранника совпадает с множеством любых выпуклых линейных комбинаций его угловых точек.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение. Найдем ОР первого неравенства: х₁ + 3x₂ ≥ 3. Построим граничную прямую х₁ +3x₂ – 3 = 0 (рис. 19.5). Под­ставим координаты точки (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. Найти ОР и ОДР системы неравенств

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

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

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

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

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

УПРАЖНЕНИЯ

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

Глава 20. ГРАФИЧЕСКИЙ МЕТОД

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

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

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

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

где е₁ и е₂ — единичные векторы по осям OX₁ и ОX₂ соответ­ственно; таким образом, = (∂L/∂х₁, ∂L/∂х₂). Координатами вектора являются коэффициенты целевой функции L().

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Целевая функция будет иметь вид

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

OABDEF — область допустимых решений (рис. 20.1). Строим вектор (1, 1). Линия уровня L₀ задается уравнением

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

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

при этом

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