Введение

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

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

1. Задание и требования по выполнению расчетно-графической работы

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

1.1. Поиск оптимального решения задачи линейного программирования на основе геометрической интерпретации.

1.2. Поиск оптимального решения задачи линейного программирования на основе табличного симплекс-метода.

1.3. Решение транспортной задачи линейного программирования по критерию стоимости на основе метода потенциалов.

1.4. Решение задачи квадратичного программирования на основе условий Куна-Таккера.

Исходные данные для выполнения РГР приведены в прил. 1 табл. П1П4.

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

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

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

2.1. Аннотация, которая должна давать краткую характеристику всей работы.

2.2. Содержание .

2.3. Введение, отражающее постановку задачи по выполнению РГР и цель работы.

2.4. Исходные данные.

2.5. Расчетная часть как основной элемент работы, раскрывающая поз. 1.11.4.

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

2.7. Список используемой литературы.

Расчетно-пояснительная записка должна быть выполнена и оформлена в соответствии с требованиями ЕСКД (написана черными чернилами или отпечатана на принтере на листах А4), ориентировочный объем записки 1215 л.

3. Краткая характеристика методов решения задач оптимизации

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

3.1.1. Математические модели задач линейного программирования

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

найти решение Х={x₁, x₂, …, x_n}, доставляющее максимум (минимум) целевой функции

(3.1)

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

(3.2)

(3.3)

Условия (3.2) могут быть равенствами или иметь знак , а также быть смешанными.

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

F(X)=C^TX→max (min) (3.4)

При А₁х₁+А₂х₂+…+А_nх_n В, (3.5)

Х 0, (3.6)

где С^Т=(с₁, с₂,…, с_n); Х^Т=(х₁, х₂,…, х_n);

С вектор весовых коэффициентов целевой функции; Хвектор переменных; А_iвектор условий; Ввектор свободных коэффициентов ограничений (3.2).

Запись задачи (3.1) - (3.3) в матричной форме

F(X)=C^TX→max(min) (3.7)

AX В, (3.8)

Х 0, (3.9)

где матрица условий размера (mn).

Задачу (3.1) - (3.3) можно представить также в сокращенной форме записи

(3.10)

п ри

(3.11)

(3.12)

Вектор Х=(x₁, x₂, …, x_n), удовлетворяющий ограничениям задачи ЛП (3.2), называется решением. При Х 0 полученное решение называется допустимым. Если Х обращает в максимум (минимум) целевую функцию F(X), решение называется оптимальным.