Тема: Решение задач линейного программирования симплекс-методом
-
Цель работы
1.1 Закрепить знания построения математической модели задачи ЛП
-
Научится строить первый опорный план задачи ЛП
-
Научится находить оптимальное решение задачи ЛП симплекс-методом
2. Теоретические сведения
Симплексный метод решения задач линейного программирования основан на последовательном переходе от одного опорного плана (решения) ЗЛП к другому, при этом значения целевой функции изменяются.
2.1 Алгоритм симплекс-метода
Алгоритм симплексного метода состоит:
-
Составление первого опорного плана.
а) Симплексная таблица начального опорного решения методом cимплексного метода при стремлении целевой функции к максимуму.
Коэффициенты целевой функции |
c1 |
c2 |
|
cn |
0 |
0 |
0 |
0 |
|
|||
План |
Базисные переменные |
Значения базисных переменных |
х1 |
х2 |
… |
xn |
xn+1 |
xn+2 |
…. |
xn+m |
zi |
|
1 |
xn+1
xn+2 …… xn+m
|
b1
b2 ….. bm |
а11
а21
аm1 |
a12
a22
am2 |
|
а1n
а2n
аmn |
1
0
0
|
0
1
0 |
|
0
0
1
|
|
|
Индексная строка |
F(X) |
0 |
- c1 |
- c2 |
|
- cn |
0 |
0 |
0 |
0 |
|
При стремлении целевой функции к минимуму опорное решение находится методом М- базиса.
Коэффициенты целевой функции |
C *1 |
C *2 |
|
C*n |
0 |
0 |
0 |
0 |
|
|||
План |
Базисные переменные |
Значения базисных переменных |
х1 |
х2 |
… |
xn |
y1 |
y2 |
…. |
ym |
zi |
|
1 |
y1
y2 …… ym
|
b1
b2 ….. bm |
а11
а21
аm1 |
a12
a22
am2 |
|
а1n
а2n
аmn |
1
0
0
|
0
1
0 |
|
0
0
1
|
|
|
Индексная строка |
F(X) |
M(b1+…+bm) |
-C *1 |
-C *2 |
|
-C* n |
0 |
0 |
0 |
0 |
|
Для нахождения значений C *i надо переменные уi выразить через основные переменные (в уравнениях ограничителях) и подставить в целевую функцию.
-
Проверка плана (решения) на оптимальность. Если все коэффициенты последней строки симплексной таблицы (F(X)) при решении на максимум неотрицательны, то план (решение) оптимален. Если хотя бы одно значение индексной строки меньше нуля, то план не оптимален, и его можно улучшить. (При решении ЗЛП на минимум целевой функции признаком оптимального плана являются отрицательные значения коэффициентов индексной строки) симплексной таблицы. Переходим к следующему этапу.
-
Определение ведущих столбцов и строк. Из отрицательных значений последней строки выбираем наибольший по модулю, что и определяет ведущий столбец, который показывает, какая переменная на следующем приближении перейдет из свободных в базисные. Затем столбец свободных членов симплексной таблицы делим на элементы того же знака ведущего столбца. Делятся только элементы одинаковых знаков. Результаты заносим в отдельный столбец zi. Строка, соответствующая минимальной zi является ведущей. Она определяет переменную, которая в следующем плане выйдет из базиса и станет свободной. Элемент, находящийся на пересечении ведущей строки и ведущего столбца, называют разрешающим и выделяют.
-
Построение нового опорного плана. Разделить элементы ведущей строки предыдущей таблицы на разрешающий элемент и результаты деления занесем в строку следующей симплексной таблицы значения , соответствующие введенной в базис переменной (на месте разрешающего элемента появится 1). А в остальные клетки ведущего столбца, включая и строку f , записываем нули.
Остальные новые элементы нового плана находятся по правилу прямоугольника НЭ = СЭ - (А∙В)/РЭ,
где НЭ- новый элемент, СЭ- старый элемент, РЭ- разрешающий элемент, А и В –элементы старого плана образующие прямоугольник с элементами СЭ и РЭ
Далее возвращаемся ко второму этапу - проверке на оптимальность.
Пример
Коммерческое предприятие реализует три группы товаров (А,В,С). плановые нормативы затрат ресурсов на 1 т. руб. товарооборота ,доход от продажи товаров на 1 т. руб. товарооборота , а так же объем ресурсов заданы. Определить плановый объем продаж и структуру товарооборота так, чтобы доход торгового предприятия был максимальным.
-
Виды ресурсов
Нормы затрат на 1т. руб. товарооборота.
объем ресурсов
А
В
С
Рабочее время продавцов
Площадь торговых залов
Площадь складских помещений
Доход
0,1
0,05
3
3
0,2
0,02
1
5
0,4
0,02
2
4
110
20
800
максимальный
Запишем математическую модель :
х1, х2,х3 - количество продаваемых товаров;
Доход ( целевая функция ) определяется
F(X)= max(3 х1+5 х2+4 х3)
При условии
х1≥0; х2≥0; х3≥0;
и ограничениях
0,1х1+ 0,2х2+ 0,4х3≥1100
0,05х1+0,02х2+0,02х3≤120
3х1+ х2+ 2х3≤8000
Для построения первого опорного плана приведем запись ОЗЛП в канонической форме
F(X)= max(3 х1+5 х2+4 х3)
При условии
х1≥0; х2≥0; х3≥0;
и ограничениях
0,1х1+ 0,2х2+ 0,4х3+х4 =1100
0,05х1+0,02х2+0,02х3+ х5 =120
3х1+ х2+ 2х3+ х6 =8000
Запишем математическую модель в векторном виде
F(X)=max(C∙X), где С=(3 5 4 0 0 0 ) – вектор-строка из коэфф. Целевой функции
х1
х2
Х= х3 - вектор-столбец переменных
х4
х5
х6
при условии вектор Х ≥0
и ограничениях А*Х=Р0,
где матрица
0,1 0,2 0,4 1 0 0 1100
А= 0,05 0,02 0,02 0 1 0 , Р0 = 120
3 1 2 0 0 1 8000
Находим первый опорный план
Базисные переменные: х3; х4; х5.
Свободные переменные: х1=0; х2=0; х3=0;
В этом случае значения базисных переменных равны значениям свободных членов. Построим таблицу
Коэффициенты целевой функции |
3 |
5 |
4 |
0 |
0 |
0 |
|
||
План |
Базисные переменные |
Значения базисных переменных |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
zi |
1 |
х4
x5
x6
|
1100
120
8000 |
0,1
0,05
3 |
0,2
0,02
1 |
0,4
0,02
2 |
1
0
0 |
0
1
0
|
0
0
1 |
5500
6000
8000 |
Индексная строка |
F(X) |
0 |
- 3 |
- 5 |
-4 |
0 |
0 |
0 |
|
Первый опорный план не оптимален, т.к. в индексной строке находятся отрицательные коэффициенты. Значит будем строить новый план.
За ведущий столбец выбираем столбец с максимальным по модулю отрицательным элементом индексной строки (-5). Переменная х2 переходит из свободных в базисные.
Для определения ведущей строки находим значения z. Значения базисных переменных делим на значения элементов ведущего столбца, учитывая знак.
Минимальное значение z определяет ведущую строку. Базисная переменная х4 переходит в свободные. Разрешающий элемент равен 0.2.
Формируем второй план таблицы.
Новые значения ведущей строки равны значению старого элемента деленного на разрешающий элемент.
Новые значения ведущего столбца равны нулю (включая и инд.строку), кроме элемента находящегося на пересечении ведущего столбца и ведущей строки. (Он равен 1).
Остальные элементы находятся по правилу прямоугольника
НЭ = СЭ - А∙В/РЭ
Например для элемента на пересечении х5 и х1 НЭ=0,05-0.01*0.02/0,2=0,04 и т.д.
План |
Базисные переменные |
Значения базисных переменных |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
zi |
2 |
х2
х5
x6
|
5500
10
2500
|
0,5
0,04
2,5 |
1
0
0 |
2
-0,02
0 |
5
-0,1
-5 |
0
1
0
|
0
0
1 |
11000
250
1000 |
Индексная строка |
F(X) |
27500 |
- 0,5 |
0 |
6 |
0 |
0 |
0 |
|
Этот план не оптимален. По вышеописанному алгоритму строим следующий план решения
План |
Базисные переменные |
Значения базисных переменных |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
zi |
3 |
х2
х1
x6
|
5375
250
1875
|
0
1
0 |
1
0
0 |
2,25
-0,5
1,25 |
5
-0,1
-5 |
6,25
-2,5
1,25
|
0
0
1 |
|
Индексная строка |
F(X) |
27625 |
0 |
0 |
5,75 |
23,75 |
12,5 |
0 |
|
При третьей итерации (приближении) получаем оптимальный план.
Следовательно фирма должна продавать 250 ед. товара А , 5375 ед. товара В , товар С не реализуется. Доход получат при этом максимальный – 27625. Оказывается недоиспользована площадь складских помещений на 1875 м2.
Индексная строка свободных переменных 3-го плана (х3,х4,х5) имеет ненулевые элементы. Это говорит о том , что данный план линейной задачи является единственным.
3. Задание
Выбрать одну задачу из приведенных ниже и выполнить следующие этапы по ее решению:
- записать математическую модель ЗЛП
- изучить теоретический материал, разобрать предложенный пример и решить задачу симплекс-методом
- сделать выводы по полученным результатам.
Задача 1.
Предприниматель арендовал технологическую линию деревообрабатывающих станков для изготовления вагонки. Магазин «Стройматериалы» заказал комплекты из трех элементов: две вагонки длиной 2 м и одной вагонки длиной 1,25 м. Поставщик завозит на грузовом автомобиле доски толщиной 20 мм, шириной 100 мм и длиной по 6,5 м — 200 шт. и длиной по 4 м — 50 шт.
Рассчитайте, как распилить доски, чтобы продать максимальное количество комплектов?
Задача 2.
Составьте дешевый вариант 1 т кормовой смеси в соответствии с требованиями, представленными в следующей таблице:
Питательные вещества |
Требования % от веса |
Содержание питательных веществ в кормах, % |
|||
Люцерновая мука |
Сухая барда |
Рыбная мука |
Соевый шрот |
||
Белок |
Не менее 35 |
17 |
25 |
60 |
45 |
Жиры |
Не менее 1,5 |
2 |
5 |
7 |
0,5 |
Клетчатка |
Не более 8 |
25 |
3 |
1 |
6,5 |
Вес |
1 т |
1 |
1 |
1 |
1 |
Стоимость руб. за 1 т |
? |
70 |
90 |
150 |
100 |
Задача 3
По предписанию врача пациенту необходимо перейти на диету и за сезон употребить питательных веществ, содержащихся во фруктах, в количествах, указанных в таблице. Определите, какое количество фруктов каждого вида необходимо купить за сезон, чтобы выполнить предписание врача с минимальными расходами.
Вещества |
Содержание питательных веществ в 1 кг фруктов |
Нормы потребления, г |
||
клубника |
яблоки |
смородина |
||
Р1 |
3 |
2 |
1 |
30 |
Р2 |
1 |
3 |
4 |
70 |
Р3 |
0 |
0 |
5 |
40 |
Р4 |
1 |
0 |
1 |
50 |
Цена, руб. за 1 кг |
1,0 |
0,5 |
0,8 |
|
Задача 4.
Сформируйте вариант образования бензина АИ-80 и АИ-95, который обеспечивает максимальный доход от продажи, если имеется 5 т смеси 1-го сорта и 30 т смеси 2-го сорта. На изготовление бензина АИ-80 идет 60% смеси 1-го сорта и 40% смеси 2-го сорта, на изготовление бензина АИ-95 идет 80% смеси 1-го сорта и 20% смеси 2-го сорта. Реализуется 1 т бензина АИ-80 за 5000 руб., а 1 т АИ-95 - за 6000 руб.
Задача 5.
Фирма производит два безалкогольных широко популярных напитка «Колокольчик» и «Буратино». Для производства 1 л «Колокольчика» требуется 0,02 ч работы оборудования, а для «Буратино» - 0,04 ч, а расход специального ингредиента на них составляет 0,01 кг и 0,04 кг на 1 л соответственно. Ежедневно в распоряжении фирмы 16 кг специального ингредиента и 24 ч работы оборудования. Доход от продажи 1 л «Колокольчика» составляет 0,25 руб., а «Буратино» - 0,35 руб.
Определите ежедневный план производства напитков каждого вида, обеспечивающий максимальный доход от их продажи.
Задача 6.
Фирма производит для автомобилей запасные части типа А и В. Фонд рабочего времени составляет 5000 чел.-ч в неделю. Для производства одной детали типа А требуется 1 чел.-ч, а для производства одной детали типа В — 2 чел.-ч. Производственная мощность позволяет выпускать максимум 2500 деталей типа А и 2000 деталей типа В в неделю. Для производства детали типа А уходит 2 кг полимерного материала и 5 кг листового материала, а для производства одной детали типа В — 4 кг полимерного материала и 3 кг листового металла. Еженедельные запасы каждого материала -по 10 000 кг. Общее число производимых деталей в течение одной недели должно составлять не менее 1500 штук.
Определите, сколько деталей каждого вида следует производить, чтобы обеспечить максимальный доход от продажи за неделю, если доход от продаж одной детали типа А и В составляет соответственно 1,1 руб. и 1,5 руб.
Задача 7.
Брокеру биржи клиент поручил разместить 100 000 долл. США на фондовом рынке, сформировать портфель с ценными бумагами, чтобы получить максимальные годовые проценты с вложенного капитала. Выбор ограничен четырьмя возможными объектами инвестиций-акций А, В, С, Д, которые позволяют получить доход в размерах соответственно 6%, 8%, 10% и 9% годовых от вложенной суммы. При этом клиент поручил не менее половины инвестиций вложить в акции А и В. С целью обеспечения ликвидности не менее 25% общей суммы капитала нужно поместить в акции Д. Учитывая прогноз на изменение ситуации в будущем, в акции С можно вложить не более 20% капитала. Специфика налогообложения указывает на необходимость вложения в акции А не менее 30% капитала.
Определите распределение инвестиций капитала, обеспечивающего максимальный годовой процентный доход.
Задача 8.
Туристская фирма в летний сезон обслуживает в среднем 7500 туристов и располагает флотилией из двух типов судов, характеристики которых представлены в таблице.
-
Судно
1
2
Пассажировместимость, чел.
2000
1000
Горючее, т
12000
7000
Экипаж, чел.
250
100
В месяц выделяется 60 000 т горючего. Потребность в рабочей силе не превышает 700 человек.
Определите количество судов I и II типа, чтобы обеспечить максимальный доход, который составляет от эксплуатации судов I типа 20 млн руб., а II типа - 10 млн руб. в месяц.
Задача 9.
Фирма производит и продает столы и шкафы из древесины хвойных и лиственных пород. Расход каждого вида в кубометрах на каждое изделие задан в таблице.
-
Вид изделия
Расход древесины, м3
Цена изделия, тыс. руб.
Хвойные
Лиственные
Стол
0,15
0,2
0,8
Шкаф
0,3
0,1
1,5
Запасы древесины
80
40
Определите оптимальное количество столов и шкафов, которое следует поставлять на продажу для получения максимального дохода фирмы.