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

Лекция 2

В канонической форме

допустимым решением ЗЛП (допустимым планом ).

оптимальным решением ЗЛП.

Необходимость

Пример .

Запишем задачу в канонической форме

Особые ситуации графического решения ЗЛП

Кроме случая, когда задача имеет единственное оптимальное решение для и , могут быть особые ситуации :

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

2. задача не разрешима из-за неограниченности ОДР, или – рисунок 3;

3. ОДР - единственная точка А, тогда ;

4. задача не разрешима , если ОДР есть пустая область.

А

Рисунок 2 Рисунок 3

Если линия уровня параллельна стороне области допустимых решений, то экстремум достигается во всех точках стороны . Задача имеет бесчисленное множество оптимальных решений – альтернативный оптимум . Оптимальное решение находится по формуле

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

Пример . Решить графически задачу линейного программирования (альтернативный оптимум ):

Вопросы для самоконтроля

1. Запишите задачу линейного программирования в общей форме.

2. Запишите задачу линейного программирования в канонической и стандартной формах.

3. С помощью каких преобразований можно перейти от общей или стандартной формы задачи линейного программирования к канонической?

4. Дайте определение допустимого и оптимального решений задачи линейного программирования.

5. Какое из решений и является «лучшим» для задачи минимизации функции , если ?

6. Какое из решений и является «лучшим» для задачи максимизации функции , если ?

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

8. Как построить полуплоскость, заданную линейным неравенством с двумя переменными ?

9. Что называется решением системы линейных неравенств с двумя переменными? Постройте на плоскости область допустимых решений такой системы линейных неравенств, которая:

1) имеет единственное решение;

2) имеет бесконечное множество решений;

3) не имеет ни одного решения.

10. Запишите для линейной функции вектор градиент, назовите вид линий уровня. Как расположены относительно друг друга градиент и линии уровня?

11. Сформулируйте алгоритм графического метода решения стандартной ЗЛП с двумя переменными.

12. Как найти координаты решения и значения , ?

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

1) достигается в единственной точке, а - на отрезке ОДР;

2) достигается в единственной точке ОДР, а .

14. Дайте геометрическую иллюстрацию ЗЛП, если она:

1) имеет единственные оптимальные решения для и ;

2) имеет множество оптимальных решений для .

Лекция 2

графический метод нахождения оптимального решения

1. Формы линейных математических моделей и их преобразование

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

3. Особые ситуации графического решения ЗЛП

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

Формы линейных математических моделей и их преобразование

Математическая модель задачи линейного программирования (ЗЛП) может быть записана в одной из трех форм.

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

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

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

Решение системы ограничений, удовлетворяющее условиям неотрицательности переменных, называют допустимым решением ЗЛП (допустимым планом ).

Множество допустимых решений называют областью допустимых решений ЗЛП.

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

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

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

Переход к канонической форме записи ЗЛП .

Пример .

Запишем задачу в канонической форме , вводя в левую часть первого неравенства системы ограничений дополнительную (балансовую) переменную со знаком «+», а в левую часть второго неравенства дополнительную переменную со знаком «минус».

Экономический смысл различных дополнительных переменных может быть не одинаков: он зависит от экономического смысла ограничений, в которые эти переменные входят.

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

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

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

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

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

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

где x j - неизвестные; a ij , b i , c j - заданные постоянные вели­чины.

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

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

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

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

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

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

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

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

7.Решение задач линейного программирования графическим методом . Графики функций-ограничений. Линии уровня.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9.Симплекс-метод . Характеристика и алгоритм метода, применимость его.

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

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

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

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

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

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

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

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

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

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

10.Транспортная задача. Определение, виды, методы нахождения начального решения транспортной задачи.

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

1. Нахождение исходного опорного решения;

2. Проверка этого решения на оптимальность;

3. Переход от одного опорного решения к другому.

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

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

Линейное программирование включает в себя целый ряд эвристических (приближенных) методов решения, позволяющих при заданных условиях из всех возможных вариантов решений производственных задач выбрать наилучший, оптимальный. К этим методам относятся следующие – графический, симплексный, метод потенциалов (модифицированный распределительный метод – МОДИ), Хичкова, Креко, метод аппроксимации Фогеля и другие.

Часть этих методов объединяют общим названием - распределительный, или транспортный, метод.

