Математические основы информатики: Методическое пособие. Часть 2

1

Министерство образования Российской Федерации Нижегородский государственный университет им.Н.И.Лобачевского Факультет вычислительной математики и кибернетики

МЕТОДИЧЕСКОЕ ПОСОБИЕ по курсу «Математические основы информатики» для студентов факультета ВМК специальность "Прикладная информатика" Часть 2

Н.Новгород — 2004

2

Методическое пособие по курсу «Математические основы информатики» для студентов факультета ВМК, специальность "Прикладная информатика" Часть 2. / Нижег.гос.ун-т, 2004, с.24. В методическом пособии излагается материал по курсу лекций «Математические основы информатики», читаемых во втором семестре первого курса факультета ВМК. Вторая часть пособия содержит материалы курса, связанные с линейными оптимизационными моделями. Методическое пособие подготовлено профессором М.Х.Прилуцким.

3

СОДЕРЖАНИЕ 1. РАБОЧАЯ ПРОГРАММА КУРСА «МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ» .................................................................................. 4 ПРЕДИСЛОВИЕ ................................................................................................................................................. 4 СОДЕРЖАНИЕ КУРСА .................................................................................................................................... 5 МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ ................................................................................................................ 5 1. ЛИНЕЙНЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ................................................................................. 5 ЛИТЕРАТУРА (основная)................................................................................................................................ 6 ЛИТЕРАТУРА (дополнительная) .................................................................................................................... 6

2. ЗАДАЧНИК ПО КУРСУ...................................................................... 7 3. ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ ПО РАЗДЕЛУ «ЛИНЕЙНЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ» .................................................... 17 4. ВОПРОСЫ К ЭКЗАМЕНУ ............................................................... 23

4

1. РАБОЧАЯ ПРОГРАММА КУРСА «МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ» Часть 2. Специальность: «Прикладная нформатика»(35.14.00) Специализация: «Информационные системы обеспечения финансово-кредитной, юридической, управленческой и издательской деятельности» Форма обучения: очно-заочная. 1 курс: 2 семестр 2/1 ПРЕДИСЛОВИЕ

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

5

СОДЕРЖАНИЕ КУРСА МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ 1. ЛИНЕЙНЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ.

Понятие оптимизационных задач. Примеры формальных постановок оптимизационных задач. Эквивалентные формы записи задач линейного программирования Геометрический смысл задач линейного программирования. Графическое решение задач линейного программирования. Теорема о выпуклости множества допустимых решений задачи линейного программирования. Теорема о выпуклости множества оптимальных решений задач линейного программирования. Симплекс метод решения задач линейного программирования. Искусственное начальное решение в задаче линейного программирования. Особые случаи применения симплекс-метода. Двойственность. Двойственные задачи линейного программирования для различных форм. Лемма о соотношениях линейных форм. Лемма о равенстве линейных форм. Лемма о взаимодвойственности систем линейных однородных алгебраических уравнений. Основная теорема двойственности. Следствие из основной теоремы двойственности о связи оптимальных решений прямой и двойственной задач линейного программирования. Теорема равновесия. Интерпретация двойственных оценок. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ ЛИНЕЙНЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ.

1.Различные эквивалентные формы записи задач линейного программирования. Геометрическая интерпретация. 2.Симплекс метод решения задач линейного программирования. 3.Искусственное начальное решение. 4.Особые случаи применения симплекс метода. 5.Двойственные задачи линейного программирования. 6.Связь оптимальных решений прямой и двойственной задач. 7.Двойственные оценки. Их интерпретация.

6

ЛИТЕРАТУРА (основная)

1.Ашманов С.А.Линейное рограммирование. М.:Наука,1981. 2.Ляшенко И.И., Шор Н.З. и др.Линейное и нелинейное программирование. Киев, Высшая школа, 1975. ЛИТЕРАТУРА (дополнительная)

1.Ромакин М.И. Элементы линейной алгебры и линейного программирования. М. Высшая школа, 1963. 2.Таха Х. Введение в исследование операций. М. Мир,1985,Том 1. 3.Вагнер Г. Основы исследования операций. М. Мир, 1972, том 1. 4.Акулич И.Л. Математическое программирование в примерах и задачах. Учебное пособие для ВУЗов. М. Высшая школа, 1986. 5.Кузнецов А.В.,Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию.Минск, Высшая школа,1978.

7

2. ЗАДАЧНИК ПО КУРСУ ЗАДАЧА 1 X1 + X 2 ≥ 2 X1 + 3 X2 ≤ 15 2X1 + X2 ≤ 10 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(2X1- X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 2 X1 + X 2 ≥ 2 X1 + 2X2 ≤ 10 3X1 + X2 ≤ 15 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(2X1+ X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 3

8

X1 + X 2 ≥ 2 X1 + 2X2 ≤ 12 5 X1 + 3X2 ≤ 25 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(2X1+ X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи.

ЗАДАЧА 4 X1 + X 2 ≥ 2 X1 + X 2 ≤ 7 5X1 + 3X2 ≤ 25 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(2X1+ X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 5 X1 + X 2 ≥ 2 X1 + 2X2 ≤ 12 5X1 + 4X2 ≤ 30 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(2X1+ 3X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 6 X1 + X 2 ≥ 2

9

X1 + 2X2 ≤ 15 5X1 + 3X2 ≤ 10 (1) X1 ≥ 0, X ≥ 20 F(x)=max(2X1+ 3X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи.

ЗАДАЧА 7 3X1 + 2X2 ≥ 6 X1 + 2X2 ≤ 16 5X1 + 2X2 ≤ 40 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(3X1+ 2X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 8 3X1 + 2X2 ≥ 6 X1 + 2X2 ≤ 16 5X1 + 3X2 ≤ 45 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(3X1+ 2X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 9 3X1 + 2X2 ≥ 6

10

X1 + 2X2 ≤ 16 5X1 + X2 ≤ 35 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(3X1+ 2X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи.

ЗАДАЧА 10 3X1 + 2X2 ≥ 6 5X1 + 2X2 ≤ 40 2X1 + 3X2 ≤ 40 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(3X1+ 2X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 11 3X1 + 2X2 ≥ 6 5X1 + 2X2 ≤ 40 5 X1 + 6X2 ≤ 60 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(3X1+ 2X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 12 3X1 + 2X2 ≥ 6

11

5X1 + 3X2 ≤ 45 5X1 + 6X2 ≤ 60 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(3X1+ 2X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи.

ЗАДАЧА 13 2X1 + X2 ≥ 4 -X1 + X2 ≤ 1 2X1 + X2 ≤ 10 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(2X1+ 4X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 14 2X1 + X2 ≥ 4 -X1 + X2 ≤ 1 4X1 + 3X2 ≤ 24 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(2X1+ 4X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 15 2X1 + X2 ≥ 4

12

-X1 + X2 ≤ 1 4X1 + X2 ≤ 16 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(2X1+ 4X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи.

ЗАДАЧА 16 X1 + 3X2 ≥ 3 -X1 + X2 ≤ 1 4X1 + 3X2 ≤ 24 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(-2X1+ 3X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 17 X1 + 3X2 ≥ 3 -X1 + X2 ≤ 1 X1 + X2 ≤ 7 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(-2X1+ 3X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 18 X1 + X 2 ≥ 4

13

-X1 + X2 ≤ 1 2X1 + X2 ≤ 10 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(2X1+ 4X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи.

ЗАДАЧА 19 X1 + 3X2 ≥ 4 -X1 + X2 ≤ 1 2X1 + X2 ≤ 10 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(-2X1+ 3X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 20 X1 + 8X2 ≥ 8 3X1 + 2X2 ≤ 24 -5X1 + 4X2 ≤ 4 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max( 3X1+ 2X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 21 X1 + 8X2 ≥ 8

14

X1 + X2 ≤ 10 -5X1 + 4X2 ≤ 4 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max( 3X1+ 2X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи.

ЗАДАЧА 22 X1 + 8X2 ≥ 8 -X1 + 3X2 ≤ 14 -5X1 + 4X2 ≤ 4 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max( 3X1+ 2X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 23 X1 + 4X2 ≥ 4 -X1 + 3X2 ≤ 14 -5X1 + 4X2 ≤ 4 (1) X1 ≥ 0, X2 ≥ 0 F(x)=min( 3X1+ 2X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 24 X1 + X2 ≤ 10

15

X1 + 8X2 ≥ 8 -5X1 + 4X2 ≤ 4 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max( 3X1+ 2X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи.

ЗАДАЧА 25 -X1 + X2 ≤ 1 X1 + X2 ≤ 10 (1) X1 + 8X2 ≥ 8 X1 ≥ 0, X2 ≥ 0 F(x)=max( 3X1+ 2X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 26 3X1 + 2X2 ≤ 24 X1 + 8X2 ≥ 8 -5X1 + 4X2 ≤ 4 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max( 3X1+ 2X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 27 3X1 + 2X2 ≤ 24

16

X1 + X 2 ≥ 1 -4X1 + 3X2 ≤ 12 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(-2X1+ 3X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи.

ЗАДАЧА 28 2X1 + X2 ≥ 4 -X1 + X2 ≤ 1 2X1 —3X2 ≤ 1 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max(2X1+ 4X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 29 X1 + 8X2 ≥ 8 X1 + X 2 ≤ 5 5X1 + 4X2 ≥ 4 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max( 3X1+ 2X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. ЗАДАЧА 30 X1 + 4X2 ≥ 4

17

-X1 + 3X2 ≤ 14 -5X1 + 4X2 ≤ 4 (1) X1 ≥ 0, X2 ≥ 0 F(x)=max( 6X1+ X2) 1.Построить двойственную задачу к задаче (1). 2.Решить симплекс-методом задачу (1) или двойственную к ней. 3.По оптимальному решению одной из задач найти оптимальное решение другой задачи. 3. ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ ПО РАЗДЕЛУ «ЛИНЕЙНЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ»

1.Дать содержательное описание объекта, проинтерпретировать исходные параметры и варьируемые параметры. 2.Содержательно поставить оптимизационную задачу. 3.Построить общую математическую модель при условиях: — все ограничения математической модели линейные, — в модели присутствуют ограничения типа «больше или равно», — в модели присутствуют ограничения типа «меньше или равно», — в модели присутствуют ограничения типа «равно», — среди неизвестных присутствуют не ограниченные в знаке. 4.Поставить оптимизационную задачу, формализовав критерий оптимальности в виде линейного функционала. 5.Предложить свои исходные данные для случая, когда всех переменных не меньше 7, всех ограничений не меньше 6 и не менее чем одна переменная неограничена в знаке. 6.При заданных исходных данных построить математическую модель и поставить оптимизационную задачу. 7.Решить на ПЭВМ поставленную задачу. 8.Привести задачу к каноническому виду и решить ее на ПЭВМ. 9.Проинтерптетировать полученные значения искусственных

18

переменных. 10.Построить двойственную задачу. Решить ее на ПЭВМ. 11.Проинтерпретировать полученные значения двойственных переменных. 12.Написать отчет по курсовой работе. Пример. 1.Содержательное описание объекта. Предприятие выпускает продукцию нескольких наименований используя определенные количества ресурсов двух типов: 1 тип —складируемые ресурсы ( срок годности превышает величину планируемого периода), 2 тип —нескладируемые ресурсы, которые либо используются полностью в планируемом периоде, либо, при их недостатке, дополнительно приобретаются, либо, при их избытке, реализуются. Заданы величины ожидаемых доходов от производства каждого вида продукции; величина суммарного дохода, которым должно быть обеспечено производство; стоимость единицы каждого вида нескладируемого ресурса, предполагая, что эта стоимость одинакова и при его покупке и при его продаже. 2.Содержательная постановка задачи. Найти план производства продуктов, обеспеченый ресурсами, выполнение которого принесет максимальную ожидаемую прибыль. 3.Общая математическая модель. 3.1.Исходные параметры модели. i=1,2,...,m —номера продуктов, j=1,2,...,n —номера складируемых ресурсов, k=1,2,...,s —номера нескладируемых ресурсов, b(j) —объем j-го складируемого ресурса, имеющийся у предприятия, j=1,2,...,n, d(k) —объем k-го нескладируемого ресурса, имеющийся у предприятия, k=1,2,...,s, R=(r(i,j)) —матрица ресурсоемкостей по складируемым ресурсам, где r(i,j) —количество ресурса j, необходимое для производства единицы i-го вида продукции,i=1,2,...,m, j=1,2,...,n. Q=(q(i,k)) —матрица ресурсоемкостей по нескладируемым ресурсам, где q(i,k) —количество ресурса k, необходимое для производства единицы i-го вида продукции,i=1,2,...,m, k=1,2,...,s.

19

с(i) —величина ожидаемого дохода от производства единицы продукции i-го вида, i=1,2,...,m. G —величина минимального ожидаемого суммарного дохода, который предприятие должно получить в планируемом периоде за счет производства продукции, p(k) —стоимость покупки или продажи единицы k-го нескладируемого ресурса. 3.2.Варьируемые переменные. x(i) —количество продукта с номером i, которое предприятие будет выпускать в планируемом периоде, i=1,2,...,m. y(k) — количество нескладируемого ресурса с номером k, которое предприятие будет дополнительно приобретать (тогда величина y(k) —отрицательная) или продавать (тогда величина y(k) — положительная). 3.3.Ограничения математической модели.

m ∑ r(i, j)x(i, j)≤ b( j) . i =1

j=1,2,...,n, (1)

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

m ∑ q(i,k) x(i) + y(k) = d(k) , i =1

k=1,2,...,s, (2)

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

m ∑ с(i) x(i) ≥G, (3) i =1 (Должна быть обеспечена величина минимального ожидаемого суммарного дохода, который предприятие получит в

20

планируемом периоде за счет производства продукции.) x(i)

≥

0, i=1,2,...,m, (4)

y(k) —не ограничены в знаке, k=1,2,...,s. (Естественные условия на переменные.) Исходные, варьируемые переменные и ограничения (1)-(4) представляют собой искомую математическую модель. В ней n ограничений типа »меньше или равно», s ограничений типа «равно», одно ограничение типа «больше или равно», m неотрицательных переменных и s переменных, не ограниченных в знаке. 4.Постановка оптимизационной задачи m s max F(x,y)= max( ∑ с(i) x(i) + ∑ p(k) y(k) ). k =1 i =1

(5)

(Общий суммарный ожидаемый доход от производства продукции и продажи остатков нескладируемых ресурсов (или покупки недостающих нескладируемых ресурсов) должен быть максимален.) 5.Конкретные значения исходных параметров задачи. m=4 —количество различных продуктов, n=2 —количество складируемых ресурсов, s=1 —количество нескладируемых ресурсов, b(1)=35, b(2)=84 —объемы складируемых ресурсов, имеющихся у предприятия, d(1)=38 —объем нескладируемого ресурса, имеющийся у предприятия, 5 6 R=(r(i,j))= 3 9 i=1,2,3,4 j=1,2 6 8 2 7 матрица ресурсоемкостей по складируемым ресурсам, где, например, элемент r(1,1)=5 —означает, что для производства единицы первого продукта необходимо 5 единиц складмруемого ресурса с номером 1. 3 Q=(q(i,k))= 3 i=1,2,3,4 k=1

21

6 4 матрица (вектор) ресурсоемкостей по нескладируемому ресурсу, с(1)=3, с(2)=5, с(3)=8, с(4)=12 —величины ожидаемых доходов от производства разных видов продукции, G=50 —величина минимального ожидаемого суммарного дохода, который предприятие должно получить в планируемом периоде за счет производства продукции, p(1)=6 —стоимость покупки или продажи единицы нескладируемого ресурса. 6.Математическая модель и постановка оптимизационной задачи. Варьируемыми параметрами являются: x(1), x(2), x(3), x(4) — количества продуктов, которые будут выпущены в планируемом периоде, y количеств нескладируемого ресурса, которое будет приобретено (отрицательное значение переменной y) или продано (положительное значение переменной y). Ограничения математической модели: 5x(1)+3x(2)+6x(3)+ 2x(4) ≤ 35, (6) 6x(1)+9x(2)+8x(3)+ 7x(4) ≤ 84, (7) 3x(1)+3x(2)+6x(3)+ 4x(4) + y = 38, (8) 3x(1)+5x(2)+8x(3)+12x(4) ≥ 50, (9) x(1) ≥ 0, x(2) ≥ 0, x(3) ≥ 0, x(4) ≥ 0, (10) переменная y - не ограничена в знаке. (11) maxF(x,y)=max(3x(1)+5x(2)+8x(3)+12x(4)+6y). (12) Здесь ограничения (6),(7) —ограничения на складируемые ресурсы, (8) —ограничение на нескладируемый ресурс, (9) — ограничение на ожидаемый доход от производства продуктов, (10),(11) —естественные ограничения на переменные, критерий (12) —максимизация суммарного дохода, который получит предприятие. Пункт 7 выполняется на ПЭВМ. 8.Канонический вид задачи. 5x(1)+3x(2)+6x(3)+2x(4)+x(5) = 35, (13) 6x(1)+9x(2)+8x(3)+7x(4)+x(6) = 84, (14) 3x(1)+3x(2)+6x(3)+4x(4)+y(1)-y(2) = 38, (15) 3x(1)+5x(2)+8x(3)+12x(4)+x(7) = 50, (16) x(1) ≥ 0, x(2) ≥ 0, x(3) ≥ 0, x(4) ≥ 0, (17)

22

x(5) ≥ 0, x(6) ≥ 0, x(7) ≥ 0, y(1) ≥ 0, y(2) ≥ 0. maxF(x,y)=max(3x(1)+5x(2)+8x(3)+12x(4)+6y(1)-6y(2)). (18) Здесь y=y(1)-y(2) 9.Проинтерпретировать полученные значения искусственных переменных. После решения канонической задачи. 10.Построить двойственную задачу. Решить ее на ПЭВМ. Двойственная задача имеет вид: 5z(1)+6z(2)+3z(3)+3z(4) ≥ 3 3z(1)+9z(2)+3z(3)+5z(4) ≥ 5 6z(1)+8z(2)+6z(3)+8z(4) ≥ 8 2z(1)+7z(2)+4z(3)+12z(4) ≥ 12 z(1) ≥ 0, z(2) ≥ 0, z(3) ≥ 6, -z(3) ≥ -6, z(4) ≥ 0. minT(z)=min(35z(1)+84z(2)+38z(3)+50z(4)) 11.Проинтерпретировать полученные значения двойственных переменных после решения задачи на ПЭВМ.

23

4. Вопросы к экзамену 1. Понятие оптимизационных задач. 2. Примеры формальных постановок оптимизационных задач. 3. Эквивалентные формы записи задач линейного программирования 4. Геометрический смысл задач линейного программирования. 5. Графическое решение задач линейного программирования. 6. Теорема о выпуклости множества допустимых решений задачи линейного программирования. 7. Теорема о выпуклости множества оптимальных решений задач линейного программирования. 8. Симплекс метод решения задач линейного программирования. 9. Искусственное начальное решение в задаче линейного программирования. 10. Особые случаи применения симплекс-метода. 11. Двойственность. Двойственные задачи линейного программирования для различных форм. 12. Теорема о соотношениях линейных форм. 13. Теорема о равенстве линейных форм. 14. Теорема о взаимодвойственности систем линейных однородных алгебраических уравнений. 15. Основная теорема двойственности. 16. Следствие из основной теоремы двойственности о

24

связи оптимальных решений прямой и двойственной задач линейного программирования. 17. Теорема равновесия. 18. Интерпретация двойственных оценок. 19. Двойственный симплекс-метод. 20. Обобщенный симплекс метод. 21. Прямо-двойственный симплекс-метод.