Исследование множества опорных планов системы ограничений задачи линейного программирования (задачи ЛП) в канонической форме

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«Белгородский Государственный Технологический Университет им. В.Г. Шухова»
(БГТУ им. В.Г. Шухова)

ИМ

Кафедра: «Программное обеспечение вычислительной техники и
автоматизированных систем»

Лабораторная работа №1

дисциплина: «Методы оптимизации»

тема: «Исследование множества опорных планов системы ограничений задачи линейного программирования (задачи ЛП) в канонической форме»

Вариант 10

Выполнил:
студент группы МИВТ-191

Маньшин И.М.

Принял:

проф. кафедры ПОВТиАС
Брусенцев А.Г.

Белгород, 2019

Цель работы: изучить метод Гаусса-Жордана и операцию замещения, а также освоить их применение к отысканию множества допустимых базисных видов системы линейных уравнений, и решению задачи линейного программирования простым перебором опорных решений.

Задания к работе

1. Составить программу для отыскания всех базисных видов системы линейных уравнений.

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

3. Решить одну из следующих ниже задач вручную (подготовить тестовые данные).

[pic 1]

Выполнение

Составим расширенную матрицу и приведем ее к базисному виду, выбрав [pic 2], [pic 3] и [pic 4]базисными переменными:

[pic 5]

[pic 6]

Таким образом система эквивалентная исходной имеет следующий вид:

[pic 7]

Полагая, свободные неизвестные равными нулю, получается базисное решение:

[pic 8]

Для просмотра всех базисных решений был разработан алгоритм (рис. 1) и написана программа, реализующая получение всех базисных видов, отбор опорных решений и нахождение оптимального решения:

[pic 9]

Рис. 1. Блок-схема алгоритма работы программы в укрупненных блоках

Результаты выполнения программы:

[pic 14][pic 15]

Вывод: в ходе выполнения лабораторной работы был изучен метод Гаусса-Жордана и операция замещения, а также были освоены их применение к отысканию множества допустимых базисных видов системы линейных уравнений, и решению задачи линейного программирования простым перебором опорных решений.