Имеется множество переменных X= (x1, х2,..., хn). Целевая функция линейно зависит от управляемых параметров:
(1)
Имеются ограничения, которые представляют собой линейные формы
где 
(2)
Требуется определить максимум (минимум) линейной функции
(3)
при условии, что точка (х1, х2,..., хn) принадлежит некоторому множеству D, которое определяется системой линейных неравенств
(4)
Любое множество значений (х1*, х2*,..., хn*), которое удовлетворяет системе неравенств (4) задачи линейного программирования, является допустимым решением данной задачи. Если при этом выполняется неравенство
c1х1o+ c2 х2o+..+ cn хno ≥ c1х1+ c2 х2+..+ cn хn
для всего множества значений x1, х2,..., хn, то значение х1o..хno является оптимальным решением задачи линейного программирования.
Пример построения математической модели и решения ЗЛП.
Задача. Требуется определить, в каком количестве надо выпускать продукцию четырех типов A, B, C иD, для изготовления которой требуются ресурсы трех видов: трудовые, сырье и финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в таблице1. Там же приведено наличие располагаемого ресурса.
Таблица1.
| Ресурс | A | B | C | D | знак | наличие |
| трудовые | ≤ | |||||
| сырье | ≤ | |||||
| финансы | ≤ | |||||
| прибыль | max | - |
Составим математическую модель, для чего введем следующие обозначения:
xi - количество выпускаемой продукции i-го типа, i = 1,2,3,4
bj – количество располагаемого ресурса j-го вида, j = 1,2,3
aji – норма расхода j-го ресурса для выпуска i-ой продукции
ci – прибыль от реализации единицы продукции i-го типа.
Как видно из таблицы 1, для выпуска единицы продукции A требуется 6 единиц сырья, значит, для выпуска всей продукции A требуется 6 x1 единиц сырья, где x1 - количество выпускаемой продукции A. С учетом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид:
6 x1 + 5 x2 + 4 x3 + 3 x4 ≤ 110
В этом ограничении левая часть равна величине требуемого ресурса, а правая часть показывает количество имеющегося ресурса.
Аналогично можно составить ограничения для других видов ресурсов и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид:
x1 + x2 + x3 + x4 ≤ 16
6 x1 + 5 x2 + 4 x3 + 3 x4 ≤ 110
4x1 + 6 x2 + 10 x3 + 13 x4 ≤ 100
xi ≥ 0, i=1,2,3,4
Задания для лабораторной работы.
Составить математическую модель производственной системы: определить цель системы, сформировать план задачи (ситуационные переменные и ограничения) и сформировать целевую функцию.
Решить полученную задачу линейного программирования численно (или аналитически, если число ситуационных переменных равно 2.
Проверить устойчивость решения, варьируя оптимальные значения ситуационных переменных и ресурсов на 10% и сопоставляя полученные значения целевой функции с ее максимальным значением.