Контрольная работа № 1 «Линейное программирование» Вариант № 37

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР)

Кафедра компьютерных систем в управлении и проектировании (КСУП)

Контрольная работа № 1

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

Вариант № 37

Выполнил:

2014

Исходная информация

i №	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
37	8	6	1	9	2	1	6	8	9	8	6	2	6	9	3	4	3	7	2	5	2	5	9	4

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

Исходные данные:

i	1	2	3	4	5	6
i	7	8	9	10	11	12
i	13	14	15	16	17	18
i	3	6	9	12	15	18
i	19	20	21	22

.

Задача линейного программирования:

2. Содержательная постановка задачи

Небольшое ткацкое предприятие производит шесть видов ткани из трех типов пряжи.

На изготовление одного метра ткани 1-го вида требуется 8, 6 и 6 мотков пряжи 1-го, 2-го и 3-го типа соответственно; для ткани 2-го вида – 6, 8 и 9 мотков пряжи; для ткани 3-го вида – 1, 9 и 3 мотков пряжи; для ткани 4-го вида – 9, 8 и 4 мотков пряжи; для ткани 5-го вида – 2, 6 и 3 мотков пряжи; для ткани 6-го вида – 1, 2 и 7 мотков пряжи.

Предприятие продает каждый вид ткани по цене 1, 1, 9, 2, 3, 7 долл. за метр соответственно.

Сколько метров ткани каждого вида необходимо произвести за рабочий день, чтобы получить максимальную выручку, если можно израсходовать пряжи каждого типа 7, 7, и 7 мотков?

Обозначения математической модели:

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

- цена 1 м ткани каждого вида;

- имеющееся количество мотков пряжи каждого типа;

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

3. Определение оптимального решения модели

Применим симплексный алгоритм.

Шаг 1. Обозначим через значение целевой функции и введем остаточные переменные .

В результате получим систему уравнений (I):

,                (0)

               (1)

       (2)

       (3)

где .

Исходное базисное решение:

; ; .

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

Итерация 1

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

Шаг 3. Наибольшее возможное значение определяется уравнением (2), где отношение наименьшее.

Шаг 4. Замена опорного плана.

а) разделим строку (2) на 9

а) умножим строку (2) на 9 и результат прибавим к строке (0)

в) умножим строку (2) на (-1) и результат прибавим к строке (1)

г) умножим строку (2) на (-3) и результат прибавим к строке (3)

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

,                        (0)

               (1)

                       (2)

               (3)

Значения переменных нового базиса:

; , .

Прибыль увеличилась с 0 до за счет новой базисной переменной : .

Итерация 2

Шаг 2. Вводим в базис переменную, у коэффициент при которой в уравнении (0) отрицательный.

Шаг 3. Наибольшее возможное значение определяется уравнением (3), где отношение наименьшее.

Шаг 4. Замена опорного плана.

а) разделим строку (3) на 19/3

а) умножим строку (3) на 5 и результат прибавим к строке (0)

в) умножим строку (3) на (-7/9) и результат прибавим к строке (1)

г) умножим строку (3) на (-2/9) и результат прибавим к строке (2)

В результате получим систему уравнений (F):

,                (0)

               (1)

                       (2)

                       (3)

Итерация 3

Шаг 2. Так как в строке (0) все коэффициенты положительны, получено оптимальное решение:

; , .

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

Оптимальное решение модели:

;  .

4. Анализ модели на чувствительность

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

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

.

Тогда строка (0) заключительной системы уравнений (F) примет вид

.

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

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

,         ,  ,  .

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

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

Тогда строка (0) заключительной системы уравнений (F) примет вид

.        (0)

Если базис не изменился, необходимо исключить из (0).

Умножим строку (2) на и прибавим к (0).

В результате строка (0):

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

При становятся отрицательными коэффициент при и , при становится отрицательным коэффициент при .

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

.

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

,        (0)

