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

Для производства 5 видов продукции употребляют три вида ресурсов. Припасы ресурсов, нормы расхода и цены реализации единицы каждого вида продукции приведены в таблице:

Вид ресурсов Нормы расхода сырья на единицу продукции Припасы
I вид II вид III вид IV вид V вид
Сырье 1
Сырье 2
Производственная мощность
Прибыль

Требуется отыскать таковой Рассмотрим пример задачи линейного программирования план выпуска продукции, при котором будет наибольшей общей цена продукции.

Экономико-математическая модель задачки будет иметь вид:

Мотивированная функция – это выражение, которое нужно максимизировать:

Ограничения по ресурсам

Неравенство обращают в равенства, добавляя дополнительные переменные

Дополнительные переменные демонстрируют количество соответственного неиспользованного сырья, которое может остаться на складе.

К примеру,

х6 - количество неиспользованного Рассмотрим пример задачи линейного программирования сырья первого вида;

х7 - количество неиспользованного сырья второго вида;

х8 - неиспользованная мощность предприятия.

Дополнительные переменные х6 ,х7, х8 не содействуют повышению прибыли, потому что не участвуют в производстве, потому в функции цели F(x) эти переменные записываются с коэффициентом, равным нулю.

Составим симплекс таблицу:

В столбце сj записывают нули, потому Рассмотрим пример задачи линейного программирования что за базис принимают дополнительные переменные, которые равны соответственно 2700, 1000,1000.

Таблица 1

№ с.-т. сj
Б Х0 Х1 Х2 Х3 Х4 Х5 Х6 Х7 Х8
Х6
Х7
Х8

В столбце xj xj проставляют коэффициенты при соответственных неведомых в уравнениях.

Значение последней строчки F(x) выходит при вычислении разности меж суммой Рассмотрим пример задачи линейного программирования произведений частей столбца Сj для базовых переменных на надлежащие элементы столбца xj (j=1, 2, …,8) и значением Сj в линейном функционале F(x) для данной переменной.

Найдем оценки столбцов по формуле:

Для последующих столбцов

Таблица 2

№ с.-т. сj
Б Х0 Х1 Х2 Х3 Х4 Х5 Х6 Х7 Х8
Х6
Х7
Х8
F Рассмотрим пример задачи линейного программирования(x) -5 -3 -4 -6 -4

Переменную, которая находится в жирной колонки Таблицы 2., вводят в базис, потому что она содействует большему повышению прибыли.

Таковой переменной в этом случае является Х4, у которой значение F(x) равно -6.

Чтоб узнать, какую переменную нужно удалить из базиса для введения Х4, находят положительные значения делением соответственных частей столбца Х0 на элементы Рассмотрим пример задачи линейного программирования главного столбца (на ноль и отрицательные числа главного столбца не делят).

Таблица 3

№ с.-т. сj
Б Х0 Х1 Х2 Х3 Х4 Х5 Х6 Х7 Х8
Х6
Х7
Х8 5
F(x) -5 -3 -4 -6 -4

Посреди выбирают меньшее положительное (i =1, 2, 3- номера строк).

Главная строчка указывает, что нужно вывести переменную Х8.

После составления начальной Рассмотрим пример задачи линейного программирования программки приступают к последующей.

В таблицу 3 в базисе Х6, Х7, Х4 ( введена заместо Х8 со значением С4 = +6).

Конвертируют главную строчку, производя деление частей главный строчки на главный элемент Таблицы 3.

Итог записывают в шестую строчку таблицы 3.

Это правило можно представить в виде формулы:

Заполняют шестую строчку таблицы 4 для Рассмотрим пример задачи линейного программирования столбца Х0

где 1000 – элемент столбца Х0 в 3 строке;

4 – главный элемент, лежащий на скрещении 3 строчки и 4 столбца.

Для небазисных переменных последующих столбцов:


Таблица 4

№ с.-т. сj
Б Х0 Х1 Х2 Х3 Х4 Х5 Х6 Х7 Х8
Х6
Х7
Х4 0,25 1,25 0,25 0,25
F(x)

Другие значения для других строк определяются по последующей формуле:

= - ´ Рассмотрим пример задачи линейного программирования;

Главный элемент преобразуемой строчки лежит на скрещении преобразуемой строчки и главного столбца (смотри Таблицу 3).

Элемент перевоплощенной главный строчки берется в том же столбце Хj (j=1, 2, …,8), для которого определяют новый элемент в новейшей таблице 5.

Заполняют первую строчку для базовой и небазисных переменных.

Таблица 4

№ с.-т. сj
Б Х0 Х Рассмотрим пример задачи линейного программирования1 Х2 Х3 Х4 Х5 Х6 Х7 Х8
Х6 -5 1,5 -6,5 0,5 -2,5
Х7
Х4 0,25 1,25 0,25 0,25
F(x)


Аналогично вычисляют 5 строчку:

Таблица 5

№ с.-т. сj
Б Х0 Х1 Х2 Х3 Х4 Х5 Х6 Х7 Х8
Х6 -5 1,5 -6,5 0,5 -2,5
Х7 2,5 -1,5 2,5 -0,5
Х4 0,25 1,25 0,25 0,25
F(x)

Значение последней строчки F(x) выходит при вычислении разности меж суммой произведений частей столбца Сj для Рассмотрим пример задачи линейного программирования базовых переменных на надлежащие элементы столбца xj (j=1, 2, …,8) и значением Сj в линейном функционале F(x) для данной переменной.

Найдем оценки столбцов по формуле (таблица :

Для последующих столбцов

Таблица 6

№ с.-т. сj
Б Х0 Х1 Х2 Х3 Х4 Х5 Х6 Х7 Х8
Х6 -5 1,5 -6,5 0,5 -2,5
Х7 2,5 -1,5 2,5 -0,5
Х4 0,25 1,25 0,25 0,25
F(x) -1,5 3,5 -2,5 1,5

Переменную, которая находится в жирной Рассмотрим пример задачи линейного программирования колонки Таблицы 6., вводят в базис, потому что она содействует большему повышению прибыли.

Чтоб узнать, какую переменную нужно удалить из базиса для введения Х5, находят положительные значения делением соответственных частей столбца Х0 на элементы главного столбца (на ноль и отрицательные числа главного столбца не делят).

Таблица 7

№ с.-т. сj Рассмотрим пример задачи линейного программирования
Б Х0 Х1 Х2 Х3 Х4 Х5 Х6 Х7 Х8
Х6 -5 1,5 -6,5 0,5 -2,5
Х7 2,5 -1,5 2,5 -0,5
Х4 0,25 1,25 0,25 0,25
F(x) -1,5 3,5 -2,5 1,5

Посреди выбирают меньшее положительное (i =1, 2, 3- номера строк).

Главная строчка указывает, что нужно вывести переменную Х5.

После выбора главный строчки и главного столбца перебегаем к наполнению последующей симплексной таблицы (Таблицы 8).

Стоит отметить, что в ней Рассмотрим пример задачи линейного программирования значения линейной функции F(x) увеличивается до 1500, предпосылкой чего служит переменная Х4, которая вошла в базис.

Экономический смысл нового допустимого плана приведенного в таблице 8, заключается в том, что по нему рекомендуется создавать продукцию Б4 в объеме 259 ед.

№ с.-т. сj
Б Х0 Х1 Х2 Х3 Х4 Х5 Х6 Х7 Х Рассмотрим пример задачи линейного программирования8
Х6 -5,2 -6,2 -0,2 -2,4
Х5 0,4 -0,6 0,4 -0,2
Х4 0,9 1,4 -0,1 0,3
F(x)

При переходе от одной симплексной таблице к другой вероятны последующие случи:

1. Если F(x) имеет отрицательные числа, над которыми имеются положительные элементы, то программка просит улучшения;

2. Если F(x) имеет отрицательные числа нет положительных частей, то максимум F(x) находится в Рассмотрим пример задачи линейного программирования бесконечности (задачке не решается);

3. Если нет не 1-го значения F(x)<0, то максимум F(x) достигнут (задачка решена).

В Таблице 8 в строке F(x) нет отрицательных чисел, потому достигнут максимум F(x) при

Х5 =200;

Х4 =200.

Как следует, если будут создавать продукт Б5 и Б4 в объеме 200 ед., то получат наивысшую Рассмотрим пример задачи линейного программирования прибыль в размере 2000руб;

Х6=100, означает что 100 кг. Сырья первого вида осталось не использованным.


rasstoyanie-mezhdu-tochkami.html
rasstoyanie-ot-verhnej-ili-nizhnej-stroki-teksta-do-verhnej-ili-nizhnej-ramki-formata-dolzhno-bit-ne-menee-10-mm.html
rasstoyaniya-iz-goa-do-blizhajshih-krupnih-gorodov.html