Родиной линейного программирования является Россия. Первые работы по линейному программированию будущим академиком Л.В. Канторовичем были опубликованы в 1939 г. В 1975 г. за разработку методов линейного программирования им была получена Нобелевская премия по экономике. Поскольку большинство работ академика Л.В. Канторовича посвящено решению транспортных задач, можно считать, что указанная Нобелевская премия отмечает и заслуги российской транспортной науки.

На автомобильном транспорте методы линейного программирования используются с 1960-х годов для решения большого числа важнейших производственных задач, а именно: сокращение дальности перевозок грузов; составление оптимальной схемы перевозок; выбор кратчайших маршрутов движения; задачи перевозки разных, но взаимозаменяемых грузов; сменно-суточное планирование; планирование перевозок мелкопартионных грузов; распределение автобусов по маршрутам и другие.

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

Целевая функция и ограничения выражены линейными зависимостями (равенствами или неравенствами);

Число зависимостей всегда меньше числа неизвестных (условие неопределенности);

Неотрицательность искомых переменных. Общая форма записи модели линейного программирования в сокращенном виде выглядит следующим образом:

Найти х ij ≥ 0 (j = 1, 2…n) при ограничениях следующего типа:

Эти ограничения минимизируют (или максимизируют) целевую функцию

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

а 11 х 1 + а 12 х 2 + …+ а 1 n х n = b 1 ;

а 21 х 1 + а 22 х 2 + … + а 2 n х n = b 2 ; (3.1)

……………………………..

a m х 1 + а m 2 х 2 + …+ а mn х n = b m ..

Если модель записана в форме неравенств в неотрицательных числах, т. е. имеет вид

а 11 х 1 + а 12 х 2 + …+ а 1 n х n ≤ b 1 ;

а 21 х 1 + а 22 х 2 + … + а 2 n х n ≤ b 2 ; (3.2)

……………………………..

a m х 1 + а m 2 х 2 + …+ а mn х n ≤ b m ,..

то эта запись приводится к канонической форме (3.1) путем введения дополнительных переменных х n +1 > 0 (i =1,2…m ) в левую часть неравенства (или сокращения числа переменных, если знак неравенства направлен в другую сторону). Дополнительные переменные составляют базис.

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

L = с 1 х 1 + с 2 х 2 …с n х n → min, (3.3)

где с 1 , с 2 … с n – коэффициенты целевой функции L при переменных х j .

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

В случае максимизации целевой функции L следует знаки при переменных целевой функции изменить на противоположные, и мы вновь придем к задаче минимизации, т.е. одна задача сводится к другой заменой L на –L или max L = min (–L ).

Базисным решением системы линейных уравнений (3.1) называется решение, в котором небазисным переменным даны нулевые значения.

Допустимым называется такое базисное решение, в котором вошедшие в базис переменные являются неотрицательными.

Оптимальным называется допустимое решение, максимизирующее (или минимизирующее) целевую функцию (3.3).

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

Правила составления математической модели двойственной задачи базируются на правилах матричного исчисления.

Понятие двойственности широко используется в анализе задач линейного программирования. Свойство двойственности детально рассматривается в каждом конкретном случае.

3.2. Графоаналитический метод

Графоаналитический метод – это один из простейших методов линейного программирования. Он наглядно раскрывает сущность линейного программирования, его геометрическую интерпретацию. Его недостаток в том, что он позволяет решать задачи с 2 или 3 неизвестными, т. е. применим для узкого круга задач. Метод основан на правилах аналитической геометрии.

Решение задачи с двумя переменными х 1 и х 2 , которые по смыслу задачи не должны быть отрицательными, выполняется в системе декартовых координат. Уравнения х 1 =0 и х 2 = 0 являются осями системы координат первого квадранта

Метод решения рассмотрим на конкретном примере.

Пример 3.1. На складе имеются 300 т изделий из пенобетона и 200 т из стали. Автопредприятию необходимо доставить эти изделия на строящийся объект. На автопредприятии имеются грузовые автомобили КамАЗ - 5320 и

ЗИЛ-4314. За одну поездку КамАЗ-5320 может доставить 6 т пенобетона и 2 т стали, а прибыль от ездки составит 4 тыс. руб. ЗИЛ-4314 за одну поездку доставляет 2 т пенобетона и 4 т стали, прибыль от ездки составляет 6 тыс. руб. Необходимо организовать перевозку так, чтобы обеспечить автопредприятию наибольшую прибыль.

Построим математическую модель задачи. Обозначим через х 1 искомое количество ездок КамАЗ-5320 и через х 2 искомое количество ездок ЗИЛ-4314.

