39535

Математическое программирование (ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ)

Книга

Информатика, кибернетика и программирование

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

Русский

2013-10-07

2.42 MB

240 чел.

Э.В. Киселева

С.И. Соловьева

математическое

программирование

(ЛИНЕЙНОЕ  ПРОГРАММИРОВАНИЕ)

НОВОСИБИРСК 2002

Э.В. Киселева

С.И. Соловьева

математическое

программирование

(ЛИНЕЙНОЕ  ПРОГРАММИРОВАНИЕ)

НОВОСИБИРСК 2002

Оглавление

Введение ……………………………………………………..

5

1.

Примеры экономических задач

линейного программирования……..................

12

1.1. Задача оптимального производственного планирования…………………………………………………...............

12

1.2.  Задача о смесях……………………………………......

13

1.3.  Задача о раскрое....…………………………………....

15

1.4. Транспортная задача ……………………………….....

16

1.5. Вопросы для самопроверки ……………………….....

18

2.

Некоторые сведения из линейной алгебры..

19

2.1. Основные понятия и теоремы …………………….....

19

2.2. Решение систем линейных алгебраических уравнений методом ЖорданаГаусса..................……………........

20

3.

Различные формы модели задачи

линейного программирования …................….

26

3.1. Формулировка основной задачи линейного программирования …………………………….…………….............

26

3.1.1. Общая форма модели ………………………........

26

3.1.2. Стандартная форма модели ………………..........

26

3.1.3. Каноническая форма модели ……………...........

27

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

28

3.3. Переход от задачи минимизации целевой функции

к задаче максимизации ……………………………............

28

3.4. Переход от одной формы модели задачи линейного программирования к другой.................................................

29

3.4.1. Переход к канонической форме модели ….....

29

3.4.2. Переход от канонической формы модели задачи линейного программирования к стандартной........

32

3.5. Выпуклые множества …………………….……….......

34

4.

Графический метод решения ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ …..................….….

36

4.1. Геометрическая интерпретация множества решений линейного неравенства ……………………………............

36

4.2. Геометрическая интерпретация множества решений системы линейных неравенств …….……………...............

37

4.3. Вопросы для самопроверки ………………………......

46

5.

Свойства допустимых планов ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. Опорный план..

47

6.

Симплекс-метод …………………………..................

51

6.1. Идея симплекс-метода ……………………………......

51

6.2. Алгебра симплекс-метода ………………………….....

55

6.2.1. Алгоритм симплекс-метода ……………….......

58

6.2.2. Выбор разрешающей строки в симплексных преобразованиях ……………………………...............

61

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

62

6.2.4. Признак неограниченности целевой функции..

63

6.3. Понятие о вырождении …………………………….....

65

6.4. Вопросы для самопроверки ………………………......

76

6.5. Индивидуальное задание ……………...........................

77

6.6. Задачи для самостоятельной работы …….………......

85

7.

Двойственность в линейном программировании ………………......………………………………

88

7.1. Пример двойственных задач линейного программирования………………….. …………………....…………….

88

7.2. Правила построения двойственных задач ……….......

90

7.3. Симметричные двойственные задачи ……………......

92

7.4. Основные теоремы двойственности ……………........

98

7.5. Анализ устойчивости двойственных оценок …….....

115

7.6. Вопросы для самопроверки ……………………….....

122

7.7. Индивидуальное задание ……….........................…….

122

ЗАКЛЮЧЕНИЕ………………………………………………….

127

Библиографический список ………………………...

128

Приложение. Применение программы Excel к решению задач линейного программирования ………………………….

130

В мире не происходит ничего,

в чем не был бы виден

смысл какого-нибудь

максимума или минимума.

Л. Эйлер

ВВЕДЕНИЕ

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

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

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

Так в XX в. появились новые математические дисциплины, в числе которых математическое программирование.

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

Наиболее разработанной в настоящие время составной частью математического программирования является линейное программирование.

Впервые постановка задачи линейного программирования в виде предложения по составлению оптимального плана перевозок, позволяющего минимизировать суммарный километраж, дана в работе советского математика А.Н. Толстого (1930). В 1931 г. венгерский математик  Б. Эгервари рассмотрел математическую постановку и решил задачу, имеющую название «проблема выбора», метод решения которой получил название венгерский метод. В 1939 г. советский ученый Л.В. Канторович указал общий метод (метод разрешающих множителей) решения задач, связанных с составлением оптимального плана при организации производственных процессов (в связи с решением задачи оптимального распределения работы между станками фанерного треста в Ленинграде). Он же совместно с М.К. Гавуриным в 1949 г. разработал метод потенциалов, используемый при решении транспортных задач. В последующих работах Л.В. Канторовича, В.С. Немчинова, В.В. Новожилова, А.Л. Лурье, А.Г. Аганбегяна, Д.Б. Юдина, Е.Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение ее методов к исследованию различных экономических проблем.

В 1949 г. американским математиком Дж. Данцигом (G.BDantzig) был опубликован основной метод решения задач линейного программирования  симплекс-метод. Термин «линейное программирование» впервые появился в 1951 г. в работах    Дж. Данцига и Т. Купманса.

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

  1. Постановка задачи.
  2. Построение (составление) математической модели.
  3. Выбор метода решения и решение задачи.
  4. Проверка полученного решения на его адекватность изучаемому явлению и корректировка модели в случае необходимости.
  5. Реализация найденного решения на практике.

Остановимся подробнее на втором этапе.

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

В построении математической модели можно выделить следующие моменты:

  1. Выбор неизвестных величин    Х = (х1,…, хn),  воздействуя на которые можно изменять поведение изучаемого процесса. Их называют переменными, управляемыми параметрами, планом, стратегией и т.д.
  2. Необходимо выделить цель (максимизация прибыли, минимизация затрат и др.) функционирования изучаемого процесса и записать ее в виде математической функции от выбранных переменных. Такая функция называется целевой (функция цели, критерий оптимальности, критерий качества, показатель эффективности и т.д.) и позволяет, изменяя значения управляемых параметров x1,…, xn, выбрать наилучший вариант из множества возможных. Будем обозначать функцию цели Z = f (X).
  3. Запись в виде математических соотношений (уравнений, неравенств) условий, налагаемых на переменные. Эти соотношения называют ограничениями, они могут вытекать, например, из ограниченности ресурсов. Совокупность всех ограничений составляет область допустимых решений (ОДР). Будем обозначать ее буквой D (XD).

При таких обозначениях модель задачи математического программирования примет вид:

или в развернутом виде:

найти план доставляющий экстремальное значение целевой функции  Z, т.е.

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

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

Краткая классификация моделей и методов

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

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

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

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

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

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

К стохастическим моделям, в частности, относятся:

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

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

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

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

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

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

,

или мультипликативной

,

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

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

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

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

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

Классические методы нахождения экстремума функции многих переменных связаны с решением системы уравнений:

Очевидно, для линейной функции Z:

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

1. ПРИМЕРЫ ЭКОНОМИЧЕСКИХ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.1. Задача оптимального производственного планирования

Для изготовления n видов продукции P1,…,Pn используется m  видов сырья  S1,…,Sm,  запасы которого ограничены и составляют соответственно  b1,…,bm  единиц. Известно, что на производство единицы продукции  Pj (j=) расходуется аij единиц ресурса Si (i=, а прибыль от реализации единицы продукции Pj (j= составляет сj (j=.

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

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

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

Вид сырья

Р1

...

Pj

...

Pn

Запас

ресурса

S1

a11

...

a1j

...

a1n

b1

...

...

...

...

...

...

...

Si

ai1

...

aij

...

ain

bi

...

...

...

...

...

...

...

Sm

am1

...

amj

...

amn

bm

Прибыль

c1

cj

cn

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

Обозначим через  xj (j=планируемое к выпуску количество продукции  Рj  (j=, а через Z1,…, xn) – прибыль предприятия от реализации всей продукции.

Тогда планом производства будет вектор Х = (х1,…,хn), показывающий, какое количество продукции каждого вида будет произведено. Переменные   х1,…,хn – управляемые переменные.

Цель решения задачи (критерий оптимальности) – максимизировать прибыль:

Z = c1x1 + c2x2 +. . . + cnxn .

Суммарные затраты ресурса  Si (i=составляют:

.

В силу ограниченности ресурса Si величиной bi получим систему ограничений:

.

На переменные хj должно быть наложено условие неотрицательности т.е. продукция Рj может либо выпускаться (xj > 0), либо не выпускаться (xj = 0).

Итак, математическая модель примет вид:

,

.

1.2. Задача о смесях

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

Пусть имеется  m видов сырья, запасы которого составляют соответственно  d1,…, dm. Из этого сырья необходимо составить смесь, содержащую n веществ, определяющих технические характеристики смеси. Известны величины определяющие количество j-го вещества в единице -го вида сырья, цена которого равна а также  наименьшее допустимое количество j-го вещества в смеси.

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

Для составления математической модели запишем условия задачи в виде таблицы:

Вид вещества

Вид сырья

1

...

j

...

n

Объем

сырья

Цена

сырья

1

a11

...

a1j

...

a1n

d1

c1

...

...

...

...

...

i

ai1

...

aij

...

ain

di

ci

...

...

...

...

...

m

am1

...

amj

...

amn

dm

cm

Минимальное количество вещества в смеси

b1

...

bj

...

bn

Обозначим через хi количество сырья i-го вида, входящего в состав смеси.

Цель задачи (целевая функция) – минимизировать суммарные затраты на сырье:

.

Система ограничений включает в себя ограничения по техническим характеристикам:

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

.

Запишем модель в компактной форме:

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

1.3. Задача о раскрое

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

Пусть на обработку поступает  a единиц сырьевого материала одного вида (например, a бревен одной длины). Из него требуется изготовить комплекты, в каждый из которых входит  n видов изделий в количестве, пропорциональном числам . Имеется  m способов раскроя (обработки) данного материала, т.е. известны величины  определяющие количество единиц j-х изделий при i-м способе раскроя единицы сырьевого материала.

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

    Вид изделия

Способ раскроя

1

...

j

...

n

1

a11

...

a1j

...

a1n

...

...

...

...

...

i

ai1

...

aij

...

ain

...

...

...

...

...

m

am1

...

amj

...

amn

Пусть – количество единиц сырьевого материала, раскраиваемого i-м вариантом (.

Тогда количество изделий 1-го вида равно:

.

Принимая во внимание условие комплектности, имеем:

где y – количество комплектов.

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

Очевидно,

(на раскрой поступает a единиц сырьевого материала), а также

Цель задачи – максимизировать количество комплектов:

.

Итак, приходим к математической модели задачи о раскрое:

,

.

Чтобы выразить целевую функцию через переменные x1,…,xm, достаточно воспользоваться любым из соотношений:

1.4. Транспортная задача

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

Пусть имеется m пунктов производства однородного продукта (добыча руды в карьерах, производство автобусов, кондитерских изделий, компьютеров и т.д.) и n пунктов потребления этого продукта. Мощности пунктов производства составляют аi  единиц однородного продукта, а потребности каждого j-го пункта потребления равны единиц. Известны затраты на перевозку единицы продукта от i-го поставщика j-му потребителю. Составить такой план перевозок, при котором суммарные затраты на все перевозки были бы наименьшими. Пусть спрос и предложение совпадают, т.е. Такую транспортную задачу называют сбалансированной (закрытой). При этом предполагается, что вся продукция от поставщиков будет вывезена и спрос каждого из потребителей будет удовлетворен.

Составим математическую модель задачи. Обозначим через  количество продукта, перевозимого из i-го пункта производства в j-й пункт потребления. Тогда матрица:

 план перевозок.

Матрицу называют матрицей затрат (тарифов).

Внесем исходные данные и перевозки в транспортную таблицу:

     bj

ai

b1

b2

...

bn

a1

       c11

x11

       c12

x12

...

       c1n

x1n

a2

       c21

x21

       c22

x22

...

       c2n

x2n

...

...

...

...

...

am

       cm1

xm1

       cm2

xm2

...

       cmn

xmn

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

которую необходимо минимизировать при ограничениях:

(весь продукт из каждого i-го пункта должен быть вывезен полностью),

(спрос каждого j-гопотребителя должен быть полностью удовлетворен).

Из условия задачи следует, что все

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

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

.

1.5. Вопросы для самопроверки

  1. Предмет математического программирования.
  2. Основные этапы решения задачи математического программирования.
  3. Краткая классификация моделей и методов математического программирования.
  4. Понятие математической модели.
  5. Постановка задачи оптимального производственного планирования. Математическая модель.
  6. Задача о смесях. Постановка и математическая модель.
  7. Задача о раскрое. Постановка и математическая модель.
  8. Транспортная задача. Постановка и математическая модель.
  9. Этапы решения задачи математического программирования.

2. НЕКОТОРЫЕ СВЕДЕНИЯ ИЗ ЛИНЕЙНОЙ АЛГЕБРЫ

2.1. Основные понятия и теоремы

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

Определение 2.1. Упорядоченная совокупность  n действительных чисел называется  n-мерным вектором.

Определение 2.2. Совокупность всевозможных n-мерных векторов после введения в нее операций сложения и умножения на действительное число называется n-мерным линейным векторным пространством.

Частными случаями линейных пространств являются прямая, плоскость, трехмерное пространство.

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

0.

Если же это равенство возможно лишь в случае, когда все , то система векторов называется линейно независимой.

Определение 2.4. Базисом n-мерного векторного прос-транства называется любая совокупность n линейно независимых векторов этого пространства.

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

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

Теорема 2.1. Любой вектор n-мерного векторного пространства можно представить как линейную комбинацию векторов базиса, притом единственным образом.

Определение 2.6. Максимальное число линейно независимых векторов линейного пространства называется размерностью линейного пространства.

Линейное пространство обычно обозначают где n – его размерность.

  1. Решение систем линейных алгебраических уравнений методом Жордана–Гаусса

Метод Жордана–Гаусса, или метод последовательного исключения неизвестных, является модификацией метода Гаусса решения систем линейных алгебраических уравнений (СЛАУ). Он также базируется на так называемых элементарных преобразованиях (преобразованиях, переводящих систему в эквивалентную), к которым относятся:

  1. Прибавление к обеим частям одного уравнения системы другого уравнения той же системы, умноженного на некоторое число, отличное от нуля.
  2. Перестановка местами уравнений в системе.
  3. Удаление из системы уравнений вида 0=0.

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

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

Рассмотрим систему:

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

x1

x2

xs

xn

Свободный  член

a11

a12

a1s

a1n

b1

ar1

ar2

ars

arn

br

am1

am2

ams

amn

bm

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

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

  1. элементы разрешающей r-строки вычисляются так:            (2.1)
  2. все элементы разрешающего столбца, кроме станут равными  нулю;
  3. элементы, не принадлежащие разрешающей строке и разрешающему столбцу, вычисляются по формуле:

.   (2.2)

j

столбец

s

столбец

i-я

строка

aij

ais

r-я

строка

arj

ars

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

В ходе применения метода Жордана–Гаусса возможны следующие случаи:

1. В процессе исключений левая часть уравнения системы обращается в нуль, а правая часть равна некоторому числу b, отличному от нуля, т.е. получаем равенство:

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

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

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

Рассмотрим применение метода Жордана–Гаусса на примерах решения СЛАУ.

Пример 2.1. Решить методом Жордана–Гаусса систему

Решение. Запишем в таблицу Гаусса расширенную матрицу системы, и в последний, контрольный столбец поместим суммы элементов соответствующих строк.

На первом шаге за разрешающий элемент можно выбрать любой элемент Выберем .

Шаг

x1

x2

x3

bi

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

1

1

1

2

0

1

–1

1

–1

0

1

–1

–2

3

2

1

–2

5

3

3

1

1

0

0

0

0

1

–1

1

–1

1

2

1

–2

5

4

5

–2

7

5

7

2

1

0

0

0

0

1

0

0

–1

1

3

0

–2

5

9

0

–2

7

12

0

3

1

0

0

0

1

0

0

0

1

1

2

3

2

3

4

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

.

Остальные элементы пересчитываем по формуле (2.2). Так, например,      , .

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

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

или

Ответ. Задача имеет единственное решение:

, , .

Пример 2.2. Исследовать и решить систему уравнений:

Решение.

Шаг

x1

x2

x3

x4

bi

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

2

3

5

1

0

1

1

1

–1

–1

–2

0

1

2

3

1

1

2

3

1

3

5

8

2

1

2

3

2

–2

0

1

0

0

–1

–1

–1

1

1

0

1

–1

1

2

1

–1

3

5

3

–3

2

2

3

0

0

0

1

0

0

–1

–1

0

0

1

0

0

0

1

2

0

0

3

5

0

0

На втором шаге два последних уравнения обратились в тождественные равенства 0 = 0. Исключаем их из дальнейшего рассмотрения. Первым двум строкам соответствует система уравнений:

которая эквивалентна исходной.

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

,  

где и любые действительные числа.

Переменные и являются свободными, а переменные и базисными.

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

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

Полученное таким образом решение:

называется базисным решением системы.

Ответ.  Задача имеет бесчисленное множество решений:

,

где и произвольные действительные числа.

3. РАЗЛИЧНЫЕ ФОРМЫ МОДЕЛИ ЗАДАЧИ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

3.1. Формулировка основной задачи

линейного программирования

3.1.1. Общая форма модели

Общая форма модели ЗЛП характеризуется следующим образом:

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

и условиям неотрицательности:

,

для которых линейная функция (целевая функция)

достигает экстремума (максимума или минимума).

3.1.2. Стандартная форма модели

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

 

и условиям неотрицательности:

 ,

для которых целевая функция:

достигает максимума.

Если ввести в рассмотрение матрицу:

и векторы:   ,   ,  ,

то стандартная форма модели примет вид:

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

3.1.3. Каноническая форма модели

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

 ()

и условиям неотрицательности:

 (),

для которых целевая функция достигает максимума.

Компактная форма модели имеет вид:

,

,

.

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

Определение 3.1. Вектор X, удовлетворяющий системе ограничений ЗЛП, в том числе и условиям неотрицательности, если они имеются, называется допустимым решением ЗЛП.

Определение 3.2. Совокупность всех допустимых решений образует область допустимых решений (ОДР) ЗЛП.

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

3.3. Переход от задачи минимизации целевой функции

к задаче максимизации

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

.

Обе задачи имеют одно и то же решение и при этом

.

Проиллюстрируем этот факт графически на примере функции одной переменной:

Рис. 3.1.  и достигается в точке

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

3.4. Переход от одной формы модели задачи линейного программирования к другой

3.4.1. Переход к канонической форме модели

Пусть исходная ЗЛП задана в стандартной форме

,       (3.1)

    (3.2)

 .     (3.3)

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

              

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

Каноническая форма модели примет вид:

     (3.4)

,      (3.5)

.       (3.6)

Теорема 3.1.  Каждому решению () неравенства соответствует единственное  решение уравнения и неравенства , и наоборот.

Из данной теоремы следует эквивалентность систем ограничений исходной стандартной формы модели задачи и полученной канонической формы. А так как дополнительные переменные входят в целевую функцию с коэффициентами, равными нулю, то значения целевых функций (3.1) и (3.4) при соответствующих допустимых решениях и одинаковы. Отсюда следует, что целевые функции (3.1) и (3.4) на множестве соответствующих допустимых решений достигают экстремальных значений одновременно. Оптимальному решению () задачи (3.1)–(3.3) соответствует оптимальное решение  задачи (3.4)–(3.6), т.е. исходная модель и ее каноническая форма эквивалентны.

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

Вид ресурса

Нормы затрат ресурсов

Объем

ресурса

А

В

1

2

3

20

2

3

1

15

3

4

0

16

4

0

3

12

Прибыль

5

3

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

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

Решение. Обозначим через план выпуска продукции. Модель задачи примет вид:

Модель записана в стандартной форме.

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

Отметим экономический смысл дополнительных переменных. Очевидно,

 ,

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

3.4.2. Переход от канонической формы модели задачи линейного программирования к стандартной

Пусть ЗЛП задана в канонической форме:

,

 ,

 .

Первый способ

Каждое ограничение-равенство может быть заменено эквивалентной системой неравенств:

Неравенства умножением обеих частей на –1 превращаются в неравенства .

Второй способ

Предположим, в системе ограничений:

канонической формы модели и все m уравнений линейно независимы (ранг системы ). В этом случае система имеет бесчисленное множество решений. Ее можно разрешить относительно m переменных , например методом  Жордана–Гаусса, если векторы-столбцы коэффициентов при этих неизвестных линейно независимы:

 .    (3.7)

В этом случае являются базисными переменными, а свободные переменные.

Целевую функцию также выразим через свободные переменные, подставив значения из равенств (3.7) в функцию цели.

В результате преобразования получим:

,

так как , то из равенств (3.7) имеем:

 .

Стандартная форма модели ЗЛП примет вид:

,

 ,

 .

3. 5. Выпуклые множества

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

 .

В частности, выпуклой линейной комбинацией двух векторов (точек)  X 1 и X 2 является вектор:

, где

Определение 3.5. Множество D векторов (точек) линейного пространства называется выпуклым, если вместе с любыми его двумя точками и ему принадлежит отрезок, соединяющий эти точки.

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

.

На рис. 3.2 изображены выпуклые множества (а, б) и множество, не являющееся выпуклым (в).

а

б

в

Рис. 3.2. Примеры множеств

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

Например, крайними точками треугольника являются его вершины, крайними точками круга – точки окружности, которая его ограничивает.

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

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

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

4. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Рассмотрим графический метод решения ЗЛП в стандартной форме с двумя переменными, т.е. задачи вида:

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

для которого функция цели Z = c1x1+c2x2 достигает максимума.

Графический метод решения ЗЛП условно можно разбить на два этапа:

  1. Построение ОДР ЗЛП.
  2. Нахождение среди всех точек ОДР такой точки в которой целевая функция принимает максимальное значение.

Перейдем к рассмотрению этих этапов.

Этап 1

4.1. Геометрическая интерпретация множества решений линейного неравенства

Рассмотрим неравенство:

.

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

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

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

Пример 4.1. Геометрической интерпретацией решений неравенства является полуплоскость, изображенная на рис. 4.1 стрелками. Покажем это.

Рис. 4.1. Геометрическая интерпретация решений

линейного неравенства

Прежде всего в неравенстве заменим знак неравенства на знак точного равенства и построим соответствующую прямую . Эта прямая делит плоскость на две полуплоскости. Так как точка О (0,0) удовлетворяет неравенству , то областью решения данного неравенства является полуплоскость, которой принадлежит эта точка.

4.2. Геометрическая интерпретация множества решений системы линейных неравенств

Пусть дана система линейных неравенств с двумя неизвестными:

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

Возможные случаи области допустимых решений

На рис. 4.2. представлены возможные ситуации, когда ОДР ЗЛП – выпуклый многоугольник (а), неограниченная выпуклая многоугольная область (б), единственная точка (в), пустое множество (г), прямая линия (д), луч (е), отрезок (ж).

а

б

в

г

Рис. 4.2. Возможные случаи ОДР

д

е

ж

Рис. 4.2. (окончание)

Пример 4.2. Построить ОДР системы линейных неравенств:

Решение. В неравенствах системы и условиях неотрицательности переменных () знаки неравенств заменим на знаки равенств:     ,        (4.1)

,          (4.2)

,           (4.3)

(ось 0Х2),      (4.4)

(ось0Х1).      (4.5)

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

Итак, ОДР системы линейных неравенств является выпуклый многоугольник АВСDЕ.

Рис. 4.3. Область допустимых решений системы

линейных неравенств

Этап 2

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

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

Вектор называется градиентом функции Z. Он перпендикулярен линиям уровня и показывает направление наибольшего возрастания функции Z. Так как , то .

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

Рис. 4.4. Функция Z принимает максимальное значение

в точке М

Пусть, например, выпуклый многоугольник АВМСD является ОДР, а расположен так, как изображено на рис. 4.4. Тогда принимает максимальное значение в точке М.

Пример 4.3. Фирма выпускает продукцию двух видов: А и В, используя два вида взаимозаменяемого оборудования. Фонд времени работы оборудования ограничен соответственно величинами 120  и 260 ч. В таблице приведены нормы затрат времени на изготовление  единицы продукции каждого вида:

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

Вид оборудования

Нормы затрат

времени, ч

Фонд

времени, ч

А

В

1

2

4

120

2

4

2

260

Известен план выпуска продукции А и В, составляющий соответственно 50 и 70 единиц (перевыполнение плана не предполагается).

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

Решение. Обозначим через количество продукции j-го вида , выпускаемой на i-м оборудовании .

Условия задачи запишем в виде таблицы:

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

Вид  оборудования

А

В

Фонд

времени

1

2

4

120

2

4

2

260

План

50

70

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

.

Ограничения по фонду рабочего времени:

Ограничения по необходимости выполнения плана:

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

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

Построив соответствующие данным ограничениям-неравенствам граничные прямые:

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

Рис. 4.5. Целевая функция достигает минимального значения

в точке B

Далее построим вектор .

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

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

Для нахождения координат этой точки решим систему, составленную из уравнений граничных прямых АВ и ВС:

Получим .

Координаты и найдем из соотношений:

Итак, искомый оптимальный план

.

При этом минимальное значение целевой функции

.

Исходя из условий задачи, можно дать интерпретацию полученного решения: первый вид оборудования используется для выпуска продукции А в количестве 30 единиц, продукция В на первом виде оборудования не производится. На втором виде оборудования производится 20 единиц продукции А и 70 единиц продукции В. При этом затраты на выпуск продукции будут минимальными и составят 280 условных единиц.

4.3. Вопросы для самопроверки

  1. Запишите основную ЗЛП в общем виде.
  2. Запишите модель ЗЛП в стандартной и канонической формах. Матричная форма моделей.
  3. Как сводится задача минимизации целевой функции к задаче максимизации?
  4. Какова геометрическая интерпретация решения линейных неравенств с одной, двумя, тремя переменными?
  5. Что называется допустимым решением и ОДР задачи математического программирования?
  6. Какова геометрическая интерпретация решения системы линейных неравенств с двумя переменными?
  7. Постройте линию уровня целевой функции , соответствующую значению
  8. Чем определяется направление скорейшего возрастания целевой функции? Постройте для функции .
  9. Что называется оптимальным решением ЗЛП?
  10.  Какие случаи возможны при решении ЗЛП?
  11.  Как выражается оптимальное решение при наличии альтернативного оптимума?   

5. СВОЙСТВА ДОПУСТИМЫХ ПЛАНОВ ЗАДАЧИ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

ОПОРНЫЙ ПЛАН

Не ограничивая общности, рассмотрим свойства допустимых планов на примере канонической формы модели ЗЛП:

        (5.1)

       (5.2)

      (5.3)

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

Теорема 5.1.  Множество планов ЗЛП выпукло.

Необходимо показать, что если X1 и X2 – допустимые планы ЗЛП (5.1)–(5.3), то их выпуклая линейная комбинация:

где     ,

также является ее допустимым планом, т.е. удовлетворяет системе (5.1)–(5.3).

Итак, пусть X1 и X2 – допустимые планы задачи (5.1)–(5.3), т.е. справедливы соотношения:

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

или

т.е.                             

удовлетворяет системе (5.1).

А так как то также удовлетворяет условию (5.2).

Таким образом, доказано, что выпуклая линейная комбинация векторов X1 и X2 также является допустимым планом задачи (5.1)–(5.3) и, следовательно, согласно определению, множество планов ЗЛП выпукло.

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

Если же оно неограниченное, то его называют выпуклым многогранным множеством.

Теорема 5.2. Если целевая функция имеет максимум на выпуклом многограннике допустимых решений, то он достигается по крайней мере в одной из вершин этого многогранника.

Выпуклый многогранник имеет конечное число вершин, обозначим их через а точку, где функция Z имеет максимум, через X*. Очевидно,  

Если среди вершин найдется хотя бы одна вершина, например, для которой то теорема доказана.

Предположим противное, т.е. что Х* не является вершиной. Тогда для каждой вершины должно выполняться соотношение:

Но, согласно свойству ограниченных выпуклых множеств (см. теорему 3.2), точку можно представить в виде выпуклой линейной комбинации крайних точек (вершин):

.

Подставляя Х* в целевую функцию и принимая во внимание ее линейность, получим:

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

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

Теорема 5.3. Если целевая функция имеет максимум более чем в одной вершине выпуклого многогранника допустимых решений, то этот максимум достигается в любой точке, являющейся выпуклой линейной комбина-цией этих вершин.

Предположим, целевая функция достигает максимума в нескольких вершинах: многогранника, т.е.   Пусть  

Рассмотрим произвольную выпуклую линейную комбинацию этих вершин:

и покажем, что значение целевой функции также равно d.

Действительно, имеем:

Опорный план. Теорема о соответствии опорного плана вершине многогранника допустимых планов

Рассмотрим ЗЛП в канонической форме:

Предположим, что число линейно  независимых уравнений системы ограничений равно m (m<n). Методом Жордана–Гаусса приведем систему к базисному виду:

(Не ограничивая общности, можно считать, что базисными переменными являются .)

Очевидно, базисное решение системы имеет вид:

Определение 5.1. Неотрицательное базисное решение системы ограничений ЗЛП называется опорным решением (опорным планом) ЗЛП.

Из определения следует, что:

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

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

Теорема 5.4. Вектор Х является опорным планом ЗЛП тогда и только тогда, когда Х вершина многогранника допустимых планов.

Итак, для нахождения оптимального решения ЗЛП достаточно исследовать вершины выпуклого многогранника  допустимых решений. В этом и состоит основная идея симплекс-метода решения ЗЛП.

6. СИМПЛЕКС-МЕТОД

На основании свойств ЗЛП, рассмотренных в предыдущей главе, можно сделать следующие выводы.

Если решение ЗЛП существует, то оно достигается хотя бы в одной вершине (опорном решении) многогранника допустимых решений, следовательно, поиск оптимального решения необходимо осуществлять среди вершин многогранника (опорных решений).

Однако при больших и перебор всех вариантов практически нереален. Для решения ЗЛП был предложен симплекс-метод, разработанный в 1947–49 гг. американским математиком Дж. Данцигом. Идея симплекс-метода состоит в целенаправленном переборе вершин многогранника допустимых решений (опорных планов) в направлении «улучшения» значений целевой функции.

Замечание. «Симплекс» в переводе с латинского значит «простейший». В многомерной геометрии симплексом называется геометрическое место точек, удовлетворяющих условиям:

,  .

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

6.1. Идея симплекс-метода

Рассмотрим идею симплекс-метода на конкретном примере.

Пример 6.1.  

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

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

Замечаем, что система уравнений уже приведена к базисному виду (базисные неизвестные, свободные неизвестные).

Положив получаем первоначальное базисное решение

,   причем   .

Очевидно, это базисное решение является опорным, так как все  

Итак, первый этап симплекс-метода закончен.

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

Возникает вопрос, можно ли уменьшить значение целевой функции за счет перехода к новому опорному решению, в котором в базис будет введена одна из свободных переменных: либо , либо , либо . Очевидно, введение в базис переменной нецелесообразно, так как коэффициент при ней в функции цели равен +7 и увеличение этой переменной на единицу приведет к увеличению значения функции на 7 единиц. А вводя в базис или , мы можем уменьшить значение Z (поскольку коэффициенты при них отрицательны). Для определенности введем в базис , т.е. ту из свободных переменных, которая имеет наибольший по модулю отрицательный коэффициент .

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

Итак, вводим в базис.

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

Так как и остаются свободными переменными, т.е. , то система ограничений примет вид:

       (*)

Если вывести из базиса , т.е. положить , то получим , , что недопустимо (, ).

Если вывести из базиса , то получим , , , что соответствует опорному плану:

, .

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

.

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

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

и подставив его в целевую функцию , получим

.

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

Здесь базисные, а свободные переменные.

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

Разделив первое уравнение на 6, выразив из него и подставив его в функцию цели Z, получим задачу:

,

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

, причем .

Очевидно, что полученный опорный план является оптимальным, т.е.

,   

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

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

Поясним это на рассмотренном примере 6.1. Пусть, например, в системе (*) коэффициенты при переменной , которую хотим ввести в базис, в обоих уравнениях отрицательны:

    Откуда

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

6.2. Алгебра симплекс-метода

Дадим изложение симплекс-метода для ЗЛП вида:

,

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

Пусть ранг матрицы системы ограничений равен m, и все , . В матричной форме ЗЛП имеет вид:

,

.

Запишем условие задачи в виде таблицы:

Предположим, что являются базисными переменными (при необходимости можно произвести перенумерацию). Тогда первые m столбцов матрицы:

образуют квадратную невырожденную матрицу B (базисную матрицу) m-го порядка, а оставшиеся (n m) столбцов дают матрицу F размеров . Аналогичным образом вектор с разбивается на два вектора , где вектор коэффициентов при базисных неизвестных ; вектор при остальных свободных неизвестных.  – функции цели Z. Вектор.

Тогда исходная таблица примет вид:

0

Первая строка таблицы соответствует уравнению:

.

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

.

Полагая , найдем значения базисных переменных:

(единичная матрица m-го порядка).

Если при этом , то

является первоначальным опорным планом.

Эти преобразования системы ограничений соответствуют таблице:

0

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

.

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

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

0

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

В найденном опорном плане (при ) значение

.

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

6.2.1. Алгоритм симплекс-метода

  1. Запишем условия задачи:

в виде таблицы:

БП

х1

...

хn

Свободный член

a11

...

a1n

b1

...

...

...

...

am1

...

amn

bm

Z

c1

...

cn

0

,

которую будем называть симплекс-таблицей. В левом столбце записываются базисные переменные (БП).

  1. С помощью шагов Жордана–Гаусса найдем первоначальный опорный план, т.е. преобразуем таблицу так, чтобы система уравнений была приведена к базисному виду с неотрицательными свободными членами. При этом функция цели должна быть выражена через свободные неизвестные. Не нарушая общности, можно считать, что базисными переменными являются , тогда симплекс-таблица примет вид:

БП

x1

x2

xm

xm+1

xs

xn

Свободный   

 член

x1

1

0

0

a′1,m+1

a′1,s

a′1,n

b′1

x2

0

1

0

a′2,m+1

a′2,s

a′2,n

b′2

xm

0

0

1

a′m,m+1

a′m,s

a′m,n

b′m

Z

0

0

0

r1

rs

rn–m

q

Коэффициенты при

базисных неизвестных

Вектор r коэффициентов

при свободных неизвестных

В данной таблице , .

Полагая свободные неизвестные , получаем из таблицы неотрицательное базисное решение (опорный план)

.

  1.  Анализируем строку коэффициентов при свободных неизвестных, т.е. вектор в Z-строке.

Если , то соответствующее опорное решение является оптимальным, .

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

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

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

Если среди коэффициентов есть хотя бы один положительный, то s-столбец выбираем разрешающим и переходим к п. 5.

5. Для выбора разрешающей строки составляем неотрицательные отношения

и выбираем среди них наименьшее:

.

Таким образом, определилась разрешающая k-я строка и разрешающий элемент .

6. Выполняем шаг преобразований Жордана–Гаусса с разрешающим элементом и переходим к п. 3.

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

Пункт 5 нуждается в дополнительном пояснении.

6.2.2. Выбор разрешающей строки

в симплексных преобразованиях

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

Пусть при решении ЗЛП получена таблица:

БП

x1

x2

xm

xm+1

xs

xn

Свобод-

ный

  член

,

x1

1

0

0

a′1,m+1

a′1,s

a′1,n

b′1

x2

0

1

0

a′2,m+1

a′2,s

a′2,n

b′2

xm

0

0

1

a′m,m+1

a′m,s

a′m,n

b′m

Z

0

0

0

r1

rs

rn–m

q

в которой все , , т.е. найден опорный план:

.

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

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

Как было указано, за разрешающую строку принимают k-ю строку, для которой выполняется условие

.

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

Действительно, согласно правилам преобразований Жордана–Гаусса имеем:

a) для разрешающей строки () очевидно:

, так как

б) для остальных строк () имеем

.

В самом деле,

и ,   так как .

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

Пусть в последней симплекс-таблице получен оптимальный план Х*. Если среди неотрицательных компонент вектора при этом имеется хотя бы одна нулевая компонента , то введение переменной в базис не изменит величины функции цели Z Действительно, выполнив шаг преобразований Жордана–Гаусса с разрешающим элементом получим новое опорное решение, для которого

БП

Свободный

член

a kp

Следовательно, новое опорное решение является новым оптимальным решением. Обозначим эти оптимальные планы соответственно Х*1 и Х*2. Тогда согласно свойствам допустимых планов задача имеет бесконечно много решений и оптимальный план является выпуклой линейной комбинацией оптимальных планов Х*1 и Х*2, т. е.

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

Если нулевых компонент окажется несколько, то введением в базис каждой из соответствующих переменных можно найти несколько оптимальных планов и т.д. Согласно теореме 5.3 общее оптимальное решение при наличии k оптимальных опорных решений имеет вид:

где  

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

6.2.4. Признак неограниченности целевой функции

Как следует из геометрической интерпретации ЗЛП, возможны случаи, когда функция цели Z при решении задачи на минимум не ограничена снизу. Этот случай легко выявить при решении задачи симплекс-методом.

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

Пусть система ограничений ЗЛП приведена к базисному виду:

где   ,

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

причем

.

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

где    ;   q – константа.

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

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

 так как

Таким образом, ни одна из переменных не выйдет из базиса (не будет равна нулю).

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

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

6.3. Понятие о вырождении

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

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

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

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

Примеры решения задач симплекс-методом

Пример 6.2. Фирма выпускает изделия четырех типов. При этом используется сырье двух видов, запасы которого соответственно 1200 и 1000 единиц. Нормы расхода сырья на изготовление каждого типа продукции, а также доход, полученный от выпуска единицы каждого типа продукции, заданы таблицей:

Сырье

Нормы расхода

Объем

ресурсов

I

II

III

IV

1

4

2

1

4

1200

2

1

5

3

1

1000

Доход

15

5

3

20

  

Составить план производства, обеспечивающий фирме наибольший суммарный доход.

Решение. Обозначим через план выпуска продукции. Математическая модель задачи примет вид:

.

Преобразуем ее к каноническому виду. Введем две дополнительные (балансовые) неотрицательные переменные х5 и х6 и перейдем к функции  Z1= – Z. Модель примет вид:

.

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

  1. Запишем условия задачи в виде симплексной таблицы:

БП

Переменные

Свободный

член

х1

х2

х3

х4

х5

х6

х5

4

2

1

1

0

1200

х6

1

5

3

1

0

1

1000

Z1

–15

–5

–3

–20

0

0

0

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

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

.

Все компоненты вектора r отрицательны, следовательно, первоначальный опорный план не является оптимальным.

  1. Выберем максимальную по модулю отрицательную компоненту вектора r:

.

Ей соответствует четвертый столбец таблицы. Анализируем коэффициенты  вектора-столбца коэффициентов при х4. Они положительны: а14=4, а24=1. Есть возможность перейти к новому опорному плану, выведя из свободных переменных х4.

Выбираем четвертый столбец за разрешающий и переходим к п. 4.

  1. Для выбора разрешающей строки составляем неотрицательные отношения

и выбираем среди них минимальное:

.

Разрешающей строкой будет первая, разрешающим элементом элемент  а14 = 4.

  1. Выполняя симплексное преобразование с разрешающим  элементом а14=4, придем к новой таблице:

БП

Переменные

Свободный член

х1

х2

х3

х4

х5

х6

x4

1

1/2

1/4

1

1/4

0

300

х6

0

9/2

11/4

0

1/4

1

700

Z1

5

5

2

0

5

0

6000

Таблица содержит новый опорный план:

.

Видим, что все компоненты вектора r=(5, 5, 2, 5) положительные, следовательно, этот опорный план является оптимальным, при этом  Z1 min= 6000.

Обратимся к исходной модели. В ней содержится 4 ограничения и целевая функция  Z=  Z1. Оптимальным решением исходной задачи будет:

,

при этом                                   Z max=6000.

Пример 6.3. Решить симплекс-методом задачу:

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

и дать геометрическую интерпретацию процесса решения.

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

Z1= – Z.

Тогда                

В системе ограничений уже выделены базисные переменные х3 , х4 и х5. Теперь все исходные данные поместим в таблицу:

БП

Переменные

Свободный

член

1

1

0

0

5

2

1

0

1

0

9

1

2

0

0

1

7

–2

–1

1

–1

1

0

В клетку на пересечении Z1-строки и столбца “Свободный член” запишем свободный член целевой функции с противоположным знаком. В данном случае он равен 0.

Приравняв свободные переменные нулю х12=0, получим  базисное решение системы ограничений:  

где    х3=5,   х4=9,   х5=7.

Так как то базисное решение Х1 является опорным решением (планом) задачи. Итак, первоначальное опорное решение найдено.

Для проверки его на оптимальность выразим функцию цели Z1 через свободные переменные х1 и х2. Для исключения переменной х3 из функции цели Z возьмем за разрешающий элемент а13=1 в третьем столбце предыдущей таблицы. Сделав один шаг преобразований ЖорданаГаусса, придем к таблице вида:

БП

Переменные

Свободный

член

1

1

1

0

0

5

2

1

0

1

0

9

1

2

0

0

1

7

–3

–2

0

–1

1

–5

Сделав аналогично еще два шага исключения неизвестных х4 и х5 из функции цели Z1, придем к таблице:

БП

Переменные

Свободный

член

x2

1

1

1

0

0

5

2

1

0

1

0

9

x5

1

0

0

0

7

2

3

0

0

0

3

Из таблицы видно, что

Z1(Х(1))=3,  r =(2; 3).

Так как условие не выполняется, то полученный опорный план Х(1) не является оптимальным.

Необходимо перейти к новому опорному плану, для которого значение функции уменьшится. Для перехода к следующему опорному плану нужно одну из свободных переменных (х1 либо х2) перевести в базис, а одну из базисных (х3, либо х4, либо х5) перевести в свободные. Выбор свободной переменной, вводимой в базис, определяется максимальной по модулю отрицательной компонентой вектора  r= (–2; –3). 

Компоненте  r2= –3 соответствует в таблице переменная х2, которая вводится в базис, и второй столбец становится разрешающим.

Для выбора разрешающей строки вычислим

.

Итак, третья строка стала разрешающей, а разрешающим элементом стал элемент  а32=2. Сделав один шаг в симплекс-таблице, получим новое опорное решение:

.

Это решение также не является оптимальным, так как в вектор           r =(–1/2; 3/2) имеет отрицательную компоненту:

БП

Переменные

Свободный член

x1

x3

0

1

0

–1/2

3/2

3/2

0

0

1

–1/2

11/2

1/2

1

0

0

1/2

7/2

–1/2

0

0

0

3/2

15/2

Значение же функции цели Z1 уменьшилось от значения      Z1 = 3 до значения Z1 = –15/2. (Напомним, что значение функции цели из таблицы берется с противоположным знаком.)

Очевидно, что на следующем шаге необходимо в базис ввести переменную х1, соответствующую отрицательной компоненте r1 = –1/2. И первый столбец в последней таблице становится разрешающим. Для выбора разрешающей строки найдем:

Минимальное из отношений соответствует первой строке. Сделав один шаг симплексных преобразований с разрешающим элементом  а11=1/2, получим  таблицу:

БП

Переменные

Свободный

член

1

0

2

0

–1

3

0

0

–3

1

–2

1

0

1

–1

0

1

2

0

0

1

0

1

9

Из таблицы следует, что полученный опорный план:

является единственным оптимальным планом задачи, так как =(1; 1)>0. При этом значение функции уменьшилось:

.

Итак, решением исходной задачи является:

а  Z max = –Z1min=9.

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

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

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

Выразим из системы ограничений базисные переменные через свободные:

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

.

Стандартная форма модели примет вид

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

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

Геометрическая интерпретация симплекс-метода

Исходный опорный план

соответствует точке  О (0,0) ОДР.

После одного шага симплекс-метода (одной итерации) был получен новый опорный план

,

которому соответствует точка А ().

На рисунке переход от одного опорного плана (вершины) к другому опорному плану происходит по ребру ОА.

После второй итерации получен план

,

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

Пример 6.4. Решить симплекс-методом ЗЛП:

Решение. Особенностью данной задачи является то, что система ограничений не приведена к базисному виду, нет разграничения переменных на базисные и свободные (есть только одна базисная переменная х4). Поэтому прежде всего с помощью преобразований Жордана–Гаусса приведем систему к базисному виду. Для этого коэффициенты системы ограничений и целевой функции Z1= –Z занесем  в таблицу:

БП

Переменные

Свободный

член

1

1

1

1

2

–1

–1

0

0

1

1

2

0

1

–2

–1

0

–1

0

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

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

Имеем      

т.е. за разрешающую строку примем вторую, а за разрешающий элемент а21=1. Выполнив шаг преобразований Жордана–Гаусса, придем к таблице:

БП

Переменные

Свободный член

0

2

2

1

2

1

–1

–1

0

0

0

3

0

1

0

–3

–2

–1

0

Система, записанная в данной таблице, разрешена относительно х1 и х4, но так как она содержит три уравнения, то необходимо ввести в базис еще одну переменную (х2 или х3) и при этом иметь в качестве разрешающей третью строку. Посмотрим, какой столбец с этой точки зрения следует брать за разрешающий. Если возьмем второй столбец, то за разрешающую строку следует выбрать третью (благоприятный случай):

Если же возьмем третий столбец, то за разрешающую строку также следует выбрать третью:

следовательно, можно выбрать любой из них. Выберем, например, второй столбец и, выполнив шаг преобразований Жордана–Гаусса с разрешающим элементом а32 = 2, придем к таблице:

БП

Переменные

Cвободный

член

член

х1

х2

х3

х4

х4

0

0

–1

1

1

х1

1

0

1/2

0

1/2

х2

0

1

3/2

0

1/2

Z1

0

0

5/2

–1

3/2

Теперь система приведена к базисному виду, базисными переменными являются х12, х4, свободной – х3. Все свободные члены положительны, поэтому можем записать первоначальный опорный план:

Чтобы ответить, является ли он оптимальным, необходимо выполнить еще один шаг преобразований с разрешающим элементом а14 = 1, чтобы выразить целевую функцию Z1 только через свободную переменную х3. Получим новую таблицу:

БП

Переменные

Cвобод-ный член

член

х1

х2

х3

х4

х4

0

0

–1

1

1

х1

1

0

1/2

0

1/2

х2

0

1

3/2

0

1/2

Z1

0

0

3/2

0

5/2

Опорное решение

содержащееся в таблице, является оптимальным, так как вектор         r = (3/2) содержит одну положительную компоненту. Минимальное значение целевой функции:

и,  очевидно,   .

Итак,   .

6.4. Вопросы для самопроверки

  1. В чем заключается идея симплекс-метода?
  2. В каком виде должна  быть  записана модель  ЗЛП для  решения симплекс-методом?
  3. Как построить первое базисное решение? В каком случае оно будет опорным решением ЗЛП?
  4. Из каких этапов состоит переход от одного опорного решения к другому?
  5. Как определить, какой из столбцов выбирается за разрешающий в симплекс-преобразованиях?
  6. Каким образом сохраняется неотрицательность переменных нового базисного решения?
  7. Что является критерием оптимальности решения ЗЛП в симплекс-методе?
  8. Как определяется текущее значение целевой функции из таблицы?

6.5. Индивидуальное задание

Задание

  1. Составить математическую модель задачи, дав экономическую интерпретацию переменным, функции цели и системе ограничений.
  2. Записать модель в стандартной и канонической формах.
  3. Записать каноническую модель в матричной форме, записать матрицу А, векторы b, с.
  4. Решить задачу симплекс-методом. В процессе решения дать экономическую интерпретацию каждого шага.
  5. Решить задачу с использованием компьютера, сопроводив решение анализом полученного результата.

Варианты

1. Из труб длиной 25 м требуется нарезать трубы длиной 8, 12 и 16 м в количестве 100, 50 и 30 соответственно. Определить план раскроя с минимальными отходами, изрезав не более 80 труб.

2. Полосы материала длиной 3 м  кроятся на детали длиной 1,6; 1; 0,8 м, которые входят в комплект в количестве 2, 1 и 4 штуки соответственно. Определить план раскроя с минимальными расходами, если в наличии 60 полос материала и требуется соблюсти комплектность.

3. Cоставить смесь с заданными характеристиками: содержание вещества В1 – не менее 41,2 %, вещества В2 – от 45 до 60 %. Используется два вида сырья, процентное содержание  веществ В1 и В2 в которых задано таблицей:

Вещество

Сырье

В1

В2

Прочие

I

52

25

23

II

16

75

9

При составлении смеси можно использовать также вещество В1 в чистом виде. Стоимость 1 т сырья I вида составляет 3 у.е., сырья II вида – 6 у.е., вещества В1 – 5 у.е. Требуется получить 1 т смеси минимальной стоимости.

4. В сплав должно входить не менее 4 % никеля  и не более 80 % железа. Для составления сплава используют 3 вида сырья, содержащего никель, железо и прочие вещества. Кроме того, в сплав могут добавляться в чистом виде  никель, железо и прочие вещества. Стоимость сырья и процентное содержание в нем компонентов сплава представлены в таблице:

Компоненты сплава

Виды сырья

1

2

3

Ni

Fe

Прочие

Ni

70

90

85

100

Fe

5

2

7

100

Прочие

25

8

8

100

Стоимость 1 кг

6

4

5

25

67

2

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

5. Из 100 труб длиной 20 м требуется получить максимальное количество комплектов, в каждый из которых входят 4 трубы длиной 9 м, 5 труб по 8 м и 3 трубы по 7 м.

6. Для изготовления брусьев трех размеров (0,6; 1,5 и 2,5 м в соотношении 2:1:3) на распил поступают бревна длиной 3 м. Определить план распила, обеспечивающий максимальное число комплектов.

7. Произвести распил 5-метровых бревен на брусья размерами 1,5; 2,4; и 3,2 м в отношении 5:4:2 так, чтобы минимизировать общую величину отходов.

8. На складе имеются доски длиной 4 м. Требуется получить 40 комплектов деталей, в каждый из которых входит 2 детали по 1,8 м, 3 детали по 1,4 м и 1 деталь длиной 1 м. Составить план раскроя с минимумом отходов. Сколько досок потребуется?

9. Двум погрузчикам разной мощности за 24 ч нужно погрузить на первой площадке 230 т, на второй – 168 т. Первый погрузчик на первой площадке может погрузить 10 т/ч, на второй – 12, второй на каждой площадке может погрузить по 13 т/ч. Стоимость работ, связанных с погрузкой 1 т первым погрузчиком на первой площадке, составляет 8 у.е., на второй 7 у.е., вторым погрузчиком на первой площадке 12 у.е., на второй 13 у.е.

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

10. Предприятие имеет две машины, каждая из которых может произвести любое из 2-х видов изделий: А и В. Время на производство одного изделия на каждой машине, а также ресурс времени каждой машины заданы в таблице:

Продукция

Оборудование

Затраты времени на 1 изделие

Фонд

времени

А

В

1

1

2

130 мин

2

2

1

60 мин

Задан план производства: 50 изделий А и 70 изделий В. Требуется так распределить загрузку машин, чтобы при условии строгого выполнения плана время, затрачиваемое машинами на его выполнение, было минимально.

Указание: максимизировать время, не использованное при производстве (остается после выполнения плана).

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

Вид товара

Вид ресурсов

1

2

3

4

Объем

ресурсов

Сырье, кг

3

5

2

4

60

Рабочая сила, чел.-ч

22

14

18

30

400

Оборудование, станко-ч

10

14

8

16

128

Прибыль на единицу товара, у.е.

30

25

56

48

Определить оптимальный ассортимент продукции при дополнительном условии: 1-го товара выпустить не более 5 единиц, 2-го – не менее 8 единиц, а 3-го и 4-го – в отношении 1: 2.

12. Требуется произвести 300 тыс. т продукции. Существует четыре варианта ее выпуска. Себестоимость производства и удельные капитальные вложения по каждому варианту заданы таблицей:

Вариант

I

II

III

IV

Удельные кап. вложения, р./т

120

80

50

40

Себестоимость, р./т

83

89

95

98

Определить интенсивность использования вариантов из условия минимума себестоимости, если задан лимит капитальных вложений в объеме 18 млн р.

13. Из листового проката определенной формы необходимо вырезать некоторое количество заготовок  типов А и В для производства 90 штук изделий. Для одного изделия требуется 2 заготовки типа А и 10 заготовок типа В. Возможны 4 варианта раскроя одного листа проката. Количество заготовок А и В, вырезаемых из одного листа при каждом варианте раскроя, и отходы от раскроя указаны в таблице.

Вариант раскроя

Заготовка А, шт.

Заготовка В, шт.

Отходы от

раскроя, ед.

I

4

0

12

II

3

3

5

III

1

9

3

IV

0

12

0

Какое количество листов проката нужно раскроить каждым вариантом, чтобы отходы от раскроя были наименьшими?

14. На приобретение оборудования для нового производственного участка выделено 20 тыс. у. е. Оборудование должно быть размещено на площади, не превышающей 72 м2. Предприятие может заказать оборудование двух видов: более мощные машины типа А стоимостью 5 тыс. у. е., занимающие производственную площадь 6 м2 (с учетом проходов) и дающие 8 тыс. единиц продукции за смену, и менее мощные машины типа Б стоимостью 2 тыс. у. е., занимающие площадь 12 м2 и дающие за смену 3 тыс. единиц продукции. Найти оптимальный вариант приобретения оборудования, обеспечивающий максимум общей производительности нового участка.

15. Требуется составить смесь, содержащую три химических вещества – А, В и С. Известно, что составленная смесь должна содержать вещества А не менее 6 единиц, вещества В не менее 8 единиц, вещества С не менее 12 единиц. Вещества А, В и С содержатся в трех видах продуктов – I, II, III в концентрации, указанной в таблице:

Продукты

Химические вещества

I

II

III

А

2

1

3

В

1

2

1,5

С

3

4

2

Стоимость единицы продуктов I, II, III различна: единица продукта I стоит 2 у.е., единица II – 3 у.е., единица III – 2,5 у.е. Смесь надо составить так, чтобы стоимость используемых продуктов была наименьшей.

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

Тип

поезда

Тип вагона

Багажный

Почтовый

Ж. плацк.

Купейный

Мягкий

Скорый

1

1

5

6

3

Пассажирский

1

8

4

1

Число

пассажиров

58

40

32

Парк вагонов

12

8

81

70

26

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

17. Предприятие может работать по пяти технологическим процессам, причем количество единиц выпускаемой продукции по разным технологическим процессам за 1 единицу времени соответственно равно 300, 260, 320, 400 и 450 шт. В процессе производства учитываются следующие производственные факторы: сырье, электроэнергия, зарплата и накладные расходы.

Затраты соответствующих факторов в у.е. при работе по разным технологическим процессам в течение 1 единицы времени показаны в таблице:

Тех. процесс

Произв. факторы

1

2

3

4

5

Объем

ресурсов

Сырье

12

15

10

12

11

1300

Электроэнергия

0,2

0,1

0,2

0,25

0,8

30

Зарплата

3

4

5

4

2

400

Накладные расходы

6

5

4

6

4

800

Найти программу максимального выпуска продукции.

18. Имеется три вида ресурсов: I, II и III, которые используются для производства трех видов продукции: А, Б и В. Нормы расхода ресурсов на единицу продукции каждого вида приведены в таблице:

Ресурс

Норма расхода на единицу продукции

А

В

С

I

1

2

0

II

2

1

0

III

0

1

1

В распоряжении предприятия находятся 500 единиц ресурса I, 550 единиц ресурса II и 200 единиц ресурса III. Прибыль от реализации единицы продукции А составляет 3 у. е., продукции Б –  4 у.е., продукции В – 1 у.е. Определить оптимальный план производства продукции по критерию максимума прибыли.

19. Мебельная фабрика выпускает столы, стулья, бюро и книжные шкафы. При изготовлении этих товаров используется два различных типа досок, причем фабрика имеет в наличии 1500 м3 досок I типа и 1000 м3 II типа. Кроме того, заданы трудовые ресурсы в количестве 300 чел.-ч.

В таблице приведены нормативы затрат каждого из видов ресурсов на изготовление 1 единицы изделия и прибыль на 1 единицу изделия:

Ресурсы

Затраты на 1 единицу изделия

Столы

Стулья

Бюро

Кн. шкафы

Доски I типа, м3

5

1

9

12

Доски II типа, м3

2

3

4

1

Трудовые ресурсы, чел.-ч

3

2

5

10

Прибыль, р./шт.

12

5

15

10

Определить оптимальный ассортимент, максимизирующий прибыль, если отношение количества столов к количеству стульев равно 1:6.

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

Виды

ресурсов

Объем

ресурсов

Производительность и норма расхода

1

2

3

Станки I типа

30

20

10

25

Станки II типа

45

8

20

10

Пряжа

30

120

180

210

Красители

1

10

5

8

Цена

15

15

20

Определить оптимальный ассортимент, максимизирующий прибыль, если себестоимость 1 м ткани составляет соответственно 3, 5 и 15 у.е.

21. Кирпичный завод выпускает кирпичи двух марок (I и II). Для производства кирпича применяется глина трех видов (A, B, C). По месячному плану завод должен выпустить 10 условных единиц кирпича марки I и 15 условных единиц кирпича марки II. В таблице указаны расход различных видов глины для производства одной условной  единицы кирпича каждой марки и месячный запас глины:

Марка

Количество глины, необходимой

для производства 1 условной единицы кирпича

А

В

С

I

1

0

1

II

0

2

2

Запас

глины

15

36

47

Сколько условных единиц кирпича различных марок должен выпустить завод сверх плана, чтобы обеспечить наибольшую прибыль, если известно, что от реализации 1 условной единицы кирпича марки I завод получает прибыль, равную 4 у.е., а от реализации кирпича марки II – 7 у.е.?

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

Тип домов

Тип квартир

Д-1

Д-2

Д-3

Д-4

Однокомнатные

10

18

20

15

Двухкомнатные:

смежные

40

20

несмежные

20

60

Трехкомнатные

60

90

10

Четырехкомнатные

20

10

5

Плановая

себестоимость, у.е.

830

835

360

450

Годовой план ввода жилой площади составляет соответственно 800, 1000, 900, 2000 и 700 квартир указанных типов. Исходя из необходимости выполнения плана (возможно его перевыполнение по всем показателям), сформулировать задачу минимизации объема капиталовложений в жилищное строительство на плановый год.

23. В пунктах А и В расположены кирпичные заводы, а в пунктах С и Д – карьеры, снабжающие их песком. Потребность заводов в песке не больше производительности карьеров. Известно, сколько песка нужно каждому из заводов и сколько его добывают в каждом из карьеров. Кроме того, известна стоимость перевозки 1 т песка из каждого карьера к заводам. Нужно так спланировать снабжение заводов песком, чтобы суммарные затраты были наименьшими. Данные приведены на рисунке:

А+

А+

В+

С

40

Д

50

70

50

2

6

5

3

24. Полосы листового проката длиной 200 см необходимо разрезать на заготовки трех типов (А, В, С) длиной соответственно 57, 81 и 101 см для производства 50 изделий. На каждое изделие требуется по четыре заготовки А и В и по пять заготовок типа С.

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

6.6. Задачи для самостоятельной работы

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

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

Датчики

Самописцы

20

40

50

40

70

2

1

5

3

90

3

2

3

4

60

3

4

1

2

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

2. Четыре растворных узла строительного управления потребляют в сутки 170, 175, 220, 190 т песка, который производят три фабрики. Их суточная производительность соответственно 280, 240 и 235 т. В таблице приведена стоимость перевозки 1 т песка от каждой фабрики к каждому узлу, цена 1 т песка:

Фабрика

Узел

1

2

3

1

0,9

1,5

0,6

2

1,0

0,8

0,9

3

0,7

0,4

1,2

4

0,5

1,0

1,3

Цена 1 т песка, у.е.

3,0

2,9

2,2

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

3. Строительной организации необходимо выполнить четыре вида земляных работ, объем которых составляет соответственно 7000, 6500, 7600, 8100 м3. Для их осуществления предполагается использовать три механизма. Производительность механизмов и себестоимость 1 ч работы каждого из них приведены в таблице:

Показатели

Механизмы и виды работ

I механизм

II механизм

III механизм

1

2

3

4

1

2

3

4

1

2

3

4

Производительность механизма по виду работы, м3

20

15

16

30

14

18

35

32

15

29

40

15

Себестоимость 1 ч работы механизма по виду работы, у.е.

2

5

3

6

2

4

5

7

8

3

6

3

Определить оптимальный план организации работ с минимальными затратами на его осуществление.

4. Имеется пять видов сырья и пять различных предприятий, перерабатывающих это сырье. Задана матрица:

,

где характеризует прибыль, получаемую j-м предприятием при переработке i-го вида сырья.

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

5. Предложить модель построения оптимального плана мероприятий НОТ участка, если в него намечено включить не менее пяти работ из следующего перечня:

Наименование работ

Ожидаемый

эффект, у.е.

Затраты, у.е.

Проектирование рациональных трудовых ресурсов

12,0

7,0

Оптимизация норм численности обслуживающего персонала

8,0

2,0

Совмещение профессий станочников

4,0

2,0

Дополнительное обучение станочников

2,0

1,0

Введение регламентированных перерывов

3,0

0,8

Введение функциональной музыки

7,0

6,0

Создание сквозных бригад

9,0

5,0

Введение централизованной заточки инструментов

11,0

9,0

Повышение освещенности на рабочих местах

1,0

0,7

Учесть при этом, что на осуществление мероприятий НОТ отпущено 18 у.е.

7. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ

ПРОГРАММИРОВАНИИ

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

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

программирования

В качестве примера двойственных задач рассмотрим следующую задачу.

Пример 7.1. Фирма выпускает продукцию A, B, C, D, используя для ее производства три вида ресурсов в количестве соответственно 260, 400, 240 единиц. Расход каждого ресурса на единицу выпускаемой продукции и цена единицы каждого вида продукции заданы таблицей:

Вид

ресурса

Объем ресурса

Нормы расхода ресурсов

A

B

C

D

1

260

2

1

3

1

2

400

1

2

1

2

3

240

2

0

1

2

Цена, у.е.

1

4

2

5

 

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

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

Поставим в соответствие первому ресурсу оценку y1, второму – y2, третьему – y3. Тогда общая оценка ресурса, используемого на производство продукции, составит:

.

Цель задачи – минимизировать эту величину.

Суммарная оценка ресурса, необходимого для производства единицы продукции А, равна

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

.

Из аналогичных соображений получаем:

Естественно предположить, что оценки y1, y2, y3 неотрицательны, т.е.  

Итак, получаем математическую модель задачи:

       

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

Компоненты оптимального плана называют оптимальными оценками ресурсов. Это оценки ресурсов в условиях конкретной задачи. Одни и те же ресурсы для разных предприятий представляют различную ценность. Изменение запасов ресурсов приводит к необходимости их переоценки. Следуя Л.В. Канторовичу, будем называть их объективно обусловленными оценками.

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

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

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

при ограничениях-неравенствах:

при ограничениях-равенствах:

при неотрицательных переменных:

при свободных переменных:

хj 0        (j = t +1,…,n).  

Двойственной к данной прямой (исходной) задаче называют задачу:

при неотрицательных переменных:

при свободных переменных:

  

при ограничениях-неравенствах:

при ограничениях-равенствах:

т.е. задачу, получаемую из исходной по следующим правилам:

1. Количество переменных двойственной задачи равно m – числу ограничений исходной задачи, а число ограничений двойственной задачи равно n – количеству переменных исходной задачи.

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

3. Матрицей коэффициентов системы ограничений двойственной задачи служит матрица AT, получаемая транспонированием матрицы А коэффициентов системы ограничений исходной задачи.

4. Каждому ограничению-неравенству:

исходной задачи соответствует неотрицательная переменная:

двойственной задачи, а каждому ограничению-равенству:

соответствует свободная переменная:

yi0           

двойственной задачи.

5. Каждой неотрицательной переменной прямой задачи соответствует ограничение-неравенство:

двойственной задачи с тем же знаком неравенства, а каждой свободной переменной хj0 соответствует ограничение-равенство:

двойственной задачи.

6. Максимизация целевой функции исходной задачи заменяется минимизацией целевой функции двойственной задачи.

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

Исходная задача

Двойственная задача

   

 

yi 0 

 

 

xj 0  

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

7.3. Симметричные двойственные задачи

Пусть модель исходной ЗЛП задана в стандартной форме:

  (7.1)

Составим модель двойственной ЗЛП, используя правила, изложенные в п. 7.2.

Модель двойственной задачи примет вид:

  (7.2)

Если ввести в рассмотрение матрицы:

  

,

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

Прямая задача

Двойственная задача

Пример 7.2. Составить двойственную задачу к следующей ЗЛП:

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

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

Преобразуем третье ограничение, умножив обе части неравенства на –1 и изменив знак неравенства на противоположный:

В результате исходная задача примет вид:

                                 (7.3)

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

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

.

Правыми частями системы ограничений двойственной задачи станут коэффициенты (1, 2, –3, 1) целевой функции исходной задачи.

Каждой неотрицательной переменной исходной задачи соответствует ограничение-неравенство того же смысла:

Свободной переменной х4 соответствует ограничение-равенство:

х4 0    у1 у2=1.

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

Итак, математическая модель двойственной задачи примет вид:

     (7.4)

Далее покажем взаимосопряженность полученной пары двойственных задач, т.е. покажем, что задача, двойственная к (7.4), совпадает с исходной (7.3).

Для этого прежде всего преобразуем модель (7.4) к виду:

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

Умножив обе части первых двух ограничений на –1 и введя функцию Z= –Z1, получим эквивалентную ЗЛП:

которая совпадает с исходной.

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

Пример 7.3. Для задачи:

составить двойственную и найти решение обеих задач.

Решение. Двойственной является задача:

 

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

Рис. 7.1. достигается в точке B

Рис. 7.2. достигается в точке Е

Как видно из рис. 7.1, максимальное значение целевая функция исходной задачи принимает в точке В. Следовательно, Х*=(3,7) является оптимальным планом, при котором Zmax=48.

В двойственной задаче (рис 7.2) ОДР не ограничена. Минимальное значение целевая функция двойственной задачи принимает в точке Е, т.е.   и Таким образом, значения целевых функций исходной и двойственной задач при их оптимальных планах равны между собой.

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

7.4. Основные теоремы двойственности

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

Итак, пусть имеем пару двойственных задач:

Прямая задача

Двойственная задача

 ,

                    (7.5)

 .

.

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

Существование зависимости между решениями прямой и двойственной задач характеризуется сформулированными ниже леммами и теоремами двойственности.

Лемма 7.1. Для любых допустимых планов Х и Y пары двойственных ЗЛП справедливо соотношение:

        (7.6)

Так как Х и Y– допустимые планы, то

отсюда

.

Аналогично из того, что следует:

Таким образом, имеем:

что и требовалось доказать.

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

Неравенство называют основным неравенством в теории двойственности. Его экономический смысл, например, для производственной задачи выпуска продукции, заключается в том, что при любом допустимом плане производства Х общая стоимость продукции Z(X) не больше суммарной оценки ресурсов W(Y), отвечающей любому допустимому вектору оценок Y.

Лемма 7.2. Если для некоторых допустимых планов Х* и Y* пары двойственных задач выполняется условие:

                       (7.7)

то Х* и Y* являются оптимальными планами соответствующей пары двойственных задач.

Пусть Х* и Y*– допустимые планы пары двойственных задач (7.5). Необходимо доказать, что если для них выполняется условие (7.7), то эти планы оптимальны. (Напомним, что план Х* будет оптимальным тогда и только тогда, когда для любого допустимого плана Х прямой задачи.)

Рассмотрим произвольный допустимый план Х прямой задачи. Тогда в соответствии с леммой 1 и условием (7.7) имеем:

откуда , т.е. Х*– оптимальный план прямой задачи.

Аналогично доказывается оптимальность плана Y*. Лемма 2 является критерием оптимальности для пары двойственных ЗЛП. Согласно этой лемме, если среди допустимых планов пары двойственных задач найдутся планы Х* и Y*, для которых   

то Х* и Y*– оптимальные планы пары двойственных задач.

Пример 7.4. Для пары двойственных задач:

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

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

Первая теорема двойственности

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

.

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

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

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

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

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

Пример 7.5. Имеем пару двойственных задач:

Прямая задача

Двойственная задача

Допустимое решение

Допустимое решение

.

Значение

Значение

Z=3·3+5·1=14.

W=5·+2·0=16.

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

.                            (7.8)

Следует помнить, что здесь приведены допустимые решения, найденные методом проб. А лемма утверждает, что условие (7.8) справедливо для любых соответствующих допустимых решений Х и Y пары двойственных задач.

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

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

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

.

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

С помощью геометрической интерпретации пары двойственных задач проиллюстрируем первую теорему двойственности. Вернемся к примеру 7.5. Как видно из рис. 7.3, прямая задача имеет оптимальное решение, которое достигается в точке А. Следовательно, Х*=(5,0)Т является оптимальным планом прямой задачи, при котором  Zmax=15. По первой теореме двойственности тогда и двойственная задача разрешима, а экстремальные значения целевых функций должны быть одинаковы. Действительно, минимальное значение функция цели двойственной задачи принимает в точке В (рис. 7.4). Значит, Y*=(3,0) и Wmin=15.

Рис. 7.3. Оптимальное решение прямой задачи

достигается в точке А

Рис. 7.4. Оптимальное решение двойственной задачи

достигается в точке В

Кроме того, из рис. 7.3 и 7.4 легко увидеть, что значение целевой функции Z прямой задачи при любом допустимом плане не больше 15, а значение функции цели W двойственной задачи при произвольном ее допустимом плане не меньше 15.

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

Прямая задача

Двойственная задача

Рис. 7.5. Целевая функция прямой задачи не ограничена

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

Рис. 7.6. Система ограничений двойственной задачи

противоречива

Вторая теорема двойственности

Для того чтобы планы Х* и У* пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:

Условия 1 и 2 называются условиями дополняющей нежесткости.

Необходимость. Пусть Х* и Y*– оптимальные планы пары двойственных задач (7.5). Как было показано при доказательстве леммы 1, для любых допустимых планов Х и Y выполняется соотношение:

      (7.9)

Следовательно, это соотношение справедливо и для оптимальных планов:

    (7.10)

На основании первой теоремы двойственности для оптимальных планов Х* и Y* справедливо условие:

,       (7.11)

и соотношение (7.10) превращается в равенство:

отсюда получаем условия дополняющей нежесткости.

Достаточность. Пусть для некоторых допустимых планов  Х* и Y* выполняются условия дополняющей нежесткости. Тогда из первого условия имеем:

а из второго:

Таким образом получаем:

,

и согласно лемме 2  Х* и Y* – оптимальные планы пары двойственных задач, что и требовалось доказать.

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

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

(7.12)

(7.13)

Из этих условий следует:

1. Если какое-либо (i-е) ограничение прямой задачи в ее оптимальном плане Х* обращается в строгое неравенство, то соответствующая (i-я) компонента уi* оптимального плана Y* двойственной задачи должна равняться нулю.

2. Если же какая-либо (j-я) компонента xj*оптимального плана Х* прямой задачи положительна, то соответствующее (j-е) ограничение в двойственной задаче ее оптимальным планом должно обратиться в равенство.

То есть:

Аналогично:

Дадим экономическую интерпретацию условиям дополняющей нежесткости.

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

Если какой-то i-й ресурс расходуется не полностью (избыточен), т.е.   

то его оценка равна нулю,

Отсюда следует, что оценки оптимального плана – это мера дефицитности ресурсов.

Согласно условию 2, если некоторый продукт j входит в оптимальный план производства (xj*>0), то при оптимальной системе оценок двойственной задачи затраты ресурсов на его изготовление совпадают со стоимостью этого продукта, т.е.

Если затраты ресурсов на выпуск какого-либо продукта j превышают его стоимость,

то этот продукт не производится, т.е. xj*=0.

Отсюда вывод:

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

Для иллюстрации применения второй теоремы двойственности при рассмотрении пары двойственных задач рассмотрим следующие примеры.

Пример 7.7. Кирпичный завод выпускает кирпичи двух марок (I и II). Для производства кирпича применяется глина трех видов (A, В, С). По месячному плану завод должен выпустить 10 у.е. кирпича марки I и 15 у.е. кирпича марки II. В таблице указаны расход различных видов глины для производства кирпича каждой марки и месячный запас глины:

Марка

Количество глины, необходимой для

производства 1 у.е. кирпича вида

А

В

С

I

1

0

1

II

0

2

2

Запас глины

15

36

47

Сколько у.е. кирпича различных марок должен выпустить завод сверх плана, чтобы обеспечить наибольшую прибыль, если известно, что от реализации 1 у.е. кирпича марки I завод получит прибыль, равную 4 у.е., а от реализации кирпича марки II – 7 у.е.?

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

Решение. Составим математическую модель задачи. Обозначим через х1 – количество единиц кирпича марки I, выпущенных сверх плана, а х2 – марки II. Тогда выпуск кирпича марки I составляет (10+х1) единиц, марки II – (15+х2) единиц, а прибыль, получаемая от реализации продукции, составит

Цель – максимизировать прибыль, следовательно,

На выпуск продукции будет израсходовано соответственно:

Учитывая запасы глины различных видов на заводе, получаем ограничения:

Из условия задачи следует, что

Итак, математическая модель исходной (прямой) задачи имеет вид:

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

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

Итак, чтобы получить максимальную прибыль, завод должен выпустить сверх плана 5 у.е. кирпича марки I и 1 у.е. кирпича марки II.

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

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

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

Согласно первой теореме двойственности

Далее, используя вторую теорему двойственности, найдем оптимальный план  Y*=(у1*, у2*, у3*) двойственной задачи, в котором  у1*, у2*, у3*являются оптимальными оценками ресурсов (глина видов А, В и С). Так как  х1*=5>0, то согласно второй теореме, ограничение в двойственной задаче ее оптимальным планом должно обратиться в равенство, т.е.   Аналогично из того, что , следует у2*+2у3*=7. Итак, имеем систему уравнений:

 

Кроме того, в оптимальном плане первое и третье ограничения прямой задачи выполняются как равенства  (5=5; 5+2·1=7). Это означает, что глина видов А и С используется полностью, являясь дефицитной. Дальнейшее увеличение запасов глины видов А и С целесообразно. Если же ресурс расходуется не  полностью, то он избыточен, его дальнейший рост не повлияет на эффективность работы завода. Таким ресурсом является глина вида В. Действительно, так как второе ограничение в оптимальном плане выполняется как строгое неравенство  1 < 3, то глина вида В избыточна, и согласно второй теореме двойственности ее оценка равна нулю (у2*=0).

Из системы находим

.

Получим

Тогда

,

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

Кроме того, замечаем, что глина вида С является более дефицитной, чем глина вида А, так как  

Пример 7.8. Провести анализ дефицитности ресурсов (пример 7.1), решив исходную задачу симплекс-методом.

Решение. Напомним математическую модель примера 7.1:

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

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

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

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

где x5, x6, x7 базисные переменные, а х1234=0 – свободные переменные. При этом Z(X)=0.

Замечаем, что полученный опорный план не является оптимальным, так как в функции цели Z, выраженной только через свободные переменные, все коэффициенты отрицательны. Причем для получения нового опорного плана в базис можно ввести любую из свободных неизвестных: х1, х2, х3 или х4.

Введем в базис х4. Следовательно, в симплекс-таблице (см. ниже) разрешающим становится четвертый столбец. Возникает вопрос, какая из базисных переменных х5, х6 или х7 перейдет в свободные, т.е. какая строка таблицы станет разрешающей. Используя правило выбора разрешающей строки, получим:

,

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

Симплекс-таблица решения данной задачи:

БП

x1

x2

x3

x4

x5

x6

x7

Свобод-ный член

x5

2

1

3

1

1

0

0

260

X1=(0, 0, 0, 0, 260, 400, 240)Т

x6

1

2

1

2

0

1

0

400

x7

2

0

1

0

0

1

240

Z1

–1

–4

–2

–5

0

0

0

0

x5

1

1

5/2

0

1

0

140

X2=(0, 0, 0, 120, 140, 160, 0)Т

x6

–1

0

0

0

1

–1

160

x4

1

0

1/2

1

0

0

1/2

120

Z1

4

–4

9/2

0

0

0

5/2

600

x5

0

0

1

60

x2

1

0

0

80

x4

0

1

0

120

Z1

2

0

9/2

0

0

2

1/2

920

Так как r>0, то задача имеет единственное оптимальное решение:

, а  

Двойственная задача имеет вид:

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

Согласно первой теореме двойственности имеем:

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

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

Следовательно, Второе и третье ограничения обращаются в равенства:

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

,

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

7.5. Анализ устойчивости двойственных оценок

Продолжим рассмотрение пары двойственных ЗЛП.

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

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

     (7.14)

Из теоремы об оценках вытекает, что при малом изменении правой части i-го ограничения в системе ограничений ЗЛП максимальное значение целевой функции изменяется на величину

В частности, при   имеем  

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

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

.      (7.15)

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

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

         (7.16)

  (7.17)

Здесь – элементы матрицы D=B–1, обратной к матрице В базиса оптимального плана, а j принимает значения индексов базисных переменных оптимального плана.

Пример 7.9. Для задачи оптимального использования ресурсов (см. пример 7.1), математическая модель которой имеет вид:

требуется:

  1. определить интервалы устойчивости двойственных оценок;
  2. установить величину максимальной стоимости продукции при изменении объема ресурсов: первого на – 40 единиц; второго – на +30 единиц, третьего – на 50 единиц. Оценить раздельное влияние этих изменений и суммарное их влияние на стоимость продукции;
  3. оценить целесообразность введения в план производства фирмы четвертого вида продукции, нормы затрат ресурсов на единицу которого соответственно равны 3, 2, 8, а цена составляет 9 у.е.;
  4. оценить целесообразность дополнительной закупки 100 единиц третьего ресурса по цене 0,25 у.е.

Решение  

1. Прежде всего перейдем к канонической форме модели, введя неотрицательные балансовые переменные x5, x6, x7:

Матрица системы ограничений:

.

Запишем последнюю симплекс-таблицу, дающую оптимальное решение исходной задачи:

БП

x1

x2

x3

x4

x5

x6

x7

Свободный

член

x5

3/2

0

5/2

0

1

–1/2

0

60

x2

–1/2

1

0

0

0

1/2

–1/2

80

x4

1

0

1/2

1

0

0

1/2

120

z

2

0

1/2

0

0

2

1/2

920

Как видно из таблицы, базисными переменными в оптимальном решении являются переменные x2, x4, x5; оптимальное решение:

.

Матрица коэффициентов при базисных переменных в первоначальной системе ограничений имеет вид:

,

тогда обратная матрица .

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

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

Ресурс 1.  Нижняя граница:

Верхняя граница: так как среди элементов первого столбца матрицы D нет отрицательных.

Итак,   т.е. первый ресурс может изменяться в интервале:

при этом оптимальный план двойственной задачи остается неизменным.

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

Ресурс 2.  Нижняя граница:  

Верхняя граница:   

Итак,

Получаем интервал устойчивости оценок по отношению ко второму ограничению:

Ресурс 3.  Нижняя граница:  

Верхняя граница:  

Интервал устойчивости оценок по отношению к третьему ограничению имеет вид:

  1. Далее оценим влияние изменения объема ресурсов

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

Раздельное влияние:  

, т.е.

уменьшение запаса первого ресурса на 40 единиц не приводит к изменению Zmax;

Совместное влияние изменений всех ресурсов приводит к изменению максимальной стоимости продукции Zmax на величину

Иными словами, мы нашли оптимальное значение целевой функции

для задачи:

3. Оценим целесообразность введения в план производства фирмы пятого вида продукции. Для этого определим, в каком отношении находятся цена c5=9 пятого вида продукции и суммарная оценка затрат ресурсов на производство одной единицы этой продукции:

Очевидно, . Так как цена продукции превышает затраты на ее производство, то введение в план производства пятого вида продукции нецелесообразно.

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

Затраты на приобретение 100 единиц третьего ресурса:

Таким образом, данное мероприятие является эффективным, оно обеспечивает дополнительную прибыль в объеме:

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

7.6. Вопросы для самопроверки

  1. Запишите математические модели пары двойственных ЗЛП.
  2. Дайте экономическую интерпретацию пары двойственных задач.
  3. Сформулируйте правила построения двойственной задачи к исходной.
  4. Сформулируйте первую теорему двойственности и дайте экономическую интерпретацию.
  5. Сформулируйте и дайте экономическую интерпретацию второй теоремы двойственности.
  6. Перечислите свойства двойственных оценок. В чем заключается их экономический смысл?

7.7. Индивидуальное задание

Для изготовления трех видов продукции (A, B, C) используется три вида ресурсов (1, 2, 3). Объем ресурса нормы его расхода на единицу продукции и цена продукции заданы таблицей (номер таблицы соответствует номеру варианта).

По заданной таблице:

  1. Составьте математическую модель определения оптимального плана выпуска продукции из условия ее максимальной стоимости.
  2. Составьте математическую модель двойственной задачи.
  3. Дайте экономическую интерпретацию двойственной задачи.
  4. Решите исходную задачу симплекс-методом и с помощью электронной таблицы Excel.
  5. Используя теоремы двойственности, найдите оптимальное решение двойственной задачи.
  6. Решите двойственную задачу с помощью электронной таблицы Excel и убедитесь в правильности решения, найденного в п. 5.
  7. Создайте отчет по результатам, по пределам и по устойчивости, поместите их в рабочую книгу и сделайте их распечатку.
  8. Определите дефицитность ресурсов. Расположите ресурсы в порядке убывания дефицитности.
  9. Найдите интервалы устойчивости двойственных оценок.
  10. Определите изменение максимальной стоимости продукции при изменении объема ресурсов на величину , предварительно установив, находятся ли эти изменения в интервалах устойчивости двойственных оценок. Оцените раздельное влияние этих изменений и суммарное.
  11. Оцените целесообразность введения в план новой продукции, для которой заданы: цена с4 = 10 и вектор-столбец (1, 2, 1) Т, задающий нормы затрат ресурсов на производство этой продукции.
  12. Оцените целесообразность закупки дополнительно 30 единиц первого ресурса по цене p1 = 3 у. е.

Таблица 1

Таблица 2

Ресурс

Объем

ресурса

Нормы расхода

Ресурс

Объем

ресурса

Нормы расхода

А

В

С

А

В

С

1

100

1

6

1

1

100

5

6

7

2

300

1

3

1

2

300

4

5

6

3

250

1

4

3

3

250

7

1

2

Цена продукции

1

4

3

Цена продукции

3

5

6

Таблица 3

Таблица 4

Ресурс

Объем

ресурса

Нормы расхода

Ресурс

Объем

ресурса

Нормы расхода

А

В

С

А

В

С

1

120

1

3

2

1

120

8

5

4

2

150

2

1

4

2

150

3

8

1

3

75

3

7

1

3

75

2

5

6

Цена продукции

5

10

12

Цена продукции

5

10

12

Таблица 5

Таблица 6

Ресурс

Объем

ресурса

Нормы расхода

Ресурс

Объем

 ресурса

Нормы расхода

А

В

С

А

В

С

1

125

2

1

1

1

125

3

4

6

2

175

3

2

1

2

175

5

4

3

3

250

1

4

3

3

250

2

6

7

Цена продукции

2

4

3

Цена продукции

2

4

3

Таблица 7

Таблица 8

Ресурс

Объем

ресурса

Нормы расхода

Ресурс

Объем

ресурса

Нормы расхода

А

В

С

А

В

С

1

190

1

2

5

1

190

5

4

3

2

120

12

4

9

2

120

7

1

8

3

60

7

1

3

3

60

4

3

7

Цена продукции

10

11

13

Цена продукции

10

11

13

Таблица 9

Таблица 10

Ресурс

Объем

ресурса

Нормы расхода

Ресурс

 Объем

ресурса

Нормы расхода

А

В

С

А

В

С

1

180

4

3

1

1

180

5

4

6

2

90

4

5

9

2

90

7

6

8

3

120

2

1

6

3

120

1

5

8

Цена продукции

12

5

3

Цена продукции

12

5

3

Таблица 11

Таблица 12

Ресурс

Объем

ресурса

Нормы расхода

Ресурс

Объем

ресурса

Нормы расхода

А

В

С

А

В

С

1

100

1

3

5

1

100

6

7

4

2

150

6

4

2

2

150

2

5

1

3

300

1

3

7

3

300

3

4

5

Цена продукции

3

4

6

Цена продукции

3

4

6

Таблица 13

Таблица 14

Ресурс

Объем

ресурса

Нормы расхода

Ресурс

Объем

ресурса

Нормы расхода

А

В

С

А

В

С

1

200

2

4

5

1

200

3

5

70

2

180

1

2

6

2

180

4

5

8

3

300

8

3

4

3

300

1

5

1

Цена продукции

13

5

2

Цена продукции

13

5

2

Таблица 15

Таблица 16

Ресурс

Объем

ресурса

Нормы расхода

Ресурс

 Объем

ресурса

Нормы расхода

А

В

С

А

В

С

1

70

6

4

2

1

70

3

2

1

2

140

7

11

10

2

140

5

6

7

3

200

4

5

8

3

200

1

2

5

Цена продукции

12

13

9

Цена продукции

12

13

9

Таблица 17

Таблица 18

Ресурс

Объем

ресурса

Нормы расхода

Ресурс

Объем

 ресурса

Нормы расхода

А

В

С

А

В

С

1

100

9

2

1

1

100

4

8

2

2

300

1

3

1

2

300

8

4

3

3

250

2

9

3

3

250

2

3

5

Цена продукции

1

4

1

Цена продукции

12

5

3

Таблица 19

Таблица 20

Ресурс

Объем

ресурса

Нормы расхода

Ресурс

Объем

ресурса

Нормы расхода

А

В

С

А

В

С

1

120

1

3

2

1

120

7

2

1

2

150

2

1

1

2

150

4

5

8

3

75

2

2

1

3

75

6

4

2

Цена продукции

5

10

12

Цена продукции

10

20

8

Таблица 21

Таблица 22

Ресурс

Объем

ресурса

Нормы расхода

Ресурс

Объем

ресурса

Нормы расхода

А

В

С

А

В

С

1

125

2

1

1

1

125

1

2

3

2

175

8

2

1

2

175

4

3

4

3

250

3

4

3

3

250

3

4

2

Цена продукции

2

4

4

Цена продукции

13

12

8

Таблица 23

Таблица 24

Ресурс

Объем

ресурса

Нормы расхода

Ресурс

Объем

ресурса

Нормы расхода

А

В

С

А

В

С

1

150

1

8

2

1

150

3

4

1

2

120

3

1

4

2

120

5

2

8

3

60

1

8

3

3

60

6

7

4

Цена продукции

10

11

12

Цена продукции

15

14

9

ЗАКЛЮЧЕНИЕ

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

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

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

  1.  Акулич И.Л. Математическое программирование в примерах и задачах / И.Л. Акулич. – М.: Высш. шк., 1996. – 319 c.
  2.  Балашевич В.А. Основы математического программи-рования / В.А. Балашевич. – Минск: Вышэйш. шк., 1976. – 173 c.
  3.  Вентцель Е.С. Исследование операций: задачи, принципы, методология / Е.С. Вентцель. – М.: Наука, 1988. – 206 с.
  4.  Использование электронных таблиц Excel в инженерных расчетах: Учеб. пособие / В.Я. Гуськов, Р.Л. Кочубиевская, Г.А. Руев, Н.Н. Федорова. – Новосибирск: НГАСУ, 1999. – 80 с.
  5.  Деордица Ю.С. Исследование операций в планировании и управлении / Ю.С. Деордица, Ю.М. Нефедов. – Киев: Вища шк., 1991. – 270 с.
  6.  Зайченко Ю.П. Исследование операций / Ю.П. Зайченко. – Киев: Вища шк., 1998. – 320 c.
  7.  Зуховицкий С.М. Линейное и выпуклое программирование / С.М. Зуховицкий, Л.И. Авдеева. – М.: Наука, 1967. – 460 c.
  8.  Калихман И.Л. Линейная алгебра и программирование / И.Л. Калихман. – М.: Высш. шк., 1967. – 428 с.
  9.  Калихман И.Л. Сборник задач по математическому программированию / И.Л. Калихман. – М.: Выcш. шк., 1975. – 270 c.
  10.  Карманов В.Г. Математическое программирование / В.Г. Карманов. – М.: Наука, 1986. – 286 с.
  11.  Киселева Э.В. Линейное и нелинейное программирование: Метод. указания / Э.В. Киселева, С.И. Соловьева. – Новосибирск: НИСИ, 1987. – 32 с.
  12.  Киселева Э.В. Математическое программирование: Учеб. задания / Э.В. Киселева, С.И. Соловьева. – Новосибирск: НГАС, 1996. – 32 с.
  13.  Задачи транспортного типа: Метод. указания / Э.В. Киселева, С.И. Соловьева, М.С. Соппа, И.Н. Мухина. – Новосибирск: НГАС, 1994. – 32 с.
  14.  Конюховский П.В. Математические методы исследова-ния операций в экономике / П.В. Конюховский. – СПб., 2000. – 208 с.
  15.  Кузнецов А.В. Высшая математика. Математическое программирование / А.В. Кузнецов, В.А. Сакович, Н.М. Холод. – Минск: Вища шк., 1994. – 286 с.
  16.  Кузнецов Ю.Н. Математическое программирование / Ю.Н. Кузнецов, В.И. Кузубов, А.Б. Волощенко. – М.: Выcш. шк., 1980. – 300 c.
  17.  Сакович В.А. Исследование операций / В.А. Сакович. – Минск: Вышэйш. шк., 1985. – 256 с.
  18.  Таха Х. Введение в исследование операций: В 2 кн. / Х. Таха. – М.: Мир, 1985. – Кн. 1. – 479 с.; Кн. 2. – 496 с.

ПРИЛОЖЕНИЕ.  Применение программы Excel к решению задач линейного программирования

Задача П.1. Составить математическую модель ЗЛП и решить ее с помощью программы Excel.

Для изготовления изделий А и В имеем 100 кг металла. На изготовление изделия А расходуется 2 кг металла, а изделия В расходуется 4 кг. Составить план производства, обеспечивающий получение наибольшей выручки от продажи изделий, если отпускная стоимость изделия А установлена 3 у.е., а изделия В – 2 у.е., причем изделий А требуется изготовить не более 40, а изделий В – не более 20.

Решение

  1. Составим математическую модель. Обозначим через х1 количество изделий А, производимых по плану, а х2 – количество изделий В. Тогда – план производства. Из условия задачи следует, что Выручка от продажи изделий составит

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

При составлении плана также необходимо учитывать ограничения по ресурсу. На изготовление х1 изделий А расходуется 2х1 (кг). Общий расход металла составит Эта величина не может превышать запасы металла в количестве 100 кг.

Получаем ограничение-неравенство:

.

Изделий вида А в плане производства должно быть не более 40, т.е. x1. Аналогично для изделий В: так как по условию этих изделий должно быть не более 20. Получим математическую модель задачи:

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

  1. Решим ЗЛП с помощью программы Excel. Для этого выполним следующие этапы:
  2. создать форму для ввода исходных данных задачи:

 

Набранный в данной форме текст на решение задачи не влияет, являясь комментарием  к условию задачи. Для переменных х1 и х2 зарезервированы ячейки В12 и С12. В них после решения задачи будут занесены полученные значения. Значение целевой функции будет зафиксировано в ячейке G10;

  1. ввести исходные данные.

В диапазон ячеек В4:С6 вносим коэффициенты при неизвестных в системе ограничений:

«Первое» – коэффициенты 1 и 0,

«Второе» – 0 и 1,

«Третье» – 2 и 4.

В диапазоне ячеек D4:D6 и Н4:Н6 заносим значения свободных членов системы ограничений: 40, 20 и 100. В диапазон В13:С13 – коэффициенты функции цели Z, т.е. 3 и 2;

  1. ввести расчетные формулы для целевой функции и левых частей системы ограничений. Для вычисления значений целевой функции   в ячейку G10 электронной таблицы ввести формулу

= В13*В12 + С13*С12.

Здесь вместо коэффициентов 3 и 2 записаны их адреса В13 и С13,  а вместо переменных х1 и х2 соответствующие адреса В12 и С12.

Теперь создадим формулы левых частей системы ограничений и расположим их в ячейках F4:F6. Сначала в ячейку F4 запишем выражение

= В4*$B$12 + C4*$C$12,

соответствующее алгебраическому выражению (1·х1 + 0·х2). Это левая часть первого ограничения задачи. Здесь мы воспользовались абсолютной адресацией ячеек для переменных х1 и х2, так как абсолютный адрес при копировании либо перемещении не меняется. Для создания формул в ячейках F5:F6 воспользуемся маркером заполнения для копирования полученной формулы в ячейке F4. Напомним: маркер заполнения – маленький прямоугольник в правом нижнем углу клетки:

Маркер заполнения клетки

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

= В5*$B$12 + C5*$C$12,

что соответствует выражению – (0·x1 +1·x2), а в ячейке F6:

= B6*$B$12 + C6*$C$12,

что соответствует выражению (2·х1 + 4·х2). В результате ввода всех исходных данных таблица примет вид:

  1. выделить целевую ячейку для запуска поиска решения;
  2. выбрать команду: Сервис Поиск решения;
  3. в открывающимся окне диалога (рис. П.1) установить:
  4. в группе Равной переключатель на максимальное значение,
  5.  в поле Установить целевую ячейку ввести адрес ячейки G10, содержащей формулу для расчета значения целевой функции,
  6. в поле Изменения ячейки указать ссылки на изменяемые ячейки В12 и С12, содержащие управляемые переменные х1 и х2,
  7.  в поле Ограничения можно задать нужные ограничения, для этого необходимо нажать кнопку Добавить; 
  8. в результате открывается диалоговое окно (рис. П.2) Добавление ограничения:

Рис. П.1. Диалоговое окно Поиск решения

Рис. П.2. Диалоговое окно Добавление ограничения

  1. в поле Ссылка на ячейку  указать адрес левой части первого ограничения F4. Из списка выбрать нужный оператор: ,
  2. в поле Ограничения указать адрес правой части первого ограничения Н4. Нажать кнопку ОК,
  3. следующее ограничение можно ввести аналогично, нажав кнопку Добавить.

Диалоговое окно Поиск решения после ввода всех данных имеет вид:

  1. для поиска оптимального решения нажать кнопку Выполнить. Если ЗЛП имеет решение, то на экране появятся результаты программы  Поиск  решения (рис. П.3):

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

.

Причем сырье (100 кг металла) используется полностью (левая и правая части третьего ограничения равны). Кроме того, первое ограничение выполняется как строгое равенство, а второе – строгое неравенство.

Рис. П.3. Результаты решения

Анализ найденного решения. После нажатия кнопки Выполнить, кроме результатов программы Поиск решения, на экране появится диалоговое окно Результаты поиска решения:

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

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

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

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

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

Отчет по устойчивости (рис. П.6). В этом отчете будет показано, как реагирует решение на изменение формулы или ограничений.

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

Параметр Лагранжа Множитель показывает, как изменится целевая функция при изменении «связанного» ограничения на единицу.

Рис. П.4. Отчет по результатам

Рис. П.5. Отчет по пределам

Рис. П.6. Отчет по устойчивости

Задача П.2.  Составить математическую модель транспортной задачи и решить ее с помощью программы Excel.

Имеется три пункта производства однородного продукта A1, A2, A3, мощности которых составляют соответственно 200, 300 и 400 единиц. Этот продукт востребован в трех пунктах потребления B1, B2, B3, потребности которых составляют 350, 300, 250 единиц.

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

.

Найти оптимальный план перевозок, минимизирующий общие затраты на перевозки.

Решение. Обозначим через xij величину поставки от i-го поставщика j-му потребителю.

Тогда   – план перевозок.

Общая стоимость перевозок выразится функцией

,

которую необходимо минимизировать.

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

.

Решим задачу с помощью программы Excel. Выполним следующие действия:

  1. Создадим форму для исходных данных:

Для целевой функции зарезервирована ячейка А12, для переменных xij – ячейки B4:B6, D4:D6, F4:F6, в них будут занесены результаты решения задачи.

  1. В ячейки B8, D8, F8 введем формулы для вычисления левых частей уравнений-ограничений по потребностям.

Для потребителя B1 ограничение имеет вид уравнения

Следовательно, в ячейку B8 нужно записать формулу:

=СУММ (В4:В6).

Формулы в ячейках D8 и F8 задаются аналогично (можно получить копированием из ячейки В8).

  1. В ячейки I4:I6 введем формулы для вычисления левых частей уравнений-ограничений по запасам.

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

что соответствует формуле в ячейке I4:

= B4 + D4 + F4.

Аналогично задаются формулы для ячеек I5 и I6.

  1. Для вычисления значения целевой функции , минимизирующей стоимость всех перевозок, в ячейку A12 запишем формулу:

= СУММПРОИЗВ (C4:C6; B4:B6) + СУММПРОИЗВ (E4:E6; D4:D6) + СУММПРОИЗВ (G4:G6; F4:F6).

  1. Выберем команду: СервисПоиск решения.
    1. В диалоговом окне Поиск решения введем:
      1. адрес ячейки А12 целевой функции;
      2. переключатель в группе Равной поставим на минимизацию;
      3. укажем диапазоны изменяемых ячеек:

B4:B6; D4:D6; F4:F6;

  1. укажем уравнения-ограничения по потребностям:

B8=B7; D8=D7; F8=F7;

  1. укажем уравнения-ограничения по запасам:

I4:I6=H4:H6;

  1. укажем требования неотрицательности переменных:

В4:B6>=0;

D4:D6>=0;

F4:F6>=0.

  1. Нажмем кнопку Выполнить.
    1. В результате выполнения программы Поиск решения получим на экране в ячейках B4:B6; D4:D6; F4:F6  оптимальный план перевозок, а в ячейке А12 – минимальную общую стоимость за все перевозки:

Таким образом,

а

11                              12


 

А также другие работы, которые могут Вас заинтересовать

60593. Игровые моменты и опорные конспекты на уроках истории 1.8 MB
  О первостепенном значении игры для естественного развития ребёнка свидетельствует тот факт что ООН провозгласила игру универсальным и неотъемлемым правом ребёнка. Включаясь в процесс игры дети научаются жить в нашем символическом...
60594. Побудова діаграм і графіків в електронних таблицях MS Excel 1.39 MB
  Пізнавальна мета уроку: закріпити навички роботи з ЕТ Excel; поглибити знання учнів по темі Діаграми; навчити учнів будувати різноманітні типи діаграм графіків у електронній таблиці...
60597. Освітньо-кваліфікаційна характеристика випускника професійно-технічного навчального закладу 284 KB
  Повинен уміти: виконувати операції з базами даних на комп’ютерному устаткуванні введення опрацювання накопичення систематизація та виведення інформації відповідно до затверджених процедур та інструкцій з використанням периферійного обладнання систем передавання приймання даних; готувати до роботи устаткування: магнітні диски стрічки картки папір; працювати в текстовому редакторі з введенням тексту та його редагуванням; оперувати з файлами записувати текст на дискету або переносити на папір за допомогою друкувальних пристроїв;...