Линейное программирование (Графический метод. Симплексный метод) (стр. 3 )

Доход от реализации всех изделий вида П1 равен ден. единиц, тогда общий доход предприятия составит .

Итак, экономико-математическая модель задачи имеет вид: требуется найти такие неотрицательные значения х1, х2, …,хn, удовлетворяющие ограничениям

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

Функция z выражает конечную цель оптимального планирования, поэтому функцию называют целевой.

Задача «о диете»

Рассмотрим условную ситуацию. Дневная диета содержит m видов различных питательных веществ соответственно не менее условных единиц. Имеется n различных видов продуктов , каждый из которых содержит m видов питательных веществ, например, жиров, белков, углеводов. Обозначим - содержание в весовых единицах i-го питательного вещества в единице веса j-го продукта, - стоимость единицы веса продукта с номером j. Определить состав и количество продуктов, необходимых для включения в диету. При этом минимальные суточные потребности должны быть удовлетворены с минимальными денежными затратами. Сведем данные условия в таблицу 1.4.

Таблица 1.4 – Исходная информация задачи о диете

Вид питательного вещества	Вид продукта	Минимальная суточная потребность в питательном веществе, усл. ед.
		…		…
			…		…
			…		…
…	…						…
			…		…
…	…						…
			…		…
Стоимость единицы веса продукта			…		…

Составим экономико-математическую модель задачи.

Введем обозначения:

x1- количество потребления продукта вида ;

x2- количество потребления продукта вида ;

…

xn - количество потребления продукта вида в сутки.

В результате потребления ед. продукта вида содержание питательного вещества S1 в суточной норме потребления составит a11x1 усл. единиц. Общее содержание питательного вещества S1 в рационе определяется выражением . Поскольку содержание питательного вещества S1 в рационе не должно быть меньше минимальной суточной потребности организма, т. е. величины , то должно выполняться неравенство . В общем виде, содержание i-го питательного вещества в рационе не должно быть меньше , поэтому необходимо выполнение неравенства . Выполнение подобных ограничений описывает требование к диете, которое разрешает потреблять каждый вид питательного вещества в объеме не менее минимальной суточной потребности организма.

Кроме того, , так как количество потребляемых продуктов не может быть отрицательным числом.

Стоимость всего рациона определяет линейная функция .

Итак, экономико-математическая формулировка задачи «о диете» имеет вид: найти неотрицательные значения переменных х1, х2, …,хn, удовлетворяющих условиям

и минимизирующих функцию .

1.3 Формы задач линейного программирования, их эквивалентность и способы преобразования

Модель задачи линейного программирования может быть записана в одной из следующих форм:

Общая форма

Симметричная, или стандартная форма задачи линейного программирования

Каноническая, или основная форма задачи линейного программирования

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

Определение 2 Множество всех допустимых решений задачи линейного программирования называется областью (множеством) допустимых решений.

Определение 3 Допустимое решение, при котором целевая функция задачи линейного программирования принимает наибольшее (наименьшее) значение, называется оптимальным решением задачи линейного программирования () или оптимальным планом.