ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное образовательное учреждение высшего профессионального образования
«ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ»
Кафедра «Математика и моделирование»
М.М. Луценко
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
РЕШЕНИЕ ЗАДАЧИ
Методические указания и варианты индивидуальных заданий для студентов заочного факультета
САНКТ-ПЕТЕРБУРГ
УДК 512.8
М.М.Луценко
Линейное программирование. Решение задачи. Методические указания и варианты индивидуальных заданий для студентов заочного факультета, – СПб.: Петербургский государственный университет путей сообщения, 2006, 22 с.
Содержание пособия соответствует разделам математического программирования, изучаемым студентами в 3 семестре. Пособие предназначено для студентов специальностей УПП заочного факультета ПГУПС.
Рецензент: профессор В.В. Гарбарук (кафедра «Высшая математика» ПГУПС)
© М.М.Луценко
© Петербургский государственный университет
Постановка задачи
Главным объектом изучения в линейном программирование является задача, которая в наиболее общей форме формулируется следующем образом.
Задача. Найти экстремум линейной функции F, если ее аргументы удовлетворяют некоторым ограничениям.
Настоящие методические указания посвящены анализу задачи линейного программирования, даны ее различные формы записи и указаны некоторые способы ее решения.
Каждый студент должен будет сделать для своей задачи все ниже перечисленные действия.
1. Записать задачу в матричной форме
2. Записать каноническую задачу.
3. Решить задачу геометрически.
4. Найти начальный базисный план с помощью искусственных переменных.
5. Решить задачу симплекс-методом.
6. Написать двойственную задачу к искомой в матричной и развернутой формах.
7. Найти решение двойственной задачи и доказать его оптимальность с помощью теоремы двойственности.
Варианты задач и пример решения указаны в конце этих указаний.
Матричная и развернутая формы задачи линейного программирования
В этом параграфе мы сравним две формы записи задачи линейного программирования.
Определение 1. Следующая задача называется стандартной задачей линейного программирования.
Задача 1. Найти
, (1)
, 
, (2)
где A – матрица системы ограничений, имеющая m строк и n столбцов, b – столбец из m элементов; c, x – столбцы из n элементов. Таким образом, эти матрицы имеют вид
, 
, 
, 
. (3)
В развернутой форме эта стандартная задача линейного программирования может быть записана в следующем виде.
Задача 1’. Найти максимум линейной функции
, 
при ограничениях:
. 
Определение 2. Решением этих задач называется матрица (упорядоченный набор чисел) 
, удовлетворяющая системе ограничений (2) и обеспечивающая максимальное значение функции (1). Иногда это решение называется оптимальным планом задачи. Значение функции на оптимальном плане обозначается 
.
Определение 3. Линейная функция F задачи 1 называется целевой функцией, а множество D решений системы (2) – множеством допустимых решений (планов) этой задачи.
Пример 1. Записать задачу линейного программирования (1), (2) с матрицами
; 
; 
; 
в развернутой форме 
.
Решение. В развернутой форме задача формулируется следующим образом.
Найти максимум функции 
при ограничениях
.
Пример 2. Записать следующую задачу линейного программирования в матричной форме.
Минимизировать линейную функцию 
при ограничениях
.
Решение. Для того чтобы записать эту задачу в матричной форме (1, 2), изменим неравенства в ограничениях задачи так, чтоб они имели одинаковый знак. Для этого умножим первое неравенство на –1. Мы получим следующую систему ограничений задачи:
Тогда в матричной форме задача примет вид
,
, ,
где
; 
; 
; .