Линейное программирование - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Линейное программирование является составной частью раздела математики... 1 36.89kb.
Основные условия, позволяющие строить модели лп 1 196.43kb.
Линейное программирование: постановка задач и графическое решение... 1 307.48kb.
Задача о назначениях. Комбинаторное программирование. Метод ветвей... 1 21.78kb.
Темы, рассмотренные в курсе «Программирование» для гр 1 23.95kb.
Программа по дисциплине визуальное программирование маслянкин В. 1 56.07kb.
Методические указания и задания для лабораторной работы по теме:... 1 303.96kb.
Учебно-методический комплекс по дисциплине Функциональное и логическое... 4 432.76kb.
В. П. Грибанов Лабораторный практикум по дисциплине "Информатика... 1 184kb.
Учебно-методический комплекс по дисциплине по выбору дв2 «логическое... 1 351.89kb.
1. Программа дисциплины Целью изучения дисциплины «Программирование»... 7 860.11kb.
Руководство по работе с модулем «Поисковая оптимизация» (seo) 1 103.28kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

Линейное программирование - страница №1/1



Министерство общего и профессионального образования РФ

Алтайский государственный технический университет

им. И.И. Ползунова

Бийский технологический институт

Л.И. Царегородцев, Ю.Н. Каргин, В.В. Царегородцева




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

Методические указания и контрольные задания для

студентов-заочников специальности 060800 - экономика и управление на предприятиях машиностроения; 071900 - информационные системы в экономике.

Бийск, 1999

УДК 519
Царегородцев Л.И., Каргин Ю.Н., Царегородцева В.В. Линейное программирование: Методические указания и контрольные задания для студентов - заочников.
Алт. гос. ун-т им. И.И.Ползунова, БТИ. -Бийск.

Изд-во Алт. гос. ун-та, 1999.-54с.

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

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


Рассмотрено и одобрено

на заседании кафедры математики

Протокол №14 от 6.12.1998 г.
Рецензент: Фарукшин В.Х. к.ф.-м. н., доцент БИГПИ

РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ И ОФОРМЛЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ

Раздел "Линейное программирование" разбит на шесть тем. Перед выполнением контрольного задания студент должен изучить соответствующую тему по пособиям, рекомендуемым в "Методических указаниях". Пособия обозначаются номерами в квадратных скобках; например, [3] означает ссылку на учебник А.В. Кузнецова, В.А. Саковича и Н. И. Холода. В "Методических указаниях" приводится перечень знаний и умений, которыми должен обладать студент, изучивший тему. В них даются также некоторые начальные теоретические сведения и приводятся решения типовых примеров. Если студент испытывает затруднения в освоении теоретического или практического материала, то он может получить консультацию на кафедре математики БТИ. График консультаций можно узнать в деканате заочного отделения.

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

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

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

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

ЛИТЕРАТУРА


  1. Беклемишев Д.В. Курс аналитической геометрии и линейной

алгебры.-М.: Наука, 1980

  1. Высшая математика для экономистов /Под ред. проф.

Н.Ш.Кремера.- М.: Банки и биржи, 1997.

  1. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика:

математическое программирование.-Мн.: Высшая школа, 1994.

  1. Акулич И.Л. Математическое программирование в примерах и

задачах–М.: Высшая школа, 1986.

  1. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в

упражнениях и задачах. В 2-х ч.Ч.1–М.: Высшая школа, 1986.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ К КОНТРОЛЬНОЙ РАБОТЕ

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

Литература: [1], гл. V, § 1-5; [2], гл. II

Студент должен



знать:

  1. определение n-мерного арифметического пространства и линейных операций над векторами из ;

  2. определение линейно независимой системы векторов и базиса в ;

  3. определение скалярного произведения векторов в и понятие ортонормированной системы векторов в ;

  4. понятия определителя, матрицы, базисного минора и ранга матрицы, определение элементарных преобразований матрицы, теорему о базисном миноре;

  5. понятие системы линейных уравнений, виды систем, задачи теории систем линейных уравнений;

  6. метод Гаусса решения систем линейных уравнений;

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

уметь:

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

  2. выполнять элементарные преобразования матрицы и находить ее ранг;

  3. находить максимальную линейно независимую подсистему в заданной системе векторов из ;

  4. находить координаты произвольного вектора из в заданном базисе;

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

Основные теоретические сведения

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

. (1.1)

Элементы множества называют векторами. Вектор может быть записан как в виде строки (1.1), так и в виде столбца:



. (1.2)

Числа , называются компонентами вектора.

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

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

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

. (1.3)

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

. (1.4)

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

. (1.5)

Множество всех векторов вида (1.1)-(1.2), в котором определены операции сложения векторов (1.3), умножения вектора на число (1.4) (такие операции называются линейными) и операция скалярного произведения (1.5) называется n-мерным вещественным арифметическим пространством.



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

. (1.6)

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

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

Определение 1.3. Система векторов из называется базисом пространства , если:

1) эти вектора линейно независимы;

2) любой вектор из является линейной комбинацией векторов данной системы.

Примером базиса в может служить ортонормированная система векторов



. (1.7)

Векторы (1.7) обладают следующим свойством:



. (1.8)

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

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

Определение 1.4. Системой m линейных уравнений с n неизвестными называется система вида

, (1.9)

.

Систему уравнений (1.9) можно записать в матричном виде:



, (1.10)

где - основная матрица системы (1.9), -вектор-столбец неизвестных, -вектор-столбец свободных членов:



, , . (1.11)

Систему (1.9) можно представить также в векторном виде:



, (1.12)

где - вектор-столбец, составленный из коэффициентов при j-ой неизвестной .



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

Система линейных уравнений (1.9) называется совместной, если она имеет хотя бы одно решение, и несовместной, если она не имеет ни одного решения.

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

Решить систему линейных уравнений - это значит:

1) выяснить, совместна система или нет;

2) если система совместна, то найти все ее решения.

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

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

Рассмотрим пример. Решить систему уравнений:

. (1.13)

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



. (1.14)

Шаг 1. Вычитая первую строку матрицы из третьей и четвертой строк, обратим в нуль все элементы первого столбца кроме первого. Мы получим

. (1.15)

Шаг 2. Умножая элементы второй строки на числа (-2), 5 и 3 и вычитая затем вторую строку соответственно из первой, третьей и четвертой, обратим в нуль все элементы второго столбца кроме второго. Результат имеет вид:

. (1.16)

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

. (1.17)

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

Матрице (1.17) соответствует система линейных уравнений вида:

. (1.18)

Эта система равносильна исходной системе (1.13). В соответствии с выбором базисного минора переменные и являются базисными, а переменные -свободными. Придавая свободным переменным произвольные значения , , найдем общее решение системы (1.13) в виде:



, (1.19)

, .

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

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

=(-8, 3, 6, 0, 0), (1.20)

выраженное через базисные векторы .

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

, мы получим систему (1.18) в виде

, (1.21)

откуда , , . Таким образом, новое базисное решение имеет вид



=(-8, 0, 0,-3, 0). (1.22)

Оно выражено через базисные векторы .

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

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



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

программирования, ее геометрическая интерпретация
Литература: [3] гл. I, § 1.1-1.3; [2] гл. I, § 1.1–1.3; [5] гл. XI, §1,2.

Студент должен



знать:

  1. постановку и различные формы записи ЗЛП;

  2. что такое множество допустимых планов;

  3. что такое целевая функция;

  4. алгоритм решения ЗЛП геометрическим методом;

уметь:

  1. формулировать ЗЛП в различных формах для определенного типа экономических задач;

  2. решать ЗЛП геометрическим методом;

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

2.1 Математическая модель задачи ЛП

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



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

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

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

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


  1. совокупность неизвестных переменных величин - вектор

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

  1. целевую функцию , которая позволяет выбирать наилуч-

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

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

.

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

найти план

, (2.1)

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



(2.2)

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



 bi (i=1,2,..m). (2.3)

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



, , (2.4)

а иногда - целочисленности.

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

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



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

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



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

Составим математическую модель задачи. Обозначим объем производства продукции П1 через , а продукции П2 - через . Тогда прибыль от ее реализации составит (руб).



Таблица 2.1

ПолуфабрикатыРасход полуфабрикатов на единицу продукцииОбъемы полуфабрикатовП1 П2 I12800II622400Прибыль, руб/ед. прод.1035Заданные ограничения на полуфабрикаты можно записать в виде системы неравенств:



(2.5)

К записанной системе следует добавить неравенства:



(2.6)

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

(2.5) - (2.6).

2.2 Основные виды записи задачи ЛП

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

(2.7)

при условиях:



, (2.8)

, (2.9)

, (2.10)

- произвольные , (2.11)

где - заданные постоянные величины и .

Иными словами, общая ЗЛП заключается в определении n переменных величин , удовлетворяющих k неравенствам вида (2.8) и (m-k) уравнениям вида (2.9), при которых функция достигает максимального значения. (При этом переменных могут принимать только неотрицательные значения, а - произвольные значения)

Определение 2.2. Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (2.7) при выполнении условий (2.8) и (2.10), где и , т.е. задача, в которой все переменные неотрицательны, и ограничения заданы только неравенствами вида “ ”. В рассмотренном выше примере задача записана в симметричной форме.

Определение 2.3. Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (2.7) при выполнении условий (2.9) и (2.10), где и , т.е. задача, в которой все переменные неотрицательны, и ограничения заданы только уравнениями.

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



. (2.12)

Решение задачи геометрическим методом состоит из следующих этапов:



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

  2. Строят вектор градиента целевой функции (2.12). Этот вектор показывает направление наискорейшего возрастания целевой функции.

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

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

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

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

геометрическим методом

Пример 2.2. Решим пример 2.1, приведенный выше, геометрическим методом.

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

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

Рисунок 2.1


Возьмем, например, точку (10, 1). Координаты этой точки удовлетворяют всем трем неравенствам системы (2.5). Действительно, , , .

Следовательно, все три неравенства выполняются в полуплоскостях, содержащих точку (10, 1).

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

Построим в точке О(0,0) вектор градиента целевой функции или любой другой вектор, коллинеарный (рисунок 2.1).

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

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



.

3 Симплекс- метод решения ЗЛП с естественным базисом

Литература: [3], гл. 1, § 1.4–1.5; [4], гл. I, § 1.4.

Студент должен



знать:

  1. что такое опорный план, оптимальный план;

  2. алгоритм решения ЗЛП симплекс- методом;

  3. алгоритм построения симплекс- таблицы;

  4. как определить разрешающий элемент симплекс- таблицы;

  5. критерий оптимальности опорного плана;

уметь:

  1. приводить систему ограничений ЗЛП к предпочтительному виду;

  2. решать ЗЛП симплекс- методом;

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

Основные теоретические сведения

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

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

3.1 Построение начального опорного плана

Пусть требуется найти максимальное значение функции



(3.1)

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



(3.2)

, . (3.3)

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

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

будет опорным.

Если система ограничений имеет симметричный вид

, (3.5)

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



, (3.6)

которая имеет предпочтительный вид. Ее начальный опорный план можно выбрать в виде


. (3.7)

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



, . (3.8)

3.2 Признак оптимальности опорного плана

Симплекс-таблицы

Рассмотрим ЗЛП (3.1)-(3.2), записанную в предпочтительном виде. Введем обозначения:



, (3.9)

, (3.10)

,

где –вектор коэффициентов целевой функции при базисных переменных; –вектор-столбец свободных членов; –вектор-столбец коэффициентов при переменных .

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

Теорема 3.1. Опорный план задачи (3.1)-(3.2) является оптимальным, если для всех j .

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

.Теорема 3.2. Если для некоторого и среди чисел нет положительных , то целевая функция (3.1) задачи (3.1)-(3.2) не ограничена сверху на множестве ее планов.



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

Теорема 3.3. Если опорный план задачи (3.1)-(3.2) не вырожден и , но среди чисел есть положительные (не все ), то существует опорный план такой, что .

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

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

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

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

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

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




  1. для ;

  2. для некоторого , и все соответствующие этому

индексу величины ;

Таблица 3.1.

Базис


пер с1с2 .cpcmcm+1ck.cnA1A2.ApAmAm+1Ak.Anx1c1b11000a1,m+1a1,k.a1,nx2c2b20100a2,m+1a2,k.a2,n………………………………….xpcpbp0010ap,m+1ap,k.ap,n………………………………….xmcmbm0000am,m+1am,k.am,nΔ00000Δm+1Δk.Δn.

Таблица-3.2

Базис


пер



A'0с1с2 .cpcmcm+1ck.cnA1A2.ApAmAm+1Ak.Anx1c1b'110a'1,p0a'1,m+10.a'1,nx2c2b201a'2,p00a'2,m+10k.a'2,n………………………………….xkckb'p00a'p,p0a'p,m+11.a'p,n………………………………….xmcmb'm00a'm,p0a'm,m+10.a'm,nΔ'000Δ'p0Δ'm+10.Δ'n

3. j < 0 для некоторых индексов , и для каждого такого по крайней мере одно из чисел положительно.

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

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

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

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



(3.11)

Новые элементы , соответствующие новому опорному плану, вычисляются по формулам



(3.12)

После вычисления и по формулам (3.11)-(3.12) их значения заносят в таблицу 3.2. Элементы индексной строки этой таблицы могут быть вычислены либо по формулам



, (3.13)

либо на основании их определения.

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

Таким образом, переход от одного опорного плана к другому сводится к переходу от одной симплекс-таблицы к другой. Элементы новой симплекс-таблицы можно вычислять как с помощью рекуррентных формул (3.11)-(3.13), так и по правилам, непосредственно вытекающим из них. Эти правила можно найти, например в [4].

Итак, нахождение оптимального опорного плана симплексным методом включает следующие этапы:


  1. находят начальный опорный план;

  2. составляют симплекс-таблицу;

  3. выясняют, существует ли хотя бы одно отрицательное число .

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

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

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

5) по формулам (3.11)-(3.13) определяют положительные компоненты нового опорного плана, новые компоненты столбцов и оценки и . Все эти числа записывают в новую симплекс-таблицу;

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

4 Симплекс- метод решения ЗЛП с искусственным базисом

(М-метод)
Литература: [3], гл. 1, § 1.5; [4], гл. I, § 1.4.

Студент должен



знать:

  1. алгоритм приведения ЗЛП к задаче с искусственным базисом;

уметь:

  1. приводить ЗЛП к задаче с искусственным базисом;

  2. решать ЗЛП симплекс- методом с использованием симплекс-таблицы.

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

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



. (4.1)

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



. (4.2)

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

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

(4.3)

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



, (4.4)

(4.5)

, , , . (4.6)

Задача (4.4)-(4.6) называется расширенной по отношению к исходной задаче. Ее начальный опорный план можно выбрать в виде:



. (4.7)

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



Теорема 4.1. Если в оптимальном плане

(4.8)

расширенной задачи (4.4)-(4.6) все искусственные переменные , то план является оптимальным планом исходной задачи ЛП.

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

Рассмотрим подробнее процесс решения расширенной задачи.

Для опорного плана расширенной задачи значения целевой функции и оценок равны

, . (4.9)

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

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

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

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

Итерационный процесс в -ой строке продолжают до тех пор, пока не будет выполнено одно из следующих условий:



  1. все искусственные переменные исключены из базиса;

  2. среди базисных переменных есть искусственные, но в -ой

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

В первом случае базис отвечает некоторому опорному плану исходной задачи и поиск ее оптимального плана продолжают по -ой строке.

Во втором случае исходная задача не имеет решения, если значение, стоящее в -ой строке столбца отрицательно.

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



  1. составляют расширенную задачу (4.4)-(4.:6);

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

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

из числа базисных. В результате, либо получают опорный план исходной задачи (4.3), либо устанавливают ее неразрешимость;

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



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

симплекс-методом

Пример 4.1 Участок шлифовки выпускает за неделю 500 колец для подшипников типа А и 350 колец для подшипников типа B. Все кольца шлифуются на двух взаимозаменяемых станках I и II разной производительности. Машинное время каждого станка составляет 2500 мин. Трудоемкость операций (в минутах на одно кольцо) при изготовлении колец характеризуется следующими данными (таблица 4.1).

Таблица 4.1

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



Решение. Составим математическую модель задачи. Обозначим через – количество колец, изготавливаемых на станке I, для подшипников типа А; через – количество колец, изготавливаемых на станке I, для подшипников типа B; через – количество колец, изготавливаемых на станке II, .для подшипников типа А и через – количество колец, изготавливаемых на станке II, для подшипников типа B.

Целевая функция, отражающая суммарные затраты машинного времени, будет иметь вид:



(4.10)

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



(4.11)

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



где М - достаточно большое положительное число,





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



.

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












Таблица 4.2

Базисн.


перемен 4 10 6 8 0 0 M M 02500 4 10 0 0 1 0 0 0 02500 0 0 6 8 0 1 0 0 M500 1 0 1 0 0 0 1 0 M350 0 1 0 1 0 0 0 1 -4 -10 -6 -8 0 0 0 0850M M M M M 0 0 0 0Для удобства итерационного процесса множители при записываем в шестой строке, а слагаемое, которое не содержит – в пятой строке.

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


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

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

Составляем таблицу второй итерации (таблица 4.3). Чтобы заполнить третью строку новой таблицы, элементы третьей строки старой таблицы делим на разрешающий элемент. Элементы разрешающего столбца заполняем нулями, кроме . Другие базисные столбцы переписываем без изменений. Все остальные элементы таблицы 4.3 пересчитываем по формулам (3.11)-(3.13).
Таблица 4.3

Базисн.


перемен 4 10 6 8 0 0 M 0 500 0,4 10 -4 0 1 0 0 0 2500 0 0 6 8 0 1 0 4 500 1 0 1 0 0 0 0 M 350 0 1 0 1 0 0 1 2000 0 -10 -2 -8 0 0 0350M 0 M 0 M 0 0 0

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

Разрешающей строкой является вторая строка. На пересечении выбранной строки и столбца стоит разрешающий элемент, равный 8.

Составляем таблицу третьей итерации (таблица 4.4).



Таблица 4.4

Базисн.


перемен 4 10 6 8 0 0 M 0 500 0 10 -4 0 1 0 0 8 312,5 0 0 0,75 10,125 1 0 4 500 1 0 1 0 0 0 0 M 37,5 0 1 -0,75 0-0,125 0 1 4500 0 -10 4 0 1 0 0 37,5M 0 M-0,75M 0-0,125M 0 0В последней строке имеется положительное число M. Данный опорный план расширенной задачи все еще не является оптимальным. Переходим к новому опорному плану расширенной задачи. Введем в базис переменную , второй столбец будет разрешающим. Из базиса исключаем переменную . Разрешающей строкой является четвертая строка. На пересечении выбранной строки и столбца стоит разрешающий элемент 1.

Составляем таблицу четвертой итерации (таблица 4.5). При этом столбец из таблицы исключается.



Таблица 4.5

Базисн.


перемен 4 10 6 8 0 0 0 125 0 0 3,5 0 1 1,25 8 312,5 0 0 0,75 1 0 0,125 4 500 1 0 1 0 0 0 10 37,5 0 1 -0,75 0 0-0,125 4875 0 0 -3,5 0 0 -0,25В последней строке таблицы 4.5 среди оценок нет положительных. Формально это означает, что найденный опорный план исходной канонической задачи

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

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

На станке I шлифуется 500 колец для подшипников типа А и 38 колец для подшипников типа Б, общее время работы станка I равно (мин). На станке II шлифуется 312 колец для подшипников типа Б, общее время работы станка II равно



(мин).

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



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

Литература: [3], гл. 2; [4], гл. I, § 1.6

Студент должен



знать:

  1. правила построения задачи, двойственной к исходной ЗЛП;

  2. свойства взаимно двойственных задач;

  3. теоремы двойственности;

  4. свойство двойственных оценок (экономический анализ);

уметь:

  1. строить задачу, двойственную к исходной ЗЛП;

  2. определять оптимальный план двойственной задачи по оптимальному плану исходной ЗЛП;

  3. проводить экономико-математический анализ ЗЛП на основе двойственных оценок.

Основные теоретические сведения

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



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

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



(5.1)

при условиях



, (5.2)

(5.3)

Определение 5.1 Задача, состоящая в нахождении минимального значения функции

(5.4)

при условиях



, (5.5)

, (5.6)

называется двойственной по отношению к задаче (5.1)-(5.3), а переменные двойственными оценками.

Задачи (5.1)-(5.3) и (5.4)-(5.6) образуют пару задач, называемую парой взаимно двойственных задач линейного программирования.

Сравнивая пару двойственных задач (5.1)-(5.3) и (5.4)-(5.6), можно сформулировать правила, по которым составляется двойственная задача:



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

то в двойственной задаче –минимум, и наоборот;

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

бодными членами системы ограничений двойственной задачи;

  1. свободные члены системы ограничений прямой задачи являются

коэффициентами целевой функции двойственной задачи;

  1. матрицы коэффициентов ограничений прямой и двойственной зада-

чи являются транспонированными друг к другу;

  1. если прямая задача решается на максимум, и ее система ограниче-

ний состоит из неравенств типа “”,то двойственная задача решает- ся на минимум, и ее система ограничений состоит из неравенств