Если базис не изменился, необходимо исключить из (0).

Умножим строку (3) на и прибавим к (0).

В результате строка (0):

При становится отрицательным коэффициент при , при становится отрицательным коэффициент при .

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

Без изменения оптимального плана коэффициенты при базисных переменных по отдельности могут изменяться в пределах:

;        .

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

.

Если базис не изменился, необходимо исключить и из (0).

Умножим строку (2) на , строку (3) на и прибавим к (0).

В результате строка (0):

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

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

Построим эту область графически:

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

Предположим, что правая часть строки (1) системы (I) получила приращение .

.                (1)

Остаточная переменная этой строки входит в базис и на первой, и на последней итерации. Поэтому строка (1) в системе (F) примет вид:

       (1)

а остальные строки не изменятся.

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

Предположим, что правая часть строки (2) системы (I) получила приращение .

.        (2)

Остаточная переменная этой строки входит в базис и на первой, но не входит на последней итерации. Заключительная система примет вид (F1):

,                (0)

               (1)

               (2)

                       (3)

Прежний оптимальный базис останется допустимым (и оптимальным) при

, , .

Отсюда получаем .

Предположим, что правая часть строки (3) системы (I) получила приращение .

.        (3)

Остаточная переменная этой строки входит в базис и на первой, но не входит на последней итерации. Заключительная система примет вид (F2):

,                (0)

               (1)

               (2)

                       (3)

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

Отсюда получаем .

Увеличение прибыли при изменении ресурсов на единицу равны коэффициентам при соответствующих остаточных переменных в строке (0) системы (F), то есть 0, 14/19 и 15/19 единиц.

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

;                ;        .

4.5. Пусть правые части строк (1) и (2) системы (I) получили приращение и .

.                (1)

.        (2)

Заключительная система примет вид (F3):

,                (0)

       (1)

               (2)

                       (3)

Прежний оптимальный базис останется допустимым (и оптимальным) при

, , .

Отсюда получаем

Построим эту область графически:

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

5.1. Задача, двойственная к исходной, имеет вид

Получаем:

5.2. Коэффициенты при остаточных переменных в строке (0) на последней

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

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

Строка (0) системы (F) решения исходной задачи:

.        (0)

Отсюда .

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

.

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

;  .

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

               

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

,         ,  ,  .

5.4. Вводятся новые управляемые переменные .

i	2	9	16	23
i	3	10	17	24

Тогда задача линейного программирования примет вид

В двойственной задаче добавятся неравенства

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

       или        

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

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

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

Предприятие производит шесть видов ткани из трех типов пряжи.

На изготовление одного метра ткани 1-го вида требуется 8, 6 и 6 мотков пряжи 1-го, 2-го и 3-го типа соответственно; для ткани 2-го вида – 6, 8 и 9 мотков пряжи; для ткани 3-го вида – 1, 9 и 3 мотков пряжи; для ткани 4-го вида – 9, 8 и 4 мотков пряжи; для ткани 5-го вида – 2, 6 и 3 мотков пряжи; для ткани 6-го вида – 1, 2 и 7 мотков пряжи.

Вечером в день производства предприятие продает каждый вид ткани по цене 1, 1, 9, 2, 3, 7 долл. за метр соответственно.

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

Сколько метров ткани каждого вида необходимо изготовить в каждый из трех рабочих дней, чтобы получить максимальную выручку, если утром первого дня имеется 7, 7, и 7 мотков пряжи; утром второго дня будет получено ещё 2, 4, и 4 мотков; утром третьего дня – ещё 3, 6 и 5 мотков?

Обозначения математической модели:

- количество метров произведенной ткани каждого вида в -й день;

- цена 1 м ткани каждого вида;

- количество мотков пряжи -го типа, необходимое для производства 1 м ткани -го вида;

- остаток пряжи каждого типа на конец -го дня;

- цена хранения одного мотка;

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

Модель линейного программирования в буквенных обозначениях:

.