Общая перевозка в т изделий из пенобетона составляет 6х 1 + 2х 2 , а из стали 2х 1 + 4х 2 . Ограничения по перевозке, исходя из имеющегося количества изделий, составляют 6х 1 + 2х 2 ≤ 300т по пенобетону и 2х 1 + 4 х 2 ≤ 200т по стали.

Суммарная прибыль в тыс. руб. выражается величиной 4х 1 + 6х 2 , которую нужно максимизировать и которая является критерием оптимальности в рассматриваемой задаче. Математическая модель задачи, таким образом, выглядит следующей. Необходимо максимизировать целевую функцию

L = 4х 1 + 6х 2 → mах при условиях: 6х 1 + 2х 2 ≤ 300; 2х 1 + 4х 2 ≤ 200; х 1 ≥ 0; х 2 ≥ 0.

Рассмотрим уравнение 6х 1 + 2х 2 = 300. Чтобы построить прямую, описываемую этим уравнением, найдем две точки, лежащие на этой прямой. При х 1 = 0 из уравнения прямой найдем 2х 2 = 300, откуда х 2 = 150. Следовательно, точка А с координатами (0,150) лежит на искомой прямой. При х 2 = 0 имеем 6х 1 = 300, откуда х 1 = 50, а точка D с координатами (50,0) также находится на искомой прямой. Через эти две точки проводим прямую AD (рис. 3.1).

Линейное неравенство 6х 1 + 2х 2 ≤ 300 представляет собой полуплоскость, расположенную с одной из сторон от построенной прямой 6х 1 + 2х 2 = 300. Чтобы выяснить, с какой стороны от этой прямой расположены точки искомой полуплоскости, подставим в неравенство 6х 1 + 2х 2 ≤ 300 координаты какой-либо точки, не лежащей на граничной прямой. Например, начало координат 0-(0,0). Для него справедливо неравенство 6∙0 + 2∙0 = 0 < 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой AD и на рис. 3.1 заштрихована.

Уравнение 2х 1 + 4х 2 = 200 построим по двум точкам. При х 1 = 0 4х 2 = 200, откуда х 2 = 50. Тогда точка Е имеет координаты (0,50) и принадлежит искомой прямой. При х 2 = 0, 2х 2 = 200, точка с находится на данной прямой с координатами (100,0). Подставив в неравенство координаты точки с (0,0), получим 2∙0 + 4∙0 = 0 < 200. Значит, начало координат находится в области допустимых значений от прямой 2х 1 + 4х 2 = 200.

Система ограничений задачи требует, чтобы планы (х 1 ; х 2 ) удовлетворяли всем четырем неравенствам, т. е. допустимые планы – точки (х 1 ; х 2 ) должны одновременно находиться во всех четырех полуплоскостях. Этому требованию отвечают только точки, расположенные внутри и на границе многоугольника OEKD , который и является многоугольником допустимых решений.

Вершинами многоугольника допустимых решений являются точки O, E, K, D, отрезки прямых OE, EK, KD, OD – его ребра. Любая точка многоугольника OEKD является планом задачи, удовлетворяя все ее условия. Вершины многоугольника образованы пересечением двух прямых и соответствуют опорным планам задачи, среди которых находится и наилучший (оптимальный) план. Таким образом, опорных планов будет столько, сколько вершин у многоугольника допустимых решений.

