Еометрический (графический) метод решения задачи.

птимизационные методы и модели в управлении экономическими системами.

2.1. Линейное программирование.

Принцип оптимальности в планировании и управлении, общая задача оптимального программирования. Формы записи задачи линейного программирования и ее экономическая интерпретация. Геометрическая интерпретация задачи (геометрический метод решения задачи). Симплексный метод решения задач линейного программирования (с естественным и искусственным базисом). Теория двойственности в анализе оптимальных решений экономических задач.

2.2. Транспортная задача линейного программирования (закрытая). Метод потенциалов.

ероятностно-статистичесике методы моделирования экономических систем.

Теория массового обслуживания. Классификация систем массового обслуживания. Количественные характеристики. Показатели эффективности систем массового обслуживания.

алансовый метод.

Экономико-математическая модель межотраслевого баланса. Коэффициенты прямых и полных материальных затрат.

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

Контрольная работа выполняется студентами индивидуально на основе лекционного материала. Номер варианта контрольной работы - это последняя цифра номера зачетной книжки (цифре 0 соответствует 10 вариант).

ЗАДАНИЯ ДЛЯ КОНТРОЛЬНОЙ РАБОТЫ

ВАРИАНТ №1

адача 1.

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

_{, ,}

_{, .}

адача 2.

редприятие располагает 3-мя видами сырья и может выпускать одну и ту же продукцию двумя способами. При этом за 1 час работы первым способом выпускается 20 единиц продукции, а вторым способом - 30 единиц продукции. Количество сырья (кг) того или иного вида, расходуемого за 1 час при различных способах производства, и запасы сырья (кг) приведены в таблице.

Тип сырья	Способ производства	Запас сырья, кг.
1сп.	2сп.
С1
С2
С3

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

адача 3.

Решить следующую транспортную задачу:

А=(100; 150; 50), В=(75;80;60;85), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

На АЗС имеются 2 колонки для заправки автомоби­лей. Автомобили подъезжают на АЗС в соответствии с пуассоновским распределением со средней частотой 2 авто­мобиля за 5 мин. Заправка автомобиля в среднем длится 3 мин, и продолжительность заправки распределена по экс­поненциальному закону. Требуется определить:

а) вероятность того, что у АЗС не окажется ни одного ав­томобиля;

б) вероятность того, что обе колонки будут заняты;

в) среднюю длину очереди в ожидании заправки;

г) среднее время ожидания автомобиля в очереди.

адача 5.

На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.

Отрасль	Прямые межотраслевые потоки	Конечная продукция

ВАРИАНТ №2

адача 1.

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

_{, ,}

_{, .}

адача 2.

Фирма "Nokia" заключила контракт с администрацией города на прокладку новых телефонных линий двух видов: кабельных (x₁;[км]) и оптоволоконных (x₂;[км]). По условиям контракта фирме будут предоставлены льготы, если она выполнит условия контракта и охватит при этом своей сетью как можно большее пространство города (x₁+x₂). Необходимо определить в какой пропорции строить эти два вида линий связи.

	Вид телефонной линии	Условия контракта (ограничения)
кабельная	оптоволоконная
Трудовые ресурсы (чел./км)
Кол-во единиц техники (ед./км)
Денежные затраты ($/км)

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

адача 3.

Решить следующую транспортную задачу:

А=(300; 350;150; 200), В=(400;400;200), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

В парикмахерской работают 3 мастера. Посетители приходят в парикмахерскую в соответствии с пуассоновским распределением со средней частотой 4 человека в час. Стрижка в среднем длится 0,5 часа, и продолжительность стрижки распределена по экс­поненциальному закону. Требуется определить:

а) вероятность того, что в парикмахерской не окажется ни одного посетителя;

б) вероятность того, что все мастера будут заняты;

в) среднюю длину очереди в ожидании стрижки;

г) среднее время ожидания посетителя в очереди.

адача 5.

На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.

Отрасль	Прямые межотраслевые потоки	Конечная продукция

ВАРИАНТ №3

адача 1.

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

_{, ,}

_{, .}

адача 2.

При проектировании энергосистемы требуется решить, какой мощности строить гидро- и тепловые станции (x₁ и x₂), обеспечивающие общую (x₁ + x₂) максимальную установленную мощность, при условии, что известен удельный расход имеющихся ресурсов на 1МВт установленной мощности и предел по каждому ресурсу.

Ресурсы	Расход ресурсов на 1МВт мощности	Ограничения по ресурсам
ГЭС	ТЭС
Водные ресурсы, км3
Топливо, тыс.т
Кап. вложения, млн.руб.

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

адача 3.

Решить следующую транспортную задачу:

А=(20; 30;40; 10), В=(40;40;20), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

В мастерской по ремонту телевизоров работают 4 опытных мастера. В среднем в течение рабочего дня (8 часов) в соответствии с пуассоновским распределением в ремонт поступает 9 телевизоров. Каждый мастер успевает отремонтировать 3 телевизора в день, и продолжительность ремонта распределена по экс­поненциальному закону. Требуется определить:

а) вероятность того, что все мастера свободны от ремонта телевизоров;

б) вероятность того, что все мастера будут заняты;

в) среднюю длину очереди в ожидании ремонта;

г) среднее время ожидания каждым неисправным телевизором начала ремонта.

адача 5.

На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.

Отрасль	Прямые межотраслевые потоки	Конечная продукция

ВАРИАНТ №4

адача 1.

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

_{, ,}

_{, .}

адача 2.

Для производства трех видов продукции требуются два вида сырья. Количество сырья ограничено. Исходные данные приведены в таблице:

Тип сырья	Расход сырья на единицу продукции, кг/ед.	Количество сырья, кг.
П1	П2	П3
С1
С2
Прибыль, руб./ед.прод.

Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный объем производства продукции П1, П2 и П3, используя симплексный метод решения задач линейного программирования.

адача 3.

Решить следующую транспортную задачу:

А=(25; 25; 40), В=(15;15;30;30), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

В магазине имеются 2 продавца. Покупатели приходят в магазин в соответствии с пуассоновским распределением со средней частотой 3 человека за 5 мин. Обслуживание одного покупателя в среднем длится 3 мин, и продолжительность обслуживания распределена по экс­поненциальному закону. Требуется определить:

а) вероятность того, что в магазине не окажется ни одного покупателя;

б) вероятность того, что оба продавца будут заняты;

в) среднюю длину очереди в ожидании обслуживания;

г) среднее время ожидания покупателя в очереди.

адача 5.

На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.

Отрасль	Прямые межотраслевые потоки	Конечная продукция

ВАРИАНТ №5

адача 1.

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

_{, ,}

_.

адача 2.

Изготавливается смесь, в которой, кроме прочего, содержание вещества В1 должно быть не более 0,1 %, вещества В2 не более 16 %. Оба вещества содержаться в трех компонентах К1, К2 и К3. Компоненты добавляются к смеси в любых пропорциях и влияют на ее качество. Содержание веществ В1 и В2 в каждом компоненте, а также показатель качества смеси на 1 г каждого компонента приведены в таблице.

Характеристики	Вид компонента
К1	К2	К3
Содержание В1 в 1грамме компонента, %	0,03	0,01	0,01
Содержание В2 в 1грамме компонента, %
Показатель качества смеси, усл.ед./г.

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

адача 3.

Решить следующую транспортную задачу:

А=(40; 50;30; 70), В=(40;70;80),

где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

В обувной мастерской работают 3 мастера. В среднем в течение рабочего дня (8 часов) в соответствии с пуассоновским распределением в ремонт поступает 10 пар обуви. Каждый мастер успевает отремонтировать 5 пар обуви в день, и продолжительность ремонта распределена по экс­поненциальному закону. Требуется определить:

а) вероятность того, что все мастера свободны от ремонта обуви;

б) вероятность того, что все мастера будут заняты;

в) среднюю длину очереди в ожидании ремонта;

г) среднее время ожидания каждой парой обуви начала ремонта.

адача 5.

На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.

Отрасль	Прямые межотраслевые потоки	Конечная продукция

ВАРИАНТ №6

адача 1.

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

_{, ,}

_.

адача 2.

Для выпуска двух видов продукции требуются за­траты сырья, рабочего времени и оборудования. Количество ресурсов ограничено. Исходные данные приведены в таблице:

Тип ресурса	Hормы затрат ресурсов на единицу продукции	Наличие ресурсов, т
П1	П2
Сырье, т.
Рабочее время, час.
Оборудование, ед.
Прибыль на единицу продукции, руб.

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

адача 3.

Решить следующую транспортную задачу:

А=(30; 50; 50), В=(20;35;20;55), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

У службы доставки продуктов на дом имеется 2 автомобиля. Заказы на обслуживание поступают в соответствии с пуассоновским распределением со средней частотой 2 заказа в час. Обслуживание каждого заказа в среднем длится 45 мин, и продолжительность обслуживания распределена по экс­поненциальному закону. Требуется определить:

а) вероятность того, что все автомобили свободны от работы;

б) вероятность того, что оба автомобиля будут заняты;

в) среднюю длину очереди в ожидании обслуживания;

г) среднее время ожидания каждым заказом начала обслуживания.

адача 5.

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

Отрасль	Коэффициенты прямых затрат	Конечная продукция
	0,3	0,4
	0,5	0,1

ВАРИАНТ №7

адача 1.

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

_{, ,}

_{, .}

адача 2.

Для производства двух видов продукции требуются три вида сырья. Количество сырья ограничено. Исходные данные приведены в таблице:

Тип сырья	Расход сырья на единицу продукции, кг/ед.прод.	Количество сырья, кг.
П1	П2
С1
С2
С3
Прибыль, руб./ед.прод.

Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный объем производства продукции П1, П2, используя симплексный метод решения задач линейного программирования.

адача 3.

Решить следующую транспортную задачу:

А=(50; 35; 45), В=(30;65;25;10), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

В часовой мастерской работают 3 мастера. В среднем в течение рабочего дня (8 часов) в соответствии с пуассоновским распределением в ремонт поступает 3 часов. Каждый мастер успевает отремонтировать 2 часов в день, и продолжительность ремонта распределена по экс­поненциальному закону. Требуется определить:

а) вероятность того, что все мастера свободны от ремонта;

б) вероятность того, что все мастера будут заняты;

в) среднюю длину очереди в ожидании ремонта;

г) среднее время ожидания каждыми неисправными часами начала ремонта.

адача 5.

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

Отрасль	Коэффициенты прямых затрат	Конечная продукция
	0,6	0,2
	0,4	0,3

ВАРИАНТ №8

адача 1.

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

_{, ,}

_{, .}

адача 2.

Для производства двух видов продукции требуются три вида сырья. Количество сырья ограничено. Исходные данные приведены в таблице:

Тип сырья	Расход сырья на единицу продукции, кг/ед.прод.	Количество сырья, кг.
П1	П2
С1
С2
С3
Прибыль, руб./ед.прод.

Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный объем производства продукции П1, П2, используя симплексный метод решения задач линейного программирования.

адача 3.

Решить следующую транспортную задачу:

А=(45; 50; 40), В=(65;35;25;10), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

В швейном ателье работают 3 закройщика. В среднем в течение рабочего дня (8 часов) в соответствии с пуассоновским распределением поступает 5 заказов. Каждый мастер успевает выполнить 2 заказа в течение дня, и продолжительность выполнения заказа распределена по экс­поненциальному закону. Требуется определить:

а) вероятность того, что все закройщики свободны от работы;

б) вероятность того, что все закройщики будут заняты;

в) среднюю длину очереди в ожидании выполнения заказа;

г) среднее время ожидания каждого заказа в очереди.

адача 5.

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

Отрасль	Коэффициенты прямых затрат	Конечная продукция
	0,1	0,7
	0,2	0,3

ВАРИАНТ №9

адача 1.

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

_{, ,}

_{, .}

адача 2.

Для производства двух видов продукции требуются два вида сырья. Количество сырья ограничено. Исходные данные приведены в таблице:

