Линейное программирование (практика)

Исследование операций

Контрольные вопросы по предмету

0


Подпишитесь на бесплатную рассылку видео-курсов:

Текст видеолекции

Содержание лекции:

  1. Производственная задача (математическая модель).
  2. Графический метод решения производственной задачи.
  3. Решение производственной задачи табличным симплекс-методом.

Следует заметить, что в 3-м разделе лекции будет рассмотрено решение задач симплекс-методом не только вручную, но и с использованием компьютерной  программы  Excel.

 

  1. 1.      Производственная задача (математическая модель)

 

Реальные объекты слишком сложны, поэтому для их изучения создают модели – копии изучаемых реальных объектов. Модели должны быть доступны для изучения. Они не должны быть слишком сложными. Так как выводы, полученные при их изучении, будут распространяться на реальные объекты (прототипы), то модель должна отражать существенные черты изучаемого объекта. Чем удачнее будет подобрана модель, тем лучше она будет отражать существенные черты реального объекта, тем успешнее будет ее исследование и полезнее вытекающие из этого исследования выводы и рекомендации.

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

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

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

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

При решении конкретной экономической задачи требуется соответственно и экономическая информация. Характер информации определяется содержанием экономико-математической задачи и математическим методом её решения.

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

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

1. Задача использования сырья (задача планирования производства).

Для изготовления двух видов продукции Р1 и Р2 используют три вида сырья: S1, S2 и S3. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 1. Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.

Таблица 1

Виды сырья

Запасы сырья

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

Р1

Р2

S1

S2

S3

b1

b2

b3

a11

a21

a31

a12

a22

a32

Прибыль от единицы продукции

(в руб.)

c1

c2

 Составим экономико-математическую модель (математическое описание исследуемого экономического процесса) задачи.

Обозначим через x1, x2 количество единиц продукции соответственно Р1, Р2, запланированных к производству. Тогда учитывая количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также запасы сырья, получим систему ограничений

                                                     (1)

По смыслу задачи переменные x1³0, x2³0.                                             (2)

Суммарная прибыль F(x) составит с1x1  руб. от реализации продукции Р1 и с2x2  руб. – от реализации продукции  Р2, т.е.

F(x) =с1x1 + с2x2 .                                       (3)

Итак, экономико-математическая модель задачи: найти такой план выпуска продукции X=(x1, x2), удовлетворяющий системе (1) и условию (2), при котором функция (3) принимает максимальное значение.

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

2. Задача составления рациона (задача о диете)

Имеется два вида корма I и II, содержащие питательные вещества (витамины) S1, S2 и S3. Содержание количества единиц питательного вещества в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице 2.

 Таблица 2

Питательные

вещества

Необходимый минимум питательных веществ

Количество единиц питательного вещества в 1 кг корма

Корм I

Корм II

S1

S2

S3

b1

b2

b3

a11

a21

a31

a12

a22

a32

Стоимость 1 кг корма (в руб.)

c1

c2

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

Составим экономико-математическую модель задачи. Обозначим через x1 и x2  соответственно количество кормов I и II, входящих в дневной рацион. Принимая во внимание значения, приведенные в табл. 2, и условие, что дневной рацион удовлетворяет требуемой питательности только в случае, если количество единиц питательных веществ не меньше предусмотренного, получим систему ограничений

                                      (4)

Кроме того, переменные

                                                     x1³0, x2³0.                                            (5)

Общая стоимость рациона (в руб.) составит

                                           F(x) =с1x1 + с2x2 .                                (6)

Итак, экономико-математическая модель задачи: составить дневной рацион X=(x1, x2), удовлетворяющий системе (4) и условию (5), при котором функция (6) принимает минимальное значение.

 3. Задача о раскрое материалов.

На раскрой поступает материал одного образца в количестве a единиц. Требуется изготовить из него l разных комплектующих изделий в количествах пропорциональных числам  b1, b2, …, bl (условие комплектности). Каждая единица материала может быть раскроена различными способами, при этом использование i-го способа (i =1, 2, …, n) дает aik единиц k-го изделия (= 1, 2, …, l). Требуется составить план раскроя, обеспечивающий максимальное количество комплектов.

