.
Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.
Исходные данные задачи запишем в виде таблицы, а опорный план получим методом минимального элемента.
Минимальный тариф, равный 1, находится в клетке (1,3).
х13 = min(A1,B3)=A1=160.
Запишем это значение в соответствующую клетку и временно исключим из рассмотрения строку А1.
Теперь потребности пункта B3 считаем равными 190-160=30 ед. В оставшейся части таблицы наименьший тариф находится в клетке (3,2) и равен 2.
х32 = min(A3,B2)=B2=50.
Внесём значение в соответствующую клетку и исключим из рассмотрения столбец B2.
Запасы пункта А3 считаем равными 170-50=120 ед.
В оставшейся части (строки А2, А3 и столбцы В1, В3, В4) минимальный тариф равен 3 и находится в клетке (3,3).
х33 = min(A3,B3)=В3=30.
И так далее, пока не исчерпаем запасы и не удовлетворим потребности. Получим следующую таблицу.
Потребности Запасы | B1=120 | B2=50 | B3=190 | B4=110 | |
β1=2 | β2=2 | β3=3 | β4=6 | ||
A1=160 | α1=-2 | 7 | 8 | 1 160 | 2 |
A2=140 | α2=2 | 4 120 | 5 | 9 | 8 20 |
A3=170 | α3=0 | 9 | 2 50 | 3 30 | 6 90 |
Число заполненных клеток равно 6 и m+n-1=3+4-1=6 – план невырожденный.
Оптимальный план найдём методом потенциалов.
В оптимальном плане транспортной задачи заполненным клеткам отвечают равенства 
, а пустым – неравенства 
. Тогда, получим
, положим 
, тогда
.
(Обычно равным нулю принимают потенциал строки или столбца с наибольшим числом заполненных клеток.)
Теперь проверим пустые клетки на выполнение неравенства .
Запишем систему неравенств:
.
Для клетки (1, 4) неравенство не выполняется, значит в неё нужно "ввезти" груз. Строим цикл.
Цикл перерасчёта таблицы - это последовательность ячеек, начинающаяся и заканчивающаяся в одной и той же клетке, с вершинами, лежащими в занятых клетках, кроме одной.
Вершина цикла – клетка, в которой происходит поворот под прямым углом.
"Перемещаем" груз по следующим правилам:
1. Каждой из клеток, связанных циклом присваивается знак: пустой ячейке "+", остальным - поочерёдно знаки "-" и "+" .
2. Среди минусовых клеток находим число 
и прибавляем его к числам, стоящим в плюсовых клетках, и вычитаем из чисел, стоящих в минусовых клетках; остальные клетки вне цикла остаются без изменения.
В нашем примере цикл образуют четыре ячейки: (1,4) – пустая, для которой не выполняется неравенство, и клетки (1,3), (3,3), (3,4) – заполненные.
х = min(160, 90)=90. Значит в плюсовые клетки "завозим" 90 ед. груза, из минусовых "вывозим". Получим новый опорный план:
Потребности Запасы | B1=120 | B2=50 | B3=190 | B4=110 | |
β1=0 | β2=2 | β3=3 | β4=4 | ||
A1=160 | α1=-2 | 7 | 8 | 1 70 | 2 90 |
A2=140 | α2=4 | 4 120 | 5 | 9 | 8 20 |
A3=170 | α3=0 | 9 | 2 50 | 3 120 | 6 |
Расставим потенциалы и проверим пустые клетки на выполнение неравенства :
Для клетки (2,2) неравенство не выполняется. Значит, строим цикл с вершиной в этой клетке.
х = min(50, 70, 20)=20. Значит в плюсовые клетки "завозим" 20 ед. груза, из минусовых "вывозим". Получим новый опорный план:
Потребности Запасы | B1=120 | B2=50 | B3=190 | B4=110 | |
β1=1 | β2=2 | β3=3 | β4=4 | ||
A1=160 | α1=-2 | 7 | 8 | 1 50 | 2 110 |
A2=140 | α2=3 | 4 120 | 5 20 | 9 | 8 |
A3=170 | α3=0 | 9 | 2 30 | 3 140 | 6 |
Полученный план является оптимальным (неравенство выполняется для всех пустых клеток).
Ответ: 
,
=50*1+110*2+120*4+20*5+30*2+140*3=1330.
Вариант № 1
1. Найти решение задачи ЛП, используя графический метод.
2. Составить математическую модель задачи.
На швейной фабрике для изготовления четырёх видов изделий может быть использована ткань трёх артикулов. Нормы расхода тканей всех артикулов на пошив одного изделия приведены в таблице. В ней же указаны имеющееся в распоряжении фабрики общее количество тканей каждого артикула и цена одного изделия данного вида. Определить сколько изделий каждого вида должна произвести фабрика, чтобы стоимость изготовленной продукции была максимальной.
Артикул ткани | Норма расхода ткани (м) на одно изделие | Общее количество ткани (м) | |||
Вид 1 | Вид 2 | Вид 3 | Вид 4 | ||
I | 1 | - | 2 | 1 | 180 |
II | - | 1 | 3 | 2 | 210 |
III | 4 | 2 | - | 4 | 800 |
Цена одного изделия (руб.) | 9 | 6 | 4 | 7 |
3. В следующей задаче требуется: а) составить для данной задачи линейного программирования двойственную задачу; б) решить исходную задачу симплексным методом; в) по решению исходной найти решение двойственной задачи.
4. Решить транспортную задачу.
На трёх хлебокомбинатах ежедневно производится 110, 190 и 90 т муки. Эта мука потребляется четырьмя хлебозаводами, ежедневные потребности которых равны соответственно 80, 60, 170 и 80 т. Тарифы перевозок 1 т муки с хлебокомбинатов к каждому из хлебозаводов задаются матрицей
Составить такой план доставки муки, при котором общая стоимость перевозок является минимальной.
Вариант № 2
1. Найти решение задачи ЛП, используя графический метод.
2. Составить математическую модель задачи.
Предприятие выпускает четыре вида продукции и использует три типа основного оборудования: токарное, фрезерное и шлифовальное. Затраты времени на изготовление единицы продукции для каждого из типов оборудования приведены в таблице. В ней же указаны общий фонд рабочего времени каждого из типов оборудования, а также прибыль от реализации одного изделия данного вида. Определить такой объём выпуска каждого из изделий, при котором общая прибыль от их реализации является максимальной.
Тип оборудования | Затраты времени (станко-ч) на единицу продукции вида | Общий фонд рабочего времени (станко-ч) | |||
1 | 2 | 3 | 4 | ||
Токарное | 2 | 1 | 1 | 3 | 300 |
Фрезерное | 1 | - | 2 | 1 | 70 |
Шлифовальное | 1 | 2 | 1 | - | 340 |
Прибыль от реализации ед. продукции (руб.) | 8 | 3 | 2 | 1 |
3. В следующей задаче требуется: а) составить для данной задачи линейного программирования двойственную задачу; б) решить исходную задачу симплексным методом; в) по решению исходной найти решение двойственной задачи.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 |
