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



страница6/10
Дата02.01.2013
Размер0.83 Mb.
ТипМетодические указания
1   2   3   4   5   6   7   8   9   10


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

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

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

Таблица 4.4

Базисн.

перемен





4

10

6

8

0

0

M


























0

500

0

10

-4

0

1

0

0

gif" name="object394" align=absmiddle width=24 height=21>

8

312,5

0

0

0,75

1

0,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

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

знать:

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

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

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

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

уметь:

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

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

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

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

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

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).
1   2   3   4   5   6   7   8   9   10

Похожие:

Линейное программирование iconЛинейное программирование
Линейное программирование (ЛП) это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на...
Линейное программирование iconПеречень вопросов для вступительного экзамена в аспирантуру по специальности 05. 13. 18 «Математическое моделирование, численные методы и комплексы программ» Математические основы
Математическое программирование, линейное программирование, выпуклое программирование
Линейное программирование iconЛинейное программирование. Методы решения одношаговых задач оптимального управления
Методы решения таких задач получили название математического программирования. Простейшим случаем математического программирования...
Линейное программирование iconМатематическое программирование
В математическом программировании выделяют линейное программирование – когда функции и линейны, квадратичное программирование, когда...
Линейное программирование iconЛинейное программирование задачи математического и линейного программирования
Соответствующие методы, позволяющие решать указанные задачи, объединяются под общим названием «математическое программирование»
Линейное программирование iconПараметрическое линейное программирование
Параметрическое программирование представляет собой один из разделов математического программирования, изучающий задачи, в которых...
Линейное программирование icon«Линейное программирование и симплекс метод»

Линейное программирование iconВопросы экзамена Методы оптимизации Раздел Линейное программирование
Алгоритм симплекс-метода без корректного вида базиса с искусственными переменными
Линейное программирование iconЛинейное программирование и симплекс метод
...
Линейное программирование iconТранспортная задача
Линейное программирование является одним из разделов математического программирования – области математики, разрабатывающей теорию...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org