Тип сырья	Расход сырья на единицу продукции, кг/ед.прод.	Количество сырья, кг.
П1	П2
С1
С2
С3
Прибыль, руб./ед.прод.

Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный объем производства продукции П1, П2, используя симплексный метод решения задач линейного программирования.

адача 3.

Решить следующую транспортную задачу:

А=(10; 85; 40), В=(70;35;10;20), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

В супермаркете имеются 4 кассы. Покупатели подходят к кассам в соответствии с пуассоновским распределением со средней частотой 2 человека за 5 мин. Обслуживание одного покупателя в среднем длится 5 мин, и продолжительность обслуживания распределена по экс­поненциальному закону. Требуется определить:

а) вероятность того, что у касс не окажется ни одного покупателя;

б) вероятность того, что все кассы будут заняты;

в) среднюю длину очереди в ожидании обслуживания;

г) среднее время ожидания покупателя в очереди.

адача 5.

На основании данных, приведенных в таблице, рассчитать объемы конечной продукции каждой отрасли и коэффициенты полных материальных затрат.

Отрасль	Коэффициенты прямых затрат	Совокупная продукция
	0,5	0,2
	0,3	0,6

ВАРИАНТ №10

адача 1.

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

_{, ,}

_{, .}

адача 2.

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

Исходная задача. Для производства двух видов продукции требуются два вида сырья. Количество сырья ограничено. Необходимо найти оптимальный объем производства продукции П1, П2, чтобы прибыль была максимальной. Исходные данные приведены в таблице:

Тип сырья	Расход сырья на единицу продукции, кг/ед.прод.	Количество сырья, кг.
П1	П2
С1
С2
Прибыль, руб./ед.прод.

адача 3.

Решить следующую транспортную задачу:

А=(20; 40; 70), В=(30;60;15;25), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

На ж/д вокзале имеются 4 кассы для продажи билетов. Пассажиры подходят к кассам в соответствии с пуассоновским распределением со средней частотой 3 человека за 5 мин. Продажа билетов одному пассажиру в среднем длится 5 мин, и продолжительность ее распределена по экс­поненциальному закону. Требуется определить:

а) вероятность того, что у касс не окажется ни одного пассажира;

б) вероятность того, что все кассы будут заняты;

в) среднюю длину очереди в ожидании обслуживания;

г) среднее время ожидания пассажира в очереди.

адача 5.

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

Отрасль	Коэффициенты прямых затрат	Совокупная продукция
	0,2	0,3
	0,1	0,6

КРАТКИЕ МЕТОДИЧЕСКИЕ УКАЗАНИЯ

для выполнения контрольной работы

ЗАДАЧА 1.В задаче линейного программирования (ЗЛП) требуется найти экстремум (максимум или минимум) линейной целе­вой функции f( ). Общая задача линейного программиро­вания выглядит следующим образом: найти

max(min) f( )=c1x1+c2x2+…+ cnxn,

(1)

при ограничениях (условиях):

a11x1+a12x2+…+ a1nxn { }b1,
a21x1+a22x2+…+ a2nxn { }b2,	(2)
………
am1x1+am2x2+…+ amnxn { }bm,
xj 0, j =	(3)

где a_ij, b_i, c_j (i= , j = )— заданные постоянные величины.

Вектор = (х₁, х₂, ..., x_п), удовлетворяющий системе ог­раничений (2), (3), называется допустимым решением, или планом ЗЛП. План (допустимое решение), который доставляет максимум или минимум целевой функции (1), называется опти­мальным планом (решением) ЗЛП.

еометрический (графический) метод решения задачи.

Если в ЗЛП ограничения заданы в виде неравенств с дву­мя переменными, она может быть решена графически. Задача ЛП в стандартной форме записи при п=2 выглядит следующим образом:

max(min) f( )=c1x1+c2x2,

(4)

при ограничениях (условиях):

a11x1+a12x2 b1,
a21x1+a22x2 b2,
………
am1x1+am2x2 bm,
x1 0, x2 0.

Каждое неравенство этой системы геометрически опреде­ляет полуплоскость с граничной прямой a_i1x₁+a_i2x₂=b_i,, i= . Условия неотрицательности определяют полуплос­кости соответственно с граничными прямыми х₁= 0, х₂= 0. Полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая представляет собой многоугольник решений (сово­купность точек, координаты каждой из которых составляют решение данной системы).