Составим экономико-математическая модель задачи. Обозначим через xi количество единиц материала, раскраиваемых i-м способом, и x – количество изготавливаемых комплектов изделий.

Так как общее количество материала равно сумме его единиц, раскраиваемых различными способами, то

                                              (7)

Условие комплектности выразится уравнениями

          (= 1, 2, …, l),                   (8)

по смыслу задачи переменные

                                                    xi³0 (= 1, 2, …, n).                            (9)

Итак, экономико-математическая модель задачи: найти такое решение X=(x1, x2, …, xn), удовлетворяющее системе уравнений (7) – (8) и условию (9), при котором функция F = x принимает максимальное значение. 

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

 

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

Задача 1. Для изготовления различных изделий А и В  используется три вида сырья. На производство единицы изделия А его требуется затратить: первого вида 10 кг, второго вида – 9 кг, третьего вида – 5 кг. На производство единицы изделия В  требуется затратить: первого вида 6 кг, второго вида – 3 кг, третьего вида – 4 кг. Производство обеспечено сырьем первого вида в количестве 730 кг, второго – 765 кг, третьего – 455 кг. Прибыль от реализации единицы готового изделия А составляет 8 руб., изделия В – 5 руб. Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации.

Решить задачу графическим методом.

Решение. Составим математическую модель задачи. Обозначим x1, x2 – количество изделий соответственно вида А и В, запланированных к производству. Так как имеются ограничения на сырье каждого вида, то переменные x1, x2 должны удовлетворять следующей системе неравенств:

 

По своему экономическому содержанию переменные

x1³0, x2³0.

Общая прибыль при этом составит

F(x) =8x1 +5x2.

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

Решим задачу графическим методом.

Построим многоугольник решений. Для этого в неравенствах системы ограничений знаки неравенств заменим на знаки точных равенств. Получим:

 

Построив полученные прямые, найдем соответствующие полуплоскости и их пересечение. Как видно из рисунка, многоугольником решений задачи является четырехугольник ОABC. Координаты точек этого многоугольника удовлетворяют неравенствам системы ограничений задачи. Следовательно, наша задача будет решена, если среди точек многоугольника решений будет найдена такая, в которой функция F(x) принимает максимальное значение. Для ее нахождения построим прямую 8x1 +5x2=0 (число 0 взято произвольно) и вектор =(8; 5). Передвигая данную прямую параллельно самой себе в направлении вектора , видим, что ее последней общей точкой с многоугольником решений задачи является точка B. Следовательно, в этой точке функция F(x)  принимает максимальное значение. Эта точка является пересечением прямых (I), (III), следовательно, ее координаты удовлетворяют системе

 

Решив эту систему, получим:

x1*=19x2*=90, Fmax= 8×19 +5×90=602.

Ответ: Оптимальный опорный план X* =(19; 90), x1*=19x2*=90, Fmax= 602

 

Рисунок 1

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

F(x) =4x1 -2x2 +x3 -x4 ® min

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

 

xj³0, j=1,…,4.

Решение.

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

F-4x1 + 2x2 - x3 + x4 =0,

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

№ итерации

 

 

 

 

 

?

 

Исходная система

 

F

1

–1

4

–2

2

4

min 

3

2

–1

4

3

11

 

4

–2

1

–1

0

2

 

 

I

F

1

–1

4

–2

2

4

 

0

5

–13

10

–3

–1

min 

0

2

–15

7

–8

–14

 

 

II

F

1

0

1,4

0

1,4

3,8

 

0

0,5

–1,3

1

–0,3

–0,1

 

0

–1,5

–5,9

0

–5,9

–13,3

 

 После второй итерации система уравнений оказалась разрешенной относительно переменных x1 и x4. Итак,

F(x)=0x1+1,5x2+5,9x3 +0x4+5,9®min

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

 

xj³0, j=1,…,4.

Перейдем от канонической к стандартной модели. Отбрасывая в уравнениях базисные переменные x1 и x4, придем к следующей задаче:

F(x)= -1,5x2 - 5,9x3 - 5,9®max

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

 

x2³0, x3 ³0 .

На рисунке 2 показано графическое решение этой задачи.

Оптимальное решение Xопт совпадает с точкой А(2; 1).

Fmax=F(2; 1) = -1,5×2-5,9×1 -5,9 = -14,8

Таким образом, оптимальное решение исходной задачи

Xопт = (0; 2; 1; 0).

Соответствующее значение функции Fmin = 14,8.

 

Рисунок 2

 

  1. 3.      Решение производственной задачи табличным симплекс-методом

 

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

В качестве примера рассмотрим задачу 1 из предыдущего раздела лекции и решим её табличным симплекс-методом.

Задача 1. 

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

 

Эти дополнительные переменные по экономическому смыслу означают не используемое при данном плане производства количество сырья того или иного вида. Например, x3  – неиспользуемое сырье 1-го вида, x4  – неиспользуемое сырье 2-го вида, x5  – неиспользуемое сырье 3-го вида.

Преобразованную систему уравнений запишем в векторной форме:

А1x1 + А2x2 + А3x3 + А4x4 + А5x5 = А0,

где

 

Так как среди векторов А1, А2, А3, А4, А5 имеется три единичных вектора, для данной задачи можно непосредственно записать опорный план. Таковым является Х0=( 0; 0; 730; 765; 455).

Получаем симплексную таблицу для 1-й итерации.

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

 

i

Базисные переменные

 

 

 

 

8

5

0

0

0

 

 

 

 

 

 

1

 

0

730

10

6

1

0

0

73

2

 

0

765

9

3

0

1

0

85

3

 

0

455

5

4

0

0

1

91

  4

 

0

–8

–5

0

0

0

 

 Определим вектор, подлежащий исключению из базиса. Для этого находим

 .

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

Теперь осуществим переход к следующей симплекс-таблице. Для этого сначала делим все элементы ведущей строки на ведущий элемент (10). Затем в ведущей строке столбца Сб помещаем коэффициент Сk, соответствующий ведущему столбцу (8). По правилу прямоугольника добиваемся того, чтобы в ведущем столбце все элементы, кроме ведущего, стали равны нулю.

Получаем симплексную таблицу для 2-й итерации: 

 

i

Базисные переменные

 

 

 

 

8

5

0

0

0

 

 

 

 

 

 

1

 

8

73

1

3/5

1/10

0

0

365/3

2

 

0

108

0

–12/5

–9/10

0

0

 

3

 

0

90

0

1

–1/2

1

1

90

4

 

584

0

–1/5

4/5

0

0

 

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

 .

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

Теперь осуществим переход к следующей таблице: 

 

i

Базисные переменные

 

 

 

 

8

5

0

0

0

 

 

 

 

 

 

 

 

1

2

3

 

 

 

8

0

5

19

324

90

1

0

0

0

0

1

2/5

-21/10

-1/2

0

1

0

-3/5

12/5

1

 

4

 

584

0

0

7/10

0

1/5

 

 

 

 

 

 

 

 

 

 

 

 

 

                           

 Так как в последней строке таблицы все элементы положительны, то полученный план является оптимальным:

,   .

Следовательно, данный план предусматривает производство 19 изделий вида A и 90 изделий вида В.

При этом расход сырья следующий (смотри  х3, х4, х5): сырье 1-го вида используется полностью, остается неиспользованным 324 единицы сырья 2-го вида, сырье 3-го вида используется полностью.

Надстройка «Поиск решения»

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

Сервис Þ Надстройки Þ Поиск решений (отметить) Þ Ок.

 

Рисунок 3. Активация команды Поиск решения 

«Поиск решения» при оптимизации линейного программирования использует симплекс- метод.

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

 

Рисунок 4. Диалоговое окно надстройки Поиск решения

С помощью кнопки Добавить вводятся необходимые ограничения.

 

Рисунок 5. Диалоговое окно надстройки

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

 

Рисунок 6. Диалоговое окно надстройки, уточняющее параметры поиска решения

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

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

Значение в поле Сходимость используется для завершения процесса поиска решения, когда изменение целевой функции происходит очень медленно. Если установить меньшее значение сходимости, чем предусмотрено по умолчанию (0,0001), программа продолжит процесс оптимизации даже при малых изменениях целевой функции.

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

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

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

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

Команда Выполнить запускает решение задачи. Поиск решения просит уточнить: сохранить ли найденное решение или нет.

 

Рисунок 7. Диалоговое окно надстройки

Задача 2.

Предприятие выпускает три вида продукции: А, В и С. Для производства продукции оно располагает ресурсами в следующих объемах (единиц): комплектующие изделия – 3120; сырье – 3000; материалы – 3150.

Расход ресурсов на единицу продукции каждого вида представлен в таблице:

Ресурсы

Вид продукции

А

В

С

Комплектующие изделия

4

6

8

Сырье

2

8

10

Материалы

6

9

4

 Прибыль от реализации единицы продукции вида А составляет 240 млн. руб., В – 210 млн. руб., С – 180 млн. руб.

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

Решение.

Система переменных определяется в соответствии с условия­ми задачи: x1 – объем производства продукции вида А, x2– вида В и х3 – вида С.

Общую прибыль предприятия от производства и реализации всей продукции

f (X) = 240x1+210 x2+ 180х3 ® max

Система ограничений по ресурсам:

 

Объемы производства продукции не могут быть отрицательными, поэтому  xj 0, j = 1, 2, 3.

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

1. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). В нашей задаче они будут помещены в ячейках B4 – D4 и F6.

2. Ввести исходные данные (переменные B3 – D3,  прибыль B6 – D6, ограничения  B9 – D11 и объем ресурсов G9 –G11).

3. Ввести зависимость для целевой функции (E6).

4. Ввести зависимости для ограничений (Е9 – Е11).

Вариант размещения исходных данных задачи на листе электронной таблицы Excel показан на рисунке. 

 

Функция СУММПРОИЗВ в 6, 9, 10 и 11-й строках занесена с помощью кнопки  Мастер функций.

5.   Запустить команду Поиск решения.

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

7.   Ввести ограничения.

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

 

          8.   Ввести параметры для решения задач линейного программирования.

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

 

 Результат решения:

х1 = 397,5;    х2 = 0;    х3 = 191,25;    fmax = 129 825.

 

Задача 3.

Найти минимум функции

 

при условиях

 

 

Решение.

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

 

при условиях

 

 

Среди векторов  (j = 1 ,2…, 6) имеется два единичных ( и ). Поэтому в левую часть третьего уравнения системы ограничений задачи добавим дополнительную неотрицательную переменную  и запишем Т-задачу:

 

при условиях

 

 

Т-задача имеет опорный план  = (0; 0; 0; 24; 22; 0; 10), определяемый системой трех единичных векторов , , .

Решим ее симплексным методом. 

итерации

Базисные переменные

 

2

-3

6

1

0

0

-M

 

x1

x2

x3

x4

x5

x6

x7

0

x4

x5

x7

1

0

М

2

1

1

1

2

-1

-2

4

2

1

0

0

0

1

0

0

0

-1

0

0

1

24

22

10

 

 (М-функция)

0

4

М

-8

-2М

0

0

0

0

0

М

0

0

24

-10М

I

x4

x5

x3

1

0

6

3

-1

1/2

0

4

-1/2

0

0

1

1

0

0

0

1

0

-1

2

-1/2

 

34

2

5

 (М-функция)

4

0

0

0

0

0

0

0

0

0

-4

0

 

64

0

II

x4

x6

x3

1

0

6

5/2

-1/2

1/4

2

2

1/2

0

0

1

1

0

0

1/2

1/2

1/4

0

1

0

 

35

1

11/2

 (М-функция)

2

0

8

0

0

0

0

0

2

0

0

0

 

68

0

 В последней итерации все ?> 0. Это означает, что найденный план (0; 0; 5,5; 35; 0; 1; 0) является оптимальным для Т-задачи. Так как x7=0, план  (0; 0; 5,5; 35; 0; 1) является оптимальным планом исходной задачи.

Fmax = 68.

 

Список литературы

1. Пантелеев, А.В. Методы оптимизации в примерах и задачах. - Москва: Высшая школа, 2008.

2. Струченков, В.И. Методы оптимизации. Основы теории, задачи, обучающие компьютерные программы. - Москва: Экзамен, 2005.

3. Е. С. Вентцель, Исследование операций: задачи, принципы, методология. Из-во Дрофа, 2006.

4. Е. В. Шикин, Г. Е. Шикина, Исследование операций. Из-во Проспект, 2006.