Гбоу спо «пермский агропромышленный техникум»

ГБОУ СПО «Пермский агропромышленный техникум»

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

«Элементы линейного программирования»

(профессиональный цикл по направлениям профессиональной

подготовки «Коммерция»)

Выполнила преподаватель математики Есенеева Эльвира Самигулловна

Пермь, 2012

Рецензенты

Малых А.Е.

Иванов А.П.

Содержание

Стр

Пояснительная записка___________________________________________________________ 3

Тематический план______________________________________________________________   4

Введение­_______________________________________________________________________  5

Классификация моделей___________________________________________________________6

Основные этапы построения математических моделей _________________________________ 9

Постановка задачи линейного программирования ____________________________________ 10

Графический метод_______________________________________________________________12

Транспортная задача. Общая постановка задачи_______________________________________15

Открытые и закрытые транспортные задачи__________________________________________17

Построение начального плана транспортной задачи по правилу «северо-западного угла»____18

Построение начального плана транспортной задачи методом  «минимального элемента»____20

Проверка найденного решения на оптимальность. Метод потенциалов__________________ 2

Вырожденность в транспортных задачах____________________________________________ 27

Приложения транспортных моделей_______________________________________________ 29

Решение транспортной задачи средствами MathCAD__________________________________32

Задача о назначениях ____________________________________________________________ 25

Симплекс – метод______________________________________________________________   29

Приложение 1 (Контрольные задания по теме «Графический метод) ____________________ 35

Приложение 2 (Контрольные задания по теме «Транспортные задачи) __________________ 40

Приложение 3 (Контрольные задания по теме «Задачи о назначениях)­­­­­­­­­__________________ 46

Приложение 4 (Контрольные задания по теме «Симплекс – метод»)____________________ 49

Приложение 5 (Вопросы к зачету)__________________________________________________ 50

Список информационных источников_______________________________________________51

 

Пояснительная записка

Современная математика характеризуется интенсивным проникновением в другие науки, во многом этот процесс происходит благодаря разделению математики на ряд самостоятельных областей. Язык математики оказался универсальным, то есть она пытается отразить, или промоделировать, на своем специфическом языке закономерности окружающего мира.

Изучение  экономических приложений математики, составляющих основу актуальной экономической математики, позволит будущему специалисту не только приобрести необходимые базовые навыки, используемые в экономике, но и сформировать компоненты своего мышления: уровень, кругозор и культуру. Все это понадобится для успешной работы  по окончании учебного заведения и для ориентации в будущей профессиональной деятельности.

Учитывая современные требования, необходимые для специалистов связанных с экономикой и воспитания конкурентоспособного выпускника возникла необходимость введение данного курса в группах профессиональной подготовки по направлению «Коммерция».

Программа данного курса рассчитана на 30 часов и включает 4 раздела:

- Графический метод решения задач линейного программирования;

- Транспортная задача;

- Задача о назначениях;

 - Решение задач линейного программирования симплекс – методом.

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

 После изучения каждой темы разбирается решение одной или нескольких задач. В конце каждого раздела выполняется контрольная работа (10 вариантов заданий)  которая позволяет закрепить и  проверить умения и навыки учащихся по пройденной теме.

Тематическое планирование

№ п/п	Содержание учебного материала (всего30 часов)	Кол – во часов
1	Введение.  Классификация моделей.  Основные этапы построения моделей.	1
2	Постановка задачи линейного программирования.	1
3	Графический метод. Решение задач.	2
4	Контрольная работа.	1
5	Общая постановка транспортной задачи. Открытые и закрытые транспортные задачи. Приведение открытой транспортной задачи к закрытой.	2
6	Построение начального плана транспортной задачи по правилу «северо–западного» угла.	1
7	Методы решения транспортных задач. Метод минимального элемента.	1
8	Проверка полученного решения на оптимальность. Метод потенциалов.	2
9	Вырожденность в транспортных задачах.	2
10	Приложения транспортных моделей.	2
11	Решение транспортных задач с помощью математического пакета MathCAD.	2
12	Контрольная работа.	2
13	Задача о назначениях. Общая постановка задачи.	1
14	Венгерский метод решения задачи о назначениях. Решение задач.	1
15	Контрольная работа.	1
16	Симплекс – метод. Алгоритм решения задач линейного программирования симплекс – методом.	3
17	Контрольная работа.	2
18	Обобщение.	1
19	Зачет.	2