Гра­фический метод решения ЗЛП состоит из следующих этапов.

Этап 1. Сначала на координатной плоскости x₁ 0 x₂ стро­ится допустимая многоугольная область, соответствующая огра­ничениям, которая является пересечением множества полуплоскостей. Далее строится вектор-градиент линейной (целевой) функ­ции f( ) в какой-нибудь точке , принадлежащей допус­тимой области:

Этап 2. Строится прямая c₁x₁+c₂x₂=f( ) (линия уровня: целевая функция во всех точках этой прямой равна f( )),перпендикулярная век­тору-градиенту. Затем прямаяпередвигается в направлении вектора-градиента в случае максимизации f( ) до тех пор, пока не покинет пределов многоугольной области. Предельная точка области при этом движении и является точкой мак­симума f( ). В случае минимизации f( ) прямую c₁x₁+c₂x₂=f( ) надо двигать в направлении, противоположном вектору-гра­диенту.

Этап 3. Для нахождения координат точки максимума (минимума) достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума (минимума). Значение f( ), найденное в получаемой точке, является максимальным (минимальным).

ЗАДАЧА 2.В данной задаче необходимо найти решение с помощью симплексного метода. Симплексный метод - это универсальный метод решения ЗЛП. Суть его заключается в следующем.

Этап 1. Вначале исходная ЗЛП записывается в канонической форме.

Канонической формой записи задачи линейного програм­мирования (КЗЛП) называют задачу вида:

max f( )=

(5)

при ограничениях

	(6)
, j = .	(7)

Или в матричном виде: max f( )=CX при условиях AX = B, X 0.

Здесь С = (c₁, c₂,…, c_n,) — вектор-строка; А=(а_ij) — матри­ца размерности т x п, X и B - вектор-столбцы.

Расширенная матрица этой системы будет иметь вид:

=

Приведение ЗЛП к каноническому виду осуществляется введением в левую часть соответствующего ограничения вида (2) k-ой дополнительной переменной x_n+k 0 со знаком “-“ в случае ограничения типа и знаком “+” в случае ограниче­ния типа .

Дальнейшее решение ведется в в симплекс-таблицах.

№ табл.	Базис	Сб	План В	с1	с2	…	сj	…	сn	Q
A1	A2	…	Aj	…	An
0	A1	с1	b1	a11	a12	…	a1j	…	a1n
A2	с2	b2	a21	a22	…	a2j	…	a2n
…	…	…	…	…	…	…	…	…
Ai	сi	bi	ai1	ai2	…	aij	…	ain
…	…	…	…	…	…	…	…	…
Am	сm	bm	am1	am2	…	amj	…	amn
	L			…	Δj	…

Рис.1. Симплексная таблица

Этап 2. Предварительно получают допустимый вариант, удовлетво­ряющий всем ограничениям, но необязательно оптимальный (т.н. начальное опорное решение).

Для этого матрица системы уравнений должна содержать единичную подматрицу раз­мерностью т х т. Предположим, что после выполнения этапа 1 первые т век­торов матрицы системы составляют единичную матрицу. Тогда очевиден первоначальный опорный план: (b₁, b₂, ..., b_m,0, ...,0). Т.е. основные переменные являются свободными и равными нулю, а дополнительные переменные являются базисными и равны правым частям СЛУ.

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

Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие

, где , j = , (т.е. - скалярное произведение векторов столбцов С_б и A_j ), то можно получить новый опорный план, для которого зна­чение целевой функции будет больше исходного.

называют оценкой столбца j.

Теорема 2. Если для всех векторов выполняется условие , то полученный план является оптимальным.

Этап 3. Если решение не оптимальное, переходят к следующему опорному решению (плану) на основе применения метода Жордана-Гаусса для системы линейных уравнений; на­правление перехода от одного опорного решения к другому выбирается на основе критерия оптимальности исходной задачи.

На основании признака оптимальности в базис вводится вектор A_k, давший минимальную отрицательную величину симплекс-разности:

= z_k - c_k = min(z_j- c_j), j = , (т.е. имеющий минимальную отрицательную оценку)

Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор А_r, который дает минимальное положительное отношение

Q = , a_ik>0, i= .

Строка A_r называется направляющей, столбец А_k и эле­мент a_rk — направляющими (или ведущими).

Элементы вводимой строки, соответствующей направ­ляющей строке, в новой симплекс-таблице вычисляются по методу Жордана-Гаусса.

Число L в симплексной таблице – это текущее значение целевой функции: , т.е. скалярное произведение векторов столбцов С_б и В.

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

Для использования приведенной выше процедуры сим­плекс-метода к минимизации линейной формы f( ) следует искать максимум функции f₁( ) = - f( ), затем получен­ный максимум взять с противоположным знаком. Это и бу­дет искомый минимум исходной ЗЛП.

С каждой ЗЛП тесно связана другая линейная задача, называемая двойственной, первоначальная задача называется исходной или прямой.

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

g( )= min ,	(8)
,	(9)
, i = .	(10)

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

1) целевая функция исходной задачи (5)-(7) формули­руется на максимум, а целевая функция двойственной задачи (8)-(10 ) - на минимум, при этом в задаче на максимум все неравенства в функциональных ограниче­ниях имеют вид , а в задаче на минимум – вид ;

2) матрица А, составленная из коэффициентов при неизвестных в сис­теме ограничений (6) исходной задачи, и аналогич­ная матрица

=

в двойственной задаче получаются друг из друга транс­понированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений (6) исходной задачи, а число ограничений в системе (9) двойственной задачи - числу переменных в исходной задаче;

4) коэффициентами при неизвестных в целевой функции (8) двойственной задачи являются свободные члены в системе (6) ограничений исходной задачи, а правыми частями в ограничениях (9) двойственной задачи - коэффициенты при неизвестных в целевой функции (5) исходной задачи;

5) каждому ограничению одной задачи соответствует пере­менная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записан­ному в виде неравенства , соответствует переменная, связанная условием неотрицательности.

ЗАДАЧА 3.

Транспортная задача по критерию стоимости в общем виде формули­руется следующим образом. В т пунктах отправления А₁, А_{2, …,}, А_m , которые в даль­нейшем будем называть поставщиками, сосредоточено опре­деленное количество единиц некоторого однородного про­дукта, которое обозначим a_i ( i = 1, 2, ..., т). Данный про­дукт потребляется в п пунктах B₁, B_{2, …,}, B_n, которые будем называть потребителями; объем потребления обозначим b_j
(j = 1, 2, ..., n). Известны расходы на перевозку единицы продукта из пункта A_i в пункт B_j, которые равны c_ij и при­ведены в матрице транспортных расходов С = (c_ij).

Требуется составить такой план прикрепления потреби­телей к поставщикам, т.е. план перевозок, при котором весь продукт вывозится из пунктов А_i, в пункты B_j в соответ­ствии с потребностью и общая величина транспортных из­держек будет минимальной.

Обозначим количество продукта, перевозимого из пункта A_j в пункт B_j, через х_ij. Совокупность всех переменных х_ij для краткости обозначим .

Наиболее применяемым ме­тодом решения данной задачи является метод потенциалов, при котором каждой i-й строке (i-му поставщику) устанавливается потенциал u_i, который можно интерпретировать как цену продукта в пункте поставщика, а каждому столбцу j (j-му потребителю) устанавливается потенциал v_j, который можно принять ус­ловно за цену продукта в пункте потребителя. В простей­шем случае цена продукта в пункте потребителя равна его цене в пункте поставщика плюс транспортные расходы на его доставку, т.е.

vj=ui+cij.

(11)

Следует отметить, что ранг сис­темы линейных уравнений равен т + п - 1; таким образом из общего числа т п неизвестных базисных неизвестных будет т + п - 1. Вследствие этого при любом допустимом базисном распределении в матрице перевозок (таблице поставок), представленной в общем виде на рис. 2, будет занято ровно т + п - 1 клеток, которые будем назы­вать базисными в отличие от остальных свободных клеток; занятые клетки будем отмечать диагональной чертой.

Рис.2. Таблица поставок

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

Первым этапом является состав­ление начального распределения (начального плана перевозок); для реализации этого начального этапа имеется в свою очередь ряд методов: северо-западного угла, наименьших стоимостей и др.

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

В методе северо-западного угла всегда в первую очередь за­полняется клетка (из числа невычеркнутых), стоящая в верхнем левом (северо-западном) углу матрицы перевозок. В различных модификациях метода наименьших стоимо­стей заполнение клеток матрицы перевозок проводится с учетом значений величин c_ij. Так, в модификации «двойно­го предпочтения» отмечают клетки с наименьшими стоимо­стями перевозок сначала по каждой строке, а затем по каж­дому столбцу. Клетки, имеющие две отметки, заполняют в первую очередь, затем заполняют клетки с одной отметкой, а данные о нераспределенном грузе записывают в неотме­ченные клетки с наименьшими стоимостями.

Вторым этапом служат построение системы потенциалов на основе равенства (11) и проверка начального плана на оптимальность; в случае его неоптимальности переходят к третьему этапу.

Введем специальные показатели u_i для каждой строки матрицы перевозок (каждого поставщика), где , и показатели v_j для каждого столбца (каждого по­требителя), где . Эти показатели называются потен­циалами поставщиков и потребителей, их удобно интерпре­тировать как цены продукта в соответствующих пунктах по­ставщиков и потребителей. Потенциалы подбираются таким образом, чтобы для заполненной клетки (i;j) выполнялось равенство (11).

Совокупность уравнений вида (11), со­ставленных для всех заполненных клеток (всех базисных неизвестных), образует систему т + п - 1 линейных урав­нений с т+п неизвестными u_i и v_j. Эта система всегда со­вместна, причем значение одного из неизвестных можно задавать произвольно (например, и₁= 0), тогда значения остальных неизвестных находятся из системы однозначно.

Чтобы оценить оптимальность распределения, для всех клеток (i;j) матрицы перевозок определяются их оценки, ко­торые обозначим через d_ij, по формуле:

dij=(ui+cij)- vj.

(12)

Используя ранее принятую интерпретацию, выражение (u_i+c_ij) можно трактовать как сумму цены продукта у по­ставщика и стоимости перевозки; эта сумма путем вычита­ния сравнивается с ценой продукта у соответствующего потребителя v_j. Очевидно, оценки заполненных клеток рав­ны нулю. Таким образом, условием оптималь­ности распределения служит условие неотрицательности оценок свободных клеток матрицы перевозок. Оценки клеток по формуле (12) удобно представить в виде матрицы оценок.

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

Чтобы улучшить неоптимальный план перевозок, выбирается клетка матрицы перевозок с от­рицательной оценкой; если таких клеток несколько, то обычно выбирается клетка с наибольшей по абсо­лютной величине отрицательной оценкой. Для выбранной клетки строится замкнутая линия (контур), начальная вершина которой лежит в выбранной клетке, а все остальные вершины находятся в занятых клетках; при этом направления отдельных отрезков контура могут быть толь­ко горизонтальными и вертикальными. Вершиной контура, кроме первой, является занятая клетка, где отрезки контура образуют один прямой угол. Очевидно, число отрезков контура, как и его вершин, будет четным. В вершинах контура рас­ставляются поочередно знаки «+» и «-», начиная со знака «+» в выбранной свободной клетке.

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

Пример простого контура показан пунктиром на рис. 3.

Рис. 3. Пример таблицы поставок

ЗАДАЧА 4.

Данная задача отражает процесс моделирования систем массового обслуживания (СМО). СМО - это такие системы, в кото­рых, с одной стороны, возникают массовые запросы (требо­вания) на выполнение каких-либо услуг, с другой - проис­ходит удовлетворение этих запросов. СМО включает в себя следующие элементы: источник требований, входящий поток требований, очередь, обслуживающие устройства (каналы об­служивания), выходящий поток требований. Исследованием таких систем занимается теория массового обслуживания.

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

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