МИНИСТЕРСТВО ОБРАЗОВАНИЯ УКРАИНЫ
ЗАПОРОЖСКИЙ ИНСТИТУТ ЭКОНОМИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ
и варианты контрольных работ
Предисловие
Теория и методы линейного программирования используются для описания и решения задач, возникающих в различных областях человеческой деятельности. В частности, многие экономические ситуации могут быть описаны при помощи задач линейного программирования; в свою очередь, линейные модели получают естественную экономическую интерпретацию.
Линейное программирование как математическая дисциплина, разрабатывающая методы рационального распределения ограниченных ресурсов, является частью важного класса методов экономической теории, так называемых экстремальных методов. Присуждение Нобелевской премии по экономике академику Л. В. Канторовичу и американскому специалисту по математической экономике Т. Купмансу свидетельствует о признании роли экстремальных моделей в экономике.
Практическая деятельность требует от современного экономиста умения ставить и решать математические задачи большой размерности, что связано с использованием современных средств вычислительной техники.
Настоящие методические указания предназначены для студентов экономических специальностей и включают теоретическую и практическую части.
Изложены теоретические основы, постановка основной задачи линейного программирования, алгоритм симплексного метода. В пособие включены различные типы задач, рекомендуемых для лабораторного практикума по линейному программированию. В последнем разделе рассматривается математическая модель экономической ситуации, известной как транспортная задача, которая естественно приводит к формальной постановке задачи линейного программирования.
ОСНОВНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Теоретические сведения
Постановка задачи линейного программирования
Найти:
max F= 
(1.1)
x1,…,xn
при условиях:
a11x1 + a12x1 +...+a1nxn 
b1;
a21x1 + a22x2 +...+a2nxn b2;
…………………………………;
am1x1 + am2x2 +...+amnxn bm; (1.2)
и
x1 
x2 … xn (1.3)
где F= 
- целевая функция или эффективность системы (доход от
производства, объем перевезенных товаров и т.д.)
x1, …, xn - варьируемые параметры.
Расширенная форма задачи линейного программирования
Для решения задачи линейного программирования необходимо уметь переходить от ограничений в форме неравенств к равенствам. Для этого вводят свободные (дополнительные) переменные xn+1 xn+2 … xn+m 
, которые превращают неравенства в равенства.
В таком виде задачу линейного программирования называют расширенной и записывают так:
Найти
max(c1x1 + с2х2, +... +сnхn + 0. хn+1 + 0 . хn+2 + 0 . хm+n) (1.4)
при ограничениях
a11x1 + a12x2 +...+a1nxn + 1xn+1 + 0xn+2 + … + 0xm+n = b1;
a21x1 + a22x2 +...+a2nxn + 0xn+1 + 1xn+2 + … + 0xm+n = b2; (1.5)
am1x1 + am2x2 +...+amnxn + 0xn+1 + 0xn+2 + … + 1xm+n = bm;
и
x1 x2 … xn+m (1.6)
Существование решения основной задачи линейного программирования
Рассмотрим основную задачу линейного программирования (ОЗЛП) - найти неотрицательные значения переменных x1, x2,..., xn, удовлетворяющие m условиям (1.5) и обращающие в максимум линейную функцию этих переменных:
F = c1x1 + c2x2 + … + cnxn (1.7)
Для простоты предположим, что все условия (1.5) линейно независимы (r=m).
Если среди условий-равенств (1.5) есть вытекающие из других, то это обнаружится автоматически в процессе решения ОЗЛП.
Допустимым решением ОЗЛП называется всякая совокупность неотрицательных значений x1, x2,…, xn, удовлетворяющая условиям (1.5).
Оптимальным называется то из допустимых решений, которое обращает в максимум функцию (7).
Если в системе (1.5) выбрать т переменных, а остальные положить равными нулю, то полученное после этого решение системы называется опорным решением. Выбранные переменные называются базисными, а те, которые положим равными нулю, - свободными.
Если полученное решение содержит только положительные элементы, то оно называется опорным допустимым.
Если в опорном решении нет нулевых элементов, то опорное допустимое решение называется невырожденным.
Теорема о достижимости оптимума. Если целевая функция задачи линейного программирования на максимум (минимум) ограничена сверху (снизу) на допустимом множестве, то эта задача имеет оптимальное решение.
Иначе говоря, если существует верхняя (соответственно, нижняя) грань целевой функции на допустимом множестве, то она и достигается на нем.
Оптимальное решение ОЗЛП (если оно существует) достигается при такой совокупности значений переменных x1, x2,…, xn, где по крайней мере к из них обращается в нуль, а остальные положительны (к = n-m).