Методы линейного программирования

Министерство науки и высшего образования Российской Федерации

ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ (НИУ)

Кафедра систем автоматического управления

2023/24 учебный год

Курсовая работа

по дисциплине «Исследование операций»

Тема: Методы линейного программирования

Исполнитель:

Группа:          

Руководитель:

к.т.н., доцент А.А. Брагина

2024

Кафедра систем автоматического управления

2023/24 учебный год

ЗАДАНИЕ

на курсовую работу по дисциплине «Исследование операций»

Тема: Методы линейного программирования

Цель работы:

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

[pic 1]

1. Предполагая, что данная задача имеет решение, найти ее оптимальные решения (min f и max f) на оптимальных планах (x*min и x*max) графически, двумя способами в разных системах координат, проставив на чертеже у каждой угловой точки соответствующий ей номер. Найти интервалы изменения коэффициентов целевой функции, в которых оптимальное решение задачи остается неизменным.

2. Решить исходную задачу двухфазным симплекс методом, найдя min f  и max f.

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

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

5. Проверить найденный методом Гомори план на оптимальность по критерию Канторовича.

ВАРИАНТ

1. [pic 2]

Решение каждой задачи обосновать элементами теории*

Исполнитель

Студент гр. КЭз-395                            _________________                А.О. Астахов

(подпись)

Руководитель к.т.н., доцент                _________________                 А.А. Брагина

(подпись)

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

Оглавление

Введение        4

1. Решение задачи графическим методом        5

2. Решение задачи двухфазным симплекс методом        20

3. Решение задачи с условием целочисленности методом Гомори        25

4. Решение двойственной задачи с помощью критерия Канторовича        29

5. Проверка критерия Канторовича для решения методом Гомори        33

Заключение        35

Список литературы        36

Введение

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

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

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