типа “”;



  1. число ограничений прямой задачи равно числу переменных двойст-

венной, а число ограничений двойственной–числу переменных

прямой;


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



5.2 Экономическая интерпретация симметричных

двойственных задач

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

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

Математическая модель задачи имеет вид (5.1)-(5.3).

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

1) общую стоимость отходов сырья покупатель стремится минимизи-

ровать;

2) предприятие согласно продать отходы только по таким ценам, при



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

получить, организовав собственное производство.

Эти требования приводят к следующей математической модели.

Требование 1 покупателя –минимизация стоимости покупки:



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



.

Здесь левая часть означает выручку за сырье, идущее на производство единицы продукции первого вида; правая – цену реализации каждой единицы этой продукции.

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

(5.4)-(5.6).



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

Решение. Пусть - объемы продукции , планируемой к выпуску; –сумма выручки. Математическая модель прямой задачи.

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





Таблица 5.1

РесурсыВыпускаемая продукцияОбъем ресурсовП1П2П3П4Р1Трудовые ресурсы, чел-час42284800Р2Полуфабрикаты, кг210602400Р3Станочное оборудование, станко-час10211500Цена единицы продукции, руб657060120Пусть –оценка стоимости одного человеко-часа, –оценка одного килограмма полуфабриката, - оценка стоимости одного станко- часа. Тогда математическая модель двойственной задачи имеет вид:



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





5.3 Связь между решениями прямой и двойственной задачи

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

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

Теорема 5.1. Для любых допустимых планов и прямой и двойственной ЗЛП справедливо неравенство , т. е.

. (5.7)

Теорема 5.2. (критерий оптимальности Канторовича). Если для некоторых допустимых планов и пары двойственных задач выполняется равенство

, (5.8)

то оптимальный план исходной задачи, а оптимальный план двойственной задачи.

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



Теорема 5.3. (первая теорема двойственности). Если одна из пары двойственных задач (5.1)-(5.3) или (5.4)-(5.6) имеет оптимальный план, то и другая имеет оптимальный план, и значения целевых функций задач при их оптимальных планах равны между собой, т. е.

. (5.9)

Если же целевая функция одной из пары двойственных задач не ограничена (для исходной задачи (5.1)-(5.3)–сверху, для двойственной задачи (5.4)-(5.6)–снизу), то система ограничений другой задачи противоречива (задача вообще не имеет допустимых планов).

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

(5.10)

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



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

(5.11)

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



6 Транспортная задача. Метод потенциалов

Литература: [3], гл. 5; [4], гл. 2, § 2.1.

Студент должен



знать:

  1. что такое открытая и закрытая транспортная задача;

  2. что такое опорный план транспортной задачи;

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

  4. что такое цикл пересчета и его свойства;

уметь:

  1. формулировать транспортную задачу в табличном виде;

  2. преобразовывать открытую транспортную задачу в закрытую;

  3. находить опорный план методом "минимального элемента";

  4. проверять оптимальность плана по методу потенциалов;

  5. выбирать и проводить цикл пересчета;

  6. определять оптимальный план и анализировать его.

6.1 Постановка задачи по критерию стоимости в матричной форме

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

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

, (6.1)

при условиях:



(6.2)

(6.3)

(6.4)

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



Определение 6.1. План , при котором функция (6.1) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывают в виде распределительной таблицы (таблица 6.1). При этом саму таблицу иногда называют табличной или матричной моделью транспортной задачи.


Таблица 6.1

Пункты отправ-ления Пункты назначения

Запасы ……. …….



……



……...





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



…….

……..





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



…..



……..





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

(6.5)

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



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

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

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

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

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

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

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

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



  1. определяют начальный опорный план задачи;

  2. найденный опорный план по определенным критериям проверяют

на оптимальность;

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

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

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

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

получают оптимальный план.



6.2 Построение начального опорного плана

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

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

Пример 6.1. Предприятие, содержащее сеть из пяти автозаправочных станций, обеспечивается бензином с трех нефтебаз. Суточные потребности АЗС, возможности нефтебаз и тарифы перевозок (руб./тонну) записаны в таблице 6.2.

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



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

тонн с нулевыми тарифами перевозок Исходный опорный план перевозок построим

Таблица 6.2

Пункты отправления Пункты назначения.

Запасы

(тонн) 142010161780 1581411890 1016121210140Потребности,



(тонн)

40

30



90

80

50



290<

<310методом минимального элемента, начиная планировать перевозки с маршрутов с наименьшими тарифами перевозок.

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

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

Таблица 6.3

Нефтебазы Автозаправочные станцииЗапасы (тонн)

14

20

10



6016

17

0



2080

158

301411

108

50

090 10



401612

3012

70

100140Потреб-ности (тонн)

40

30

90



80

50

20



310

остается доставить 30 тонн топлива. Так как в третьем столбце минимальный тариф находится в клетке (3;3), положим . Далее заполним клетки второй строки (2;5), (2;2) и (2;4) значениями , и . И, наконец, заполним клетки третьей строки (3;1) и (3;4), полагая , . В результате получим начальный опорный невырожденный план (таблица 6.3), число занятых клеток равно .

При данном плане перевозок общая стоимость перевозок равна



6.3 Метод потенциалов

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



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

для (6.6)

и для , (6.7)

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

Определение 6.2. Числа и называются потенциалами соответственно -го пункта отправления -го пункта назначения.

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

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

. (6.8)

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

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

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

Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами.

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


  1. каждой из клеток, связанных циклом с данной свободной клеткой,

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

плюс, а всем остальным клеткам–поочередно знаки минус и плюс;



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

щих в минусовых клетках. Одновременно это число прибавляют к

соответствующим числам, стоящим в плюсовых клетках, и вычита- ют из чисел, стоящих в минусовых клетках. Клетка, которая ранее

была свободной, становится занятой, а минусовая клетка, в которой

стояло наименьшее из чисел , считается свободной.

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

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

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

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



Пример 6.2. Найти оптимальный опорный план задачи из примера 6.1 и вычислить суточные расходы предприятия на перевозки бензина по этому плану.

Решение. Начальный опорный план задачи найден в примере 6.1.

Итерация 1 Для определения потенциалов составляем систему уравнений вида (6.6):

, , , ,

, , ,

Полагая , найдем, что , , , , , , , .

Потенциалы проставлены в таблице 6.4. Определим оценки свободных клеток:

, ,

, ,

, ,

, ,

,

Таблица 6.4.

40 30 90 80 50 20

142010

60

+16170

20

158



301411

108

500 10

401612

30

–12


70100

+ , , , , , .

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

Итерация 2. Наиболее потенциальной является клетка (3;6). Строим для клетки (3;6) цикл непосредственно в таблице 6.4. В него войдут клетки (3;6), (3;3), (1;3), (1;6). Наименьшее количество груза, стоящее в минусовых вершинах цикла, равно 20. В результате смещения по циклу получим новый опорный план (таблица 6.5).

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



, , , ,

, , , .

Ее решение имеет вид: , , , , , , , , .



Таблица 6.5

40 30 90 80 50 20

142010

8016170 158

301411

108

500 10

401612

1012

7010 0

20 , , , , , .

Вычисляем оценки свободных клеток:



, ,

, ,

, ,

, ,

, .

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

Минимальные суточные транспортные расходы предприятия по этому плану равны

При этом на нефтебазе осталось двадцать тонн невостребованного бензина.



ЗАДАНИЯ К КОНТРОЛЬНОЙ РАБОТЕ

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

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



Задача 1 Дана система линейных уравнений:

Требуется:



  1. выяснить совместна система или нет; если система совместна, то

является ли она опреде­ленной или нет; записать систему в матричном виде;

  1. решить систему методом Гаусса, выписать общее решение системы ;

  2. найти все базисные решения системы уравнений, указать среди них

опорные решения.

Задача 2 Для производства продукции двух типов I и II предприятие использует три вида сырья A, B и C. Общее количество сырья (в расчете на трудовую неделю), расход сырья каждого вида на единицу выпускаемой продукции и прибыль от реализации единицы продукции приведены в таблице 1.

Таблица 1

Виды

  • сырьяРасход сырья в кг/ед. прод.Количество


  1. сырья в кгПродукция IПродукция IIAM6N00B63300C714700Прибыль,

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

  1. составить экономико-математическую модель задачи и описать

смысл полученных неравенств;

  1. найти решение задачи геометрическим методом;

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

отношения , где и - прибыли от

реализации единицы продукции соответственно первого и второго

типов.

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


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

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

менных, а также полученных уравнений и неравенств;



b) найти решение задачи, используя симплекс-метод.

Таблица 2

Виды сырьяРасход сырья на одно изделие.Запасы сырья

в кг.Изделие IИзделие IIИзделие IIIA1815123600B64N2000CМ331600Прибыль в руб.201016Задача 4 Для изготовления трех видов деталей A, B и C на предприятии используются два взаимозаменяемых станка разной производительности. Суточные нормы выпуска деталей видов A, B и C соответственно равны 150, 100 и 50 штук. Каждый станок может эксплуатироваться 24 часа в сутки. Затраты времени на изготовление одной детали каждого вида для каждого из используемых станков указаны в таблице-3.

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



  1. составить экономико-математическую модель задачи;

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

таблицы;

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

переменные в оптимальном плане могут принимать только целочис-

ленные значения.



Таблица 3.

  1. СтанкиЗатраты времени на одну деталь в минABCI2M10II8N4Задача 5 Для условий задачи 3 требуется:

  1. сформулировать двойственную задачу, найти ее оптимальный план,

проанализировать использование ресурсов в оптимальном плане;

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

мых изделий и план их выпуска, если запасы сырья вида A увели-

чатся на 200 кг, а запасы сырья вида B уменьшатся на 100 кг;



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

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

изготовление одного изделия этого вида соответственно равны 7, 8

и 4 руб.

Задача 6 В четырех хранилищах , , и имеется соответственно 70, 80, 90 и 100 т топлива. Требуется спланировать перевозку топлива четырем потребителям , , , , спрос которых равен соответственно M0 (M- предпоследняя цифра в шифре студента), 60, 80 и 120 т, так, чтобы затраты на транспортировку были минимальны. Стоимость перевозки 1 т топлива указана в таблице 4. Решение задачи следует выполнить по следующему плану:


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

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

  1. решить задачу методом потенциалов;

  2. проанализировать изменения в решении задачи, если стоимость

перевозки 1 т топлива из первого хранилища второму потребителю

изменяется в пределах от 0 руб. до 10 руб.


Таблица 4.

ХранилищаПотребителиЗапас

топлива,

т Стоимость перевозки 1 т топлива в руб 9N11370 8851280 249690 7614100Потребность в топливе, M06080120СОДЕРЖАНИЕ

Рекомендации по выполнению и оформлению контрольной работы ....3

Методические указания к контрольной работе………………………….4

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

2. Постановка и различные формы записи задачи линейного
программирования, ее геометрическая интерпретация……………. 11

2.1. Математическая модель задачи ЛП……………………………....11

2.2. Основные виды записи задачи ЛП………………………………..14

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


геометрическим методом…………………………………………16

3. Симплекс- метод решения ЗЛП с естественным базисом………..…18

3.1. Построение начального опорного плана………………………...18

3.2. Признак оптимальности опорного плана. Симплекс таблицы....20

4. Симплекс- метод решения ЗЛП с искусственным базисом
(М-метод)………………………………………………………………25

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

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

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

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

5.2. Экономическая интерпретация симметричных двойственных

задач………………………………………………………………..35

5.3. Связь между решениями прямой и двойственной задачи……....37

6. Транспортная задача. Метод потенциалов…………………………...39

6.1. Постановка задачи по критерию стоимости в матричной


форме…………………………………………………………….…39

6.2. Построение начального опорного плана…………………………42

6.3. Метод потенциалов………………………………………………..44

Задания к контрольной работе по линейному программированию …..49

Царегородцев Леонид Иллирикович,

Каргин Юрий Николаевич,

Царегородцева Валентина Всеволодовна.

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Методические указания и контрольные задания для

студентов - заочников специальности 060800 - экономика и управление на предприятиях машиностроения; 071900 - информационные системы в экономике.

Подписано в печать 09.04.99. Формат 60х84 I/16.

Усл. п. л. – 3,3. Уч. изд. л. – 3,07.

Печать – множительно-копировальный аппарат

«RISO TR 1510».

Тираж 50 экз. Заказ 99 - 35.

Издательство Алтайского государственного

технического университета им. И. И. Ползунова.

656099, г. Барнаул, пр-т Ленина, 46.

Оригинал-макет подготовлен ИВЦ БТИ

АлтГТУ им. И.И. Ползунова.

Отпечатано на ИВЦ БТИ

АлтГТУ им. И.И. Ползунова.



659305, г. Бийск, ул. Трофимова, 29.





izumzum.ru