Наглядное геометрическое представление можно получить и для целевой функции L = 4х 1 + 6х 2 . Зафиксируем какое-либо значение целевой функции, например L = 120. уравнение 4х 1 + 6х 2 = 120 определяет прямую, проходящую через точку В с координатами (х 1 = 0; х 2 = 20) и точку L с координатами ((х 1 = 30; х 2 = 0). Отрезок ВL лежит внутри многоугольника OEKD . Следовательно, для всех планов (точек) этого отрезка значение целевой функции одинаково и равно 120. Придавая другие значения целевой функции, получим параллельные прямые, которые называют линиями уровня целевой функции.

Перемещая прямую L параллельно самой себе в одном направлении, получим возрастание целевой функции, а в противоположном направлении – ее убывание. В рассматриваемом примере передвижение прямой ВL вправо определяет возрастание целевой функции, которую мы максимизируем. Так поступаем до тех пор, пока прямая ВL будет иметь хотя бы одну общую точку с многоугольником допустимых решений OEKD . Из рис. 3.1 следует, что последней точкой, которую пересечет прямая уровня целевой функции, будет точка К . Это значит, что точка К определяет оптимальный план задачи.

Направление возрастания, перпендикулярное к линии уровня, называется направлением наибольшего возрастания целевой функции и определяет ее максимальный прирост. Это направление можно установить без построения линий уровня. Для этого необходимо на осях х 1 и х 2 отложить отрезки, равные коэффициентам целевой функции, и по ним, как по координатам, построить вектор наибольшего возрастания целевой функции. В математике его называют градиентом и обозначают знаком grad. Градиентом для функции L = 4х 1 + 6х 2 будет вектор n | 4; 6 | . Для удобства его построения увеличим координаты, например, в 10 раз, т.е. n | 40; 60 | . Построим градиент целевой функции L , для чего соединим точку с координатами (40; 60) с началом координат. Линии уровня целевой функции строят перпендикулярно к направлению градиента.

Итак, тем или другим способом установлено, что точка К определяет оптимальный план задачи, значения переменных которого соответствуют координатам данной точки. Для установления координат необходимо решить систему уравнений прямых, образующих эту вершину:

6х 1 + 2х 2 = 300;

2х 1 + 4х 2 = 200.

Уравняем коэффициенты при х 1 , умножив второе уравнение на 3, и вычтем из второго уравнения первое. Получим 10х 2 = 300, х 2 = 30. Подставив значение х 2 = 30 в любое из уравнений, например в первое, определим значение х 1:

6х 1 + 2х · 30 = 300,

откуда 6х 1 = 300 – 60 = 240, следовательно, х 1 = 40.

Таким образом, чтобы получить наибольшую прибыль автопредприятию, необходимо выполнить 40 ездок на КамАЗ-5320 и 30 ездок на ЗИЛ-4314. Максимальная прибыль при этом составит

L = 4х 1 + 6х 2 = 4 · 40 + 6 · 30 = 340 тыс. руб.

На основе рассмотренного примера и геометрической интерпретации задачи оптимизации с двумя переменными можно сделать следующие выводы:

1) в двухмерном пространстве область допустимых решений представляет собой многоугольник;

2) каждой стороне многоугольника соответствует значение одной переменной, равной нулю;

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

4) каждому значению целевой функции соответствует прямая;

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

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

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

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

На рис. 3.2,б изображены невыпуклые множества. В невыпуклых множествах можно указать хотя бы две точки отрезка АВ, не принадлежащие рассматриваемому множеству.

3.3. Симплексный метод

Симплексный метод – это распространенный метод решения задач линейного программирования. Свое название метод получил от слова «симплекс», обозначающего простейший выпуклый многоугольник, число вершин которого всегда на единицу больше, чем размерность пространства. Симплексный метод разработан в США математиком Дж. Данцигом в конце 1940-х годов.

Симплексный метод включает получение неотрицательного базисного решения системы канонических линейных уравнений типа (3.1), последующую минимизацию (максимизацию) целевой функции (3.3) и нахождение таким способом оптимальных значений искомых переменных х 1 , х 2… х n .

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

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

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

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

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

Пусть необходимо минимизировать линейную форму

L = с 1 х 1 + с 2 х 2 + … с n х n .

При условиях (для наглядности нулевые и единичные коэффициенты в уравнениях сохранены):

1х 1 + 0х 2 + … 0х m + a 1m+ 1x m+1 …+a 1n x n = b 1 ;

0х 1 + 1х 2 + … 0х m + a 2m+ 1x m+1 …+a 2n x n = b 2 ;

……………………………………………

0х 1 + 0х 2 + … 1х m + a mm + 1x m +1 …+a mn x n = b m .

В данной системе уравнений уже имеется готовый базис, поскольку каждое уравнение ограничений содержит неизвестную с коэффициентом, равным единице, которой нет в других уравнениях, т. е. из коэффициентов при переменных х 1 , х 2 …, х m можно составить единичную матрицу.

Решим уравнения относительно базисных переменных:

х 1 = b 1 – (a 1m+1 ·х m+1 …+ a 1n x n);

х 2 = b 2 – (a 2m+1 ·х m+1 …+ a 2n x n);

………………………………

х m = b m – (a mm+ 1x m+1 …+ a mn x n),

а целевую функцию выразим через свободные переменные, подставив в нее на место базисных переменных их выражения через свободные переменные:

L=c 1 b 1 +c 2 b 2 +c m b m –(c 1 a 1m +c 2 a 2m+1 +…+c m a mn+1)x m+1 -…-(c 1 a 1n +c 2 a 2n +…+c m a mn)x n …+c n x n..