Введение

Экономические проблемы, возникающие перед специалистами в большинстве своем сложные. Они зависят от множества различных, иногда противоречащих друг другу факторов, изменяются с течением времени и влияют на другие проблемы и процессы.

Для принятия обоснованного решения необходимо иметь и обработать большое количество информации, определяемое иногда астрономическими цифрами. Принятие ответственных решений, как правило, связано с большими материальными ценностями. В настоящее время недостаточно знать путь, ведущий к достижению цели. Необходимо из всех возможных путей выбрать наиболее экономичный, который наилучшим образом соответствует поставленной задаче.

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

Впервыематематические модели были использованы для решения практической задачи в 30-х годах в Великобритании при создании систем противовоздушной обороны. Для разработки данной системы были привлечены ученые различных специальностей. Система создавалась в условиях неопределенности относительно возможных действий противника, поэтому исследования проводились на адекватных математических моделях. В это время впервые был применен термин «операционное исследование», подразумевавший исследования военной операции. В последующие годы операционные исследования или исследования операций развиваются как наука, результаты которой применяются для выбора оптимальных решений при управлении реальными процессами и системами.

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

Определение 1. Математическая модель-это система математических соотношений, приближенно, в абстрактной форме описывающих изучаемый процесс или систему.

Определение 2. Экономико-математическая модель-это математическая модель, предназначенная для исследования экономической проблемы.

В настоящее время математические модели  применяются для анализа, прогнозирования и выбора оптимальных решений в различных областях экономики. Это планирование и оперативное управление производством, управление трудовыми ресурсами, управление запасами, распределение ресурсов, планировка и размещение объектов, руководство проектом, распределение инвестиций и т.п.

 

Классификация моделей

Математические модели  можно классифицировать следующим образом: (см. схему)

По числу критериев эффективности ММ делятся на однокритериальные и многокритериальные. Многокритериальные содержат 2 или более критерия.

По учету неизвестных факторов математические модели делятся на детерминированные, стохастические и модели с элементами неопределенности.

 В детерминированных моделях не учитываются неизвестные факторы. Несмотря на кажущуюся простоту этих моделей, к ним сводятся многие практические задачи, в том числе большинство экономических. По виду целевой функции и ограничений детерминированные модели делятся на линейные, нелинейные, динамические и графические.

В линейных моделях целевая функция и ограничения линейны по управляющим переменным.

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

Нелинейные модели – это модели, в которых либо целевая функция, либо какое–нибудь из ограничений (либо все ограничения нелинейные по управляющим переменным. (т. е. переменная не в первой степени). Для нелинейных моделей нет единого метода расчета и поэтому можно предложить различные способы решения. Однако может случиться так, что для поставленной нелинейной задачи вообще не существует метода расчета. В этом случае задачу следует упростить, сведя его к известным линейным моделям.

В динамических моделях в отличие от линейных и нелинейных моделей учитывается фактор времени. Критерий оптимальности в этих моделях может быть самого общего вида(и вообще не быть функцией), однако для него должны выполняться определенные свойства. Расчет динамических моделей сложен, и для каждой конкретной задачи необходимо разрабатывать специальный алгоритм решения.

 

Классификация моделей

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

В стохастических моделях неизвестные факторы - случайные величины, для которых известны функции распределения и различные статистические характеристики (математическое ожидание, дисперсия, среднеквадратическое отклонение и т.п.). среди них можно выделить:

- модели стохастического программирования, в которых либо в целевую функцию, либо в ограничения входят случайные величины;

- модели теории случайных процессов, предназначенные для изучения процессов, состоятие которых в данный момент времени является случайной величиной;

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

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

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

I раздел

Графический метод

Графический метод является наиболее простым и наглядным методом линейного программирования.

 

Применяется для решения задач линейного программирования с 2-мя переменными.

С геометрической точки зрения в задаче ищется такая угловая точка или набор точек из допустимого множества решений, на котором достигается самая верхняя или нижняя линия уровня или точка выхода линии уровня из области допустимых решений.

Для нахождения экстремального значения целевой функции при графическом методе используют вектор, показывающий направление наискорейшего изменения целевой функции С.

Алгоритм решения задач ГМ.

1. Находим область допустимых решений системы ограничений задачи.

2. Строим вектор С.

3. Проводим линию уровня L_0, которая перпендикулярна С.

4. Линию уровня перемещаем по направлению вектора С для задач на максимум и в направлении противоположном С, для задач на минимум.

Перемещение линии уровня производится до тех пор, пока у нее не окажется только одна общая точка с областью допустимых решений. Эта точка, определяющая единственное решение задачи, и будет точкой экстремума. Если окажется, что линия уровня параллельна одной из сторон ОДР, то в таком случае экстремум достигается во всех точках соответствующей стороны, а задача будет иметь бесчисленное множество решений.

5.Находим координаты точки экстремума и значение целевой функции в ней.

Возможны следующие случаи ОДР:

 

 

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

Фирма выпускает 2 вида мороженого: сливочное и шоколадное. Для изготовления мороженого используются 2 вида продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы заданы в таблице.

Исходный продукт	Расход исходных продуктов		Запас,кг
	сливочное	шоколадное
Молоко	0,8	0,5	400
Наполнители	0,4	0,8	365

Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого 16 руб., шоколадного – 14 руб.

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

Решение.

Обозначим: х1 – суточный объем выпуска сливочного мороженого, кг; х2 - суточный объем выпуска шоколадного мороженого, кг.

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

Целевая функция будет иметь вид:

L(x) = 16x1+14x2 – max при ограничениях:

0,8 x1+ 0,5x2£ 400,

0,4x1+0,8x2£ 365,

x1-x2£100,

x2£350,

x1³0, x2³0.

 

OABDEF – область допустимых решений. Строим вектор с(1;1). Линия уровня задается уравнением  L₀ = 16x1+14x2=const.

Перемещаем линию уровня по направлению вектора с. Точкой выхода L₀  из области допустимых решений является точка D, ее координаты определяются как пересечение прямых, заданных уравнениями:

0,8х1+0,5х2=400

0,4х1+0,8х2 = 365.

Решая систему, получим координаты точки D (312,5; 300), в которой и будет оптимальное решение, т.е Х_опт =(312,5; 300), при этом

L(x)_max = 16*312,5 + 14*300 = 9200.

Таким образом, фирма должна выпускать в сутки 312,5 кг сливочного мороженого и 300 кг шоколадного мороженого, при этом доход от реализации составит 9200 рублей.

 II раздел

Транспортная задача

Общая постановка задачи

Транспортная задача – одна из распространенных задач линейного программирования. Ее цель – разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозо к. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.

В общем виде транспортную задачу можно представить следующим образом: Некий продукт (например, сталь) вырабатывается на m заводах , причем ежемесячная выработка составляет соответственно. Пусть эту сталь нужно доставить на предприятия (всего k), причем - ежемесячная потребность этих предприятий. Наконец, пусть задана стоимость ,  перевозки одной тонны стали с завода на предприятие .  Принято считать, что общее производство стали равно суммарной потребности в ней:

а₁+а₂+…+а_т= b₁+ b₂+… b_k.

Требуется составить план перевозок, при котором:

1) была бы точно удовлетворена потребность в стали предприятий ;

2) была бы вывезена вся сталь с заводов ;

3)общая стоимость перевозок была бы наименьшей.

Пример.

Найдем начальное решение предыдущего примера методом «минимального элемента».

№	1	2	3	4	Предложение
1	90^3	^4	20^5	^6	110
2	^7	^5	100 ^8	40^1	140
3	^9	150^2	40   ^3	^4	190
Спрос	90	150	160	40

 

Минимальный тариф   Спрос 4-го потребителя удовлетворен – соответственно 4-ый столбец вычеркиваем.

 Минимальный тариф для оставшихся клеток   Спрос 2-го потребителя удовлетворен – 2-ой столбец вычеркиваем.

Для оставшихся клеток минимальный тариф:

  Спрос 1-го потребителя удовлетворен - вычеркиваем 1-ый столбец.

Для оставшихся клеток минимальный тариф:

Предложение 3-его поставщика исчерпано – вычеркиваем 3-ю строку.

Следующий минимальный тариф для оставшихся клеток: ,  Предложение 1-го поставщика исчерпано – вычеркиваем 1-ую строку.

Для последней оставшейся клетки:

.

План перевозок, полученный по методу минимального элемента, имеет вид:

Стоимость перевозок по этому плану составляет

 у.е.

 Видим, что стоимость перевозок, полученных по методу минимального элемента, меньше стоимости перевозок, полученных  с использованием правила  «северо – западного угла» на 60 у.е. План, полученный данным методом более близок к оптимальному.

Метод потенциалов

Определение 1: Если при решении транспортной задачи число заполненных клеток транспортной таблицы равно m + n – 1, где m – где число производителей, а n – число потребителей, то план перевозок невырожденный.

Определение 2: Если число заполненных клеток транспортной таблицы меньше  m + n – 1, где m – где число производителей, а n – число потребителей, то план перевозок вырожденный.

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

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

Для оценки водится понятие косвенных затрат. Косвенные затраты – это затраты, получаемые для маршрутов, по которым не осуществляются перевозкипри данном плане. Рассчитанные косвенные затраты сравниваются с реальными затратами, которые имели бы место, если бы перевозки по данным маршрутам осуществлялись. Если для всех невыбранных маршрутов косвенные затраты не больше реальных, то данный план перевозок является оптимальным. Если хотя бы для одного маршрута косвенные затраты больше реальных, то план перевозок может быть улучшен путем введения в него данного маршрута.

Рассмотрим получение оптимального плана перевозок с использованием метода потенциалов.

1 шаг: Получение начального плана перевозок. (методом «минимального элемента» или другим методом).

2 шаг: Проверка плана на невырожденность

Если полученный план вырожденный, то формально заполняют нулями некоторые из свободных клеток так, чтобы общее число занятых клеток было равно m + n – 1. Нули надо расставлять так, чтобы не образовался замкнутый цикл из занятых клеток.

3 шаг: Проверка плана на оптимальность

3.1  Определение потенциалов производителей и потребителей. Составляют систему уравнений для заполненных клеток транспортной таблицы: U_i +V_J = C_ij,

где i, j – номера строк и столбцов, на пересечении которых стоят заполненные клетки, U_i потенциал i – го поставщика V_j – потенциал j –го потребителя C_ij - тариф на перевозку из пункта i в пункт j. Для решения данной системы одно из неизвестных выбирают произвольно. Обычно полагают U_i = 0. Решая систему уравнений, находят значения потенциалов U_i и V_j, i =1,m, j = 1,n.

3.2. Определение суммы потенциалов (косвенных тарифов) для свободных клеток: C1_qp = U_q + V_p, где q p – номера строк и столбцов, на пересечении которых стоит свободная клетка, U_q  - потенциал q-го поставщика, V_p- потенциал p-го потребителя, C1_qp – косвенные тарифы.

3.3 Проверка на оптимальность.

Для каждой свободной клетки таблицы составляется разность между C1_qp и C_qp (косвенным и реальным тарифами) . Если все , то полученный план оптимален. Если хотя бы для одной свободной клетки , то план может быть улучшен.

4 шаг. Улучшение плана

4.1 Выбирают клетку, которой соответствует максимальное положительное значение разности, полученной на шаге 3.3. Если имеется несколько одинаковых из них выбирают любое.

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

4.2 Выбор переменной выводимой из списка базисных переменных.

Заполнение клетки, выбранной на шаге 4.1, происходит следующим образом. Строят цикл, начинающийся и оканчивающийся в выбранной свободной клетке, содержащий в качестве вершин заполненные клетки таблицы и состоящий из горизонтальных и вертикальных отрезков. При этом в каждой клетке таблицы, являющейся вершиной цикла, соединяют обязательно горизонтальный и вертикальный отрезки. В свободной клетке условно ставят знак «+», а в остальных вершинах цикла, чередуясь ставят «-» и «+».Затем происходит перераспределение продукции по циклу. Для этого выбирают клетку со знаком «-», которой соответствует наименьшее число единиц продукции. Это значение прибавляют к значениям, стоящим в клетках со знаком «+» и отнимают от значений, стоящих со знаком «-». При таком распределении общий баланс не изменяется. Свободная клетка заполняется. А клетка со знаком «-», которой соответствует наименьшее количество продукции, становится свободной.

Для нового плана повторяют все действия. (т.е переходят к шагу 2).

Пример 1.  

Найти оптимальный план перевозок для транспортной задачи.

1) Получим начальный план решения методом минимального элемента.

№	1	2	3	4	Предложение
1	^7	^8	160 – ^1	+^2	160
2	120  ^4	^5	^9	20 ^8	140
3	^9	50 ^2	30 +  ^3	90 –^6	170
Спрос	120	50	190	110

2) Проверим число заполненных клеток m+n-1= 4+3-1=6, т.е. данный план невырожденный. Определим потенциалы производителей и потребителей, составив уравнения  U_i +V_J = C_ij, для заполненных клеток и занесем их в таблицу:

2.1 U₁+V₃=1,                   U₁=0,              V₁=0,

U₂+V₁=4,                         U₂=4,              V₂=0,

U₂+V₄=8,                         U₃=2.              V₃=1,

U₃+V₂=2,                                                     V₄=4.

U₃+V₃=3,

U₃+V₄=6.

2.2 Составим разности для свободных клеток:

Получена положительная разность . Заполним клетку первой строки и четвертого столбца. Строим цикл, начинающийся и заканчивающийся в этой клетке. Вершинами цикла являются клетки: (3,4), (3,3), (1,3). В клетке (1,4) ставим «+», в клетке (3,4) – «-», в клетке (3,3) «+», в клетке (1,3) ставим «-». Перераспределяем продукцию по циклу. Минимальное значение для клеток со знаком «-» находится в клетке (3,4) х₃₄=90. Отнимаем 90 от значений, стоящих в клетках со знаком «-», и прибавляем к значениям, стоящим в клетках со знаком «+». Получаем новый план перевозок, представленный в следующей транспортной таблице:

№	1	2	3	4	Предложение
1	^7	^8	70 ^– ^1	90   ^+ ^2	160
2	120^4	+^5	^9	20 – ^8	140
3	^9	50 – ^2	120 + ^3	^6	170
Спрос	120	50	190	110

 

3) Проверим число заполненных клеток: m+n-1=4+3-1= 6 - план невырожденный.

4) Проверим на оптимальность.

4.1 U₁+V₃=1,                   U₁=0,             V₁=-2,

U₁+V₄=2,                         U₂=6,              V₂=0,

U₂+V₁=4,                         U₃=2.              V₃=1,

U₂+V₄=8,                                                     V₄=2.

U₃+V₂=2,

U₃+V₃=3.

4.2 Составим разности для свободных клеток:

4.3 Получена положительная разность  . Заполним клетку (2,2). Цикл будет содержать клетки (2,2), (3,2), (3,3), (1,3), (1,4), (2,4), (2,2).       

Для того, чтобы не загромождать таблицу цикл можно вынести отдельно:

		70			90
			–	+
				–
	+				20
	–	+
50			120

Минимальное значение х₂₄=20 для клеток со знаком «-». Перераспределив продукцию по циклу, получим новый план перевозок, представленный в таблице:

№	1	2	3	4	Предложение
1	^7	^8	50^1	110^2	160
2	120^4	20^5	^9	^8	140
3	^9	30^2	140^3	^6	170
Спрос	120	50	190	110

 

5) Полученный план невырожденный. Проверим на оптимальность.

5.1 U₁+V₃=1,                   U₁=0,             V₁=-1,

U₁+V₄=2,                     U₂=5,              V₂=0,

U₂+V₁=4,                    U₃=2.              V₃=1,

U₂+V₂=2,                                                V₄=2.

U₃+V₂=2,

U₃+V₃=3.

5.2 Составим разности для свободных клеток:

Все разности отрицательные, следовательно полученный план является оптимальным.

Стоимость перевозки: L_min=50·1+110·2+120·4+20·5+30·2+140·3=1330 у.е.

Пример 2.  

Три торговых склада могут поставлять некоторое изделие в количестве 9,4 и 8 тонн. Величины спроса трех магазинов розничной торговли на это изделие равны 3, 5 и 6 т.

Какова минимальная стоимость транспортировки от поставщиков к потребителям, если матрица стоимостей имеет вид ?

Решение: Запасы складов потребности магазинов:  - задача открытая. Введем фиктивный магазин со спросом  и тарифом 20 у.е. и решим задачу методом минимального элемента.

№	1	2	3	4ф	Предложение	ui
1	^10	1^20	6^5	2^20	9	0
2	^2	4^10	^8	^20	4	-10
3	3^1	^20	^7	5^20	8	0
Спрос	3	5	6	7
vj	1	20	5	20

Оптимизируем полученное решение:

1) Найдем потенциалы заполненных клеток. (см. таблицу);

2) Оценим свободные клетки: .

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

.

Минимальная стоимость транспортных расходов L_опт=93 у.е.

Пример.

Фирма осуществляет поставку бутылок на три завода, занимающиеся производством прохладительных напитков. Она имеет три склада, причем на складе 1 находится 6000 бутылок, на складе 2 – 3000 бутылок и на складе 3 - 4000бутылок. Первому заводу требуется 4000бутылок, второму – 5000 бутылок, третьему – 1000 бутылок. Стоимость перевозки одной бутылки от каждого склада к каждому заводу задана матрицей:

Как следует организовать доставку бутылок на заводы, чтобы стоимость перевозки была минимальной?

Решение:

1.1 Запишем данные в распределительную таблицу.

1.2 Найдем опорное решение методом минимального тарифа.

1.3 Проверим вырожденной или невырожденной является транспортная задача: m+n-1=3+4-1=6, а число заполненных клеток равно 5, следовательно, задача является вырожденной (см. определение).

№	1	2	3	4	Предложение	ui
1	^6	3000^4	^9	3000^8	6000	0
2	^5	2000^3	1000^2	^8	3000	-1
3	4000^2	0^3	^6	^8	4000	-1
Спрос	4000	5000	1000	3000
vj	3	4	3	8

 

Исключим вырожденность. Для этого:

1. Введем в какую–нибудь клетку нулевую поставку. Такая клетка становится условно занятой. Ее целесообразно определить при вычислении потенциалов занятых клеток, она должна иметь наименьший тариф по сравнению с другими клетками, которые могут быть условно занятыми.

2.1.2. Определим потенциалы занятых клеток:

u₁+ v₂=4, u₁+ v₄=8, u₂+ v₂=3, u₂+ v₃=2, u₃+ v₁=2.

Полагая, что u₁=0 находим v₂=4, u₂=-1, v₃=3.

Для того чтобы найти u₃ и v₁ поместим нулевую поставку в клетку (3,2), и изравенств а u₃+ v₂=0 найдем сначала u₃, затем v_1.

3.1. Составим разности для свободных клеток:

Все оценки отрицательные, значит полученное начальное решение является оптимальным.

Таким образом, со склада 1 целесообразно поставить 3000 бутылок второму и четвертому заводам, со склада 2 – 2000 бутылок второму заводу и 1000 бутылок третьему, со склада 3 – 4000 бутылок первому заводу, при этом стоимость транспортных расходов будет минимальной и составит 28000 у.е.

Пример.

Дана транспортная задача (в виде таблицы). Найти ее исходное решение.

№	В1	В2	В3	Предложение
А1	70	38	24	14
А2	58	18	56	20
А3	19	10	100	26
Спрос	30	22	8

 

т.

Решение:

Исходный план будет состоять из 9-ти чисел (для данной задачи):

, где  - количество единиц груза, которое необходимо перевезти из пункта i в пункт j.

Математическая модель такой задачи имеет вид:

Целевая функция:

Системы равенств: