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

  • Просмотров 3310
  • Скачиваний 462
  • Размер файла 155
    Кб

Министерство общего и профессионального образования Российской Федерации Воронежский Государственный Архитектурно – Строительный Университет Кафедра Экономики и управления строительством ЛАБОРАТОРНАЯ РАБОТА На тему: «Решение задач линейного программирования» Выполнил: Студент 4 курса ФЗО ЭУС Сидоров В.В. Руководитель: Богданов Д. А. Воронеж – 2002 г. ЛАБОРАТОРНАЯ РАБОТА № 11 РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Цель

работы: изучение принципов составления оценочных характеристик для задач линейного программирования, получение навыков использования симплекс-метода для решения задач линейного программирования, усвоение различий получаемых результатов, изучение табличной формы применения симплекс-метода. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ Стандартная задача линейного программирования состоит из трех частей: целевой функции (на максимум или

минимум) - формула (1.1), основных oграничений - формула (1.2), ограничений не отрицательности переменных (есть, нет) - формула (1.3) (1.1) i = 1,… m (1.2) (1.3) Алгоритм решения задач линейного программирования требует приведения их постановки в канонический вид, когда целевая функция стремится к максимуму (если стремилась к минимуму, то функцию надо умножить на -1, на станет стремиться к максимуму), основные ограничения имеют вид равенства (для

приведения к равенствам в случае знака надо в правую часть каждогo такого k-го неравенства добавить искусственную переменную uk uk надо отнять ее из правой части основных ограничений), присутствуют ограничения не отрицательности переменных (если их нет для некоей переменной хk, то их можно ввести путем замены всех вхождений этой переменной комбинацией x1k - х2k = хk, где х1k и х2k базис, т.е. набор переменных хi, в количестве, равным числу

основных ограничений, причем чтобы каждая из этих переменных присутствовала лишь в одном основном oграничении и имела свой множитель аij = 1. Если таких переменных нет, то они искусственно добавляются в основные ограничения и получают индексы хm+1, xm+2 и т.д. Считается при этом, что они удовлетворяют условиям не отрицательности переменных. Заметим, что если базисные переменные (все) образуются в результате приведения задачи к