Переменные х 1 , х 2 …, х m , с помощью которых найден первый базисный план, являются базисными, а остальные x m +1 , x m +2 ,…x n – свободными. Базисных переменных должно быть всегда столько, сколько уравнений в системе. Исходя из условия неотрицательности, наименьшее значение свободных переменных равно нулю. Полученное базисное решение системы уравнений и является ее первоначальным допустимым решением, т.е. x 1 = b 1 , x 2 =b 2 , … x m =b m , x m +1 = 0,…, x n = 0.

Этому решению соответствует значение целевой функции

L = с 1 b 1 + с 2 b 2 + … с m b m .

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

Симплексные таблицы составляют следующим образом (см. табл. 3.1). Вверху таблицы помещают все переменные х 1 , х 2 …, х n и коэффициенты c j , с которыми соответствующие переменные входят в целевую функцию. Первый столбец c i состоит из коэффициента целевой функции при переменных, вошедших в базис. Затем следует столбец базисных переменных и свободных членов уравнений. Элементы остальных столбцов таблицы представляют собой коэффициенты при переменных, с которыми последние входят в систему уравнений. Таким образом, каждой строке таблицы соответствует уравнение системы, решенное относительно базисной переменной. В таблице показан и вариант плана, который соответствует целевой функции при данном базисе.

Нижняя строка таблицы называется индексной . Каждый ее элемент (оценка) ∆ j определяют

∆ j = z j – c j ,

где c j – коэффициенты при соответствующих переменных в целевой функции; z j – сумма произведений коэффициентов целевой функции при базисных переменных на соответствующие переменные – элементы j –го столбца таблицы.

Таблица 3.1

Симплексная таблица с первоначальным допустимым

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

Покажем, как можно перейти от задачи с ограничениями-неравенствами к основной задаче линейного программирования.

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

Требуется найти такую совокупность неотрицательных значений которая удовлетворяла бы неравенствам (4.1), и, кроме того, обращала бы в минимум линейную функцию:

От поставленной таким образом задачи легко перейти к основной задаче линейного программирования. Действительно, введем обозначения:

где - некоторые новые переменные, которые мы будем называть «добавочными». Согласно условиям (4.1), эти добавочные переменные так же, как и должны быть неотрицательными.

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

Как видно, перед нами в чистом виде основная задача линейного программирования (ОЗЛП). Уравнения (4.3) заданы в форме, уже разрешенной относительно базисных переменных которые выражены через свободные переменные Общее количество переменных равно , из них «первоначальных» и «добавочных». Функция L выражена только через «первоначальные» переменные (коэффициенты при «добавочных» переменных в ней равны нулю).

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

Пример 1 Имеется задача линейного программирования с ограничениями-неравенствами: иайти неотрицательные значения переменных удовлетворяющие условиям

и обращающие в минимум линейную функцию

Требуется привести эту задачу к виду ОЗЛП.

Решение. Приводим неравенства (4.4) к стандартной форме;

Вводим дополнительные переменные:

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

удовлетворяющие уравнениям (4.6) и обращающие в минимум линейную функцию (4.5).

Мы показали, как от задачи линейного программирования с ограничениями-неравенствами можно перейти к задаче с ограничениями-равенствами (ОЗЛП). Всегда возможен и обратный переход - от ОЗЛП к задаче с ограничениями-неравенствами. Если в первом случае мы увеличивали число переменных, то во втором случае будем его уменьшать, устраняя базисные переменные и оставляя только свободные.

Пример 2. Имеется задача линейного программирования с ограничениями-равенствами (ОЗЛП):

и минимизируемой функцией

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

Решение. Так как , то выберем какие-то две из переменных в качестве свободных. Заметим, что переменные в качестве свободных выбирать нельзя, так как они связаны первым из уравнений (4 7): значение одной из них полностью определяется значением другой, а свободные переменные должны быть независимыми

По такой же причине нельзя в качестве свободных выбрать переменные (их связывает второе уравнение ). Выберем в качестве свободных переменные и выразим через них все остальные:

Так как условия (4 9) могут быть заменены неравенствами:

Перейдем в выражении линейной функции L к свободным переменным Подставляя в L вместо и их выражения (4.9). получим.

Основные понятия моделирования

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

Моделирование – это универсальный способ изучения процессов и явлений реального мира. Особое значение моделирование приобретает при изучении объектов, недоступных прямому наблюдению и исследованию. К ним, в частности, относятся социально-экономические явления и процессы.

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

Экономика – это система общественного производства, осуществляющая собственно производство, распределение, обмен и потребление необходимых обществу материальных благ.

Соответственно, экономико-математическая модель – это выраженная в формально-математических терминах экономическая абстракция, логическая структура которой определяется как объективными свойствами предмета описания, так и субъективным целевым фактором исследования, для которого это описание предпринимается.

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

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

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

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

Если целевая функция является линейной, а множество Х задается с помощью системы линейных уравнений и неравенств, то задача называется задачей линейного программирования (ЗЛП). Таким образом, общая постановка задачи линейного программирования такова:

найти экстремум функции

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

при условиях неотрицательности

Введем обозначения:

Запасы i –го вида ресурса;

затраты i –го вида ресурса на производство j –го вида продукции;

прибыль от реализации единицы j –го вида продукции.

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

Компактная запись показывает, что модель общей задачи линейного программирования включает пять основных элементов:

Переменные величины, значение которых отыскивается в процессе решения задачи;

Технико-экономические коэффициенты при переменных в ограничениях;

Объем правой части неравенств, которые называют константами задачи;

Коэффициенты при переменных в целевой функции, которые называют оценками переменных;

Индекс переменной;

Индекс ограничения.

Целевой функцией (функцией цели) называется математическое выражение, для которого требуется найти экстремальное, то есть максимальное или минимальное, значение.

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

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

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

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

Дополнительные и вспомогательные переменные всегда имеют единичные коэффициенты (+1 или –1).

Технико-экономические коэффициенты (a ij) при переменных в системе ограничений выражают нормы затрат производственных ресурсов или норму выхода продукции в расчете на единицу измерения переменной величины.

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

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

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

Правой части ограничений (b i) называют константами, т.е. постоянными величинами. К ним относят объемы производственных ресурсов – земли, труда, техники, удобрений, капиталовложений и т.д. Производственные ресурсы должны быть определены с учетом их фактического состояния и обязательно учитывать период планирования. Кроме того, те производственные ресурсы, использование которых в течение года неравномерно, рассчитывают не только за год в целом, но и по отдельным напряженным периодам или месяцам (трудовые ресурсы).

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

Таким образом, определение наличия производственных ресурсов не простое дело. Необходимо тщательно проанализировать производственную деятельность хозяйства, использование трудовых, земельных, технических и прочих ресурсов, и только после этого включать их объемы в ограничения.

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

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

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

v отражать в задаче только те условия, которые действительно ограничивают возможности производства;

v слишком большое количество ограничений увеличивает размеры задачи и делает ее трудноразрешимой

Ограничения бывают трех типов: равенства (=), неравенства типа меньше либо равно (≤), неравенства типа больше либо равно (≥). Например,

где i = 1, 2, … , m . Коэффициенты при переменных обозначаются a ij , где индекс i – номер ограничения, индекс j – номер переменной, свободные члены (правая часть ограничений) обозначаются b i , индекс i – номер ограничения.

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

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

Основные ограничения – это те, которые накладываются на все или большинство переменных задач. Как правило, с их помощью отражаются основные условия задачи – по земле, труду, кормам, питательным веществам, технике и т.д.

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

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

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

Условие неотрицательности переменных записывается в виде

x j ≥ 0, j = 1, 2, …, n .

В реальной жизни производства, исходя из условий задания, по данной записи структурной экономико-математической модели (ЭММ) составляется перечень переменных величин и ограничений, подготавливается исходная информация, строится развернутая ЭММ задачи, которая затем записывается в виде матрицы (таблицы), вводится в компьютер и по соответствующей программе производится расчет и анализ результатов.i = 1, …, m , (1.5)

j = 1, …, n . (1.6)

Вектор x = (x 1 , x 2 , …, x n), компоненты x j которого удовлетворяют ограничениям (1.2) и (1.3) [или (1.5) и (1.6) в задаче на минимум], называется допустимым решением или допустимым планом задачи ЛП. Совокупность всех допустимых планов называется множеством допустимых планов.

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

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

Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на – 1;

3) если среди ограничений имеются неравенства, то путем введения дополнительных переменных неотрицательных переменных они преобразуются в равенства. Например, дополнительные переменные S j в ограничения типа меньше либо равно (£) вводятся со знаком плюс:

Дополнительные переменные S j в ограничения типа больше либо равно (≥) вводятся со знаком минус:

Для устранения отрицательности дополнительных переменных – S j вводят искусственные переменные со знаком плюс + М j c очень